グラフの連結性について
教科領域教育専攻 自然系コース(数学) 坂 手 隆 人
はじめに
グラフとは，直感的には平面上の点の集ま りと，これらの点どおしを適当に辺といわれ る線で結んだものとして図式化できるもので ある.グラフはその単純さにもかかわらず，
様々な応用と深い定理を持つ.またグラフは 集合の要素聞の2項関係の外延的表現とみな すことができることから，計算機科学，シス テム科学，電子工学，心理学，社会学，経済 学，情報工学，管理工学，などの多くの分野 で、数学的モデ、ルとして広く応用されている.
本研究は，連結グラフの連結の度合の研究 を意図して始められた.連結の度合というの は，グラフから任意にいくつかの頂点を取り 除くとき，結果としてできる部分グラフが依 然連結性を保つためには最大何個まで取り除 けるかということである.また頂点のかわり に辺を取り除くということも同様に考察の対 象となる.この問題は現実の中への応用とし ては，例えば通信路の設計の問題とかかわっ ている.
グラフの連結度(connectivity)に関する最 も基本的な定理はMeng俳句 Theoremであ る.この定理はグラフ理論の異なる分野に 属する 2つの重要な定理と深い関係にある ことが明らかにされている. 1つは有向グ ラフ上の flowに関する FordとFulkerson による M ω‑flow Min‑cut Theoremであ る.もう 1つはマッチング、の分野で、のHallの Mαrriage Theoremである.したがって本論 文の目的は次の 2つになる.
指導教官 湯 谷 洋
1.頂点連結度と辺連結度を考察する.
2.上記 3つの定理の関係を明らかにする.
以下で本論文の内容を述べていく.
1.
グラフ理論の基本的な定義と定理
まずこの第1章でグラフ理論の基礎的な概 念や結果を与える.
~ 1. グラフについて
ここではまずグラフに関しての基本的な定 義と定理を与える.
~ 2.有向グラフについて
ここでは有向グラフに関して，あとで必要 となる定義と定理を与える.また有向グラフ の利用例としてトーナメントでの順位付けを 取り上げる.
2 . 有向グラフにおける f 1 ω
この章では，有向グラフにおける flowに 関する諸定理を与え ，Mαx‑floω Min‑ωt Theoremを示す.これは輸送路の問題とし て知られているものの内容となっている.
~ 1. flowについて
source (流出口)とsink(流入口)といわれ る 2点s，
t
をもった有向グラフG = ( V，E )
を
考える.またnon‑negαtivefunction c : E →
Rが与えられているとする.c(
ゆ) =
c(x，y) を弧ゅの容量(capacity)という .source sか らsinktへの floωとは次の2条件を満足す る関数f:E→
Rのことである.1.すべてのめ
εE
に関して，o : ; : :
f(x，
y)三c(x，
y).2.すべてのx
f j :
{s，t}に関して，Zへのflω の全流入量
二 Zからのflowの全流出量
条件2からわかるように我々が考察する flowはいわゆる定常流である.
この定義から
r
source sでの実質の流出 量=sink tでの実質の流入量J が証明さ れる.この量を総流量とよびv(f)で表す.次に S
εS
かっ tj : f
Sであるような集合S
を考える.このとき
E(S
，
SC) ={ め ε
ElxεS
かつν ε
SC} をcutという.fl仰 と cutとの関係を明らかにするのがこ の章の内容となる.
まず全流量υ(f)がcutE(S， SC)とE(SC，S) 上でのflowによって表される.次にc(S，SC) をcutE(S，SC)上での容量の和とするとき，
v(f)壬c(S，SC)であることが示される.
Mαx‑flow Min‑cut Theoremは， Mαx{υ(f)} =凶 n{c(S
，
SC)} となることをいったものである.3 . 連結性と Me n g e r ' s Tearem
この章ではグラフの連結性に関する諸定理 を与え，連結性に関する最も基本的な定理で ある Menger'sTeoremを示す.第 2章で取 り扱ったMαx‑floωMin‑cutTheoremから 多くの結果が導けるがMenger乍Theoremは その1つである.
~ 1. グラフの連結性
連結グラフが k‑連結 (k‑頂点連結)とは，
任意のk‑1個の頂点を取り除いてもそれか らできる部分グラフが連結であることをいう.
連結グラフの連結度κ(G)はグラフがk‑連結 であるような最大のkとして定義される.従っ
て κ
( G )‑
1以下の個数の任意の頂点を除い てもグラフは連結であるが， κ( G )
個の頂点 の集合でそれを除くとグラフが非連結となる ものが存在する.k‑辺連結と辺連結度入(G)も同様に定義さ れる.
κ(G)と入(G)について次の2つの基本的な 関係式が示される.
1.κ(G) ‑1 :::;κ(G‑{x})かっ 入(G)‑1三入(G‑{xy})三入(G) 2.κ(G)壬入(G):::; <5 ( G)
ただし <5(G)はGの頂点の次数の最小値で ある.
連結グラフ G のbridgeとその両端の点か らなる部分グラフと極大 2‑連結部分グラフ をblockとよび，blockと連結性，cutvertex の聞の関係を考察する.
~ 2. Meng俳句 Theoremについて
W を連結グラフ Gの頂点または辺の集合 とする
.G‑W
が非連結となり，頂点s，tが 異なる成分に属するとき W はSとtを分離 するという .s‑t Pαthの集合を考えたとき，任意の2つのpathが頂点を共有しないとき disjointであるといい，辺を共有しないとき edge圃disjointであるという.
Menger匂 Teoremとは，連結グラフ G に対して sとtを分離する頂点の個数の 最 小 値 は disjointな s‑t pathの 個 数 の 最 大 値 に 等 し い こ と と 、 同 様 の 内 容 が 辺 に ついてもいえることを述べたものである.
Mengerセ TheoremをMαx‑f low M in‑cut Theoremを用いて証明する.
~ 3. M enger' s Theoremの応用
この節では Menger匂 Theoremを用いて HallのMarriageTheoremを証明する.そ のために必要なマッチング、の定義を合わせて 述べる.
