グラフ理論
用語
正則グラフ
すべての頂点の次数が同一
単純グラフ
並列枝と自己ループの無いグラフ
定理の強弱
2つの定理
定理A:$ P \Rightarrow Q
定理B:$ R \Rightarrow Q
が存在し,$ P \subset Rであるとき,「BはAより強い定理である」という
BはAより条件が弱いことに注意
条件が弱いので強い定理なのである
補グラフ
補グラフ$ \bar{G}とは,$ Gの枝があるところには枝がなく,枝がないところに枝があるようなグラフである.
walk(歩道)
頂点と枝が交互に並んだもの
trail(小道)
walkのうち,枝の重複がないもの
頂点の重複を許容する
path(道)
walkのうち,枝と頂点の重複がないもの
ただし頭と終わりは同じでも良い
circuit(回路)
trailのうち,頭と終わりの頂点が同じもの
cycle(閉路)
pathのうち,頭と終わりの頂点が同じもの
細かい定理
握手定理
任意のグラフの次数の合計は偶数になる
次数列の単純グラフ化可能性
$ (3, b, c, d, e) のグラフ化可能であることは $ (b-1, c-1, d-1, e)のグラフ化可能であることと同値
証明:
まず,$ (b-1, c-1, d-1, e)がグラフ化可能ならば$ (3, b, c, d, e)がグラフ化可能なのは自明
次に,$ (3, b, c, d, e)がグラフ化可能ならば$ (b-1, c-1, d-1, e)がグラフ化可能なのは,非自明
頭の次数に当たる頂点を削除したグラフ$ Gが$ (b-1, c-1, d-1, e)のグラフになるとは限らない
ここで,「$ Gの枝を1つ削除して別のところに生やす」という操作を繰り返して,$ (b-1, c-1, d-1, e)のグラフ$ G^{\prime}を作れることを示せる.
略された証明:次数列のうち,$ d(u) > d(v)となるような頂点$ u, vに関して,他の頂点の次数に影響を与えずに,$ uから$ vへと次数を「移動」することができる.
仮定$ d(u) > d(v)から,$ (u, w) \in E \land (v, w) \not\in Eとなるような$ wが一つ以上存在する.この$ wについて,$ (u, w)を削除し,$ (v, w)を作成することで,他の頂点に影響を与えることなく次数を「移動」することができる
最小全域木
連結な枝重み付きグラフ$ G(V, E)について,グラフの連結性を失わないように$ E^{\prime} \subseteq Eを選び,かつ枝重みの合計が最小となるように作られた木$ G(V, E^{\prime})
クラスカルのアルゴリズム
重みの小さい枝から順番に見ていき,閉路が発生しなければその枝を$ E^{\prime}に加えるという動作を,グラフが連結になるまで行う.
オイラー回路
すべての枝をちょうど一回づつ通る回路
頂点の重複を許容する
オイラー回路の存在判定
すべての頂点の次数が偶数である $ \Leftrightarrow オイラー回路が存在する
$ \Leftarrow:始点以外の頂点に移動するとき1本枝を消費する.出ていくときにも1本消費する.従って,入って出るときには2本枝を消費する.従って,オイラー回路が存在するなら,始点以外の頂点は2n本の枝を持つ.また,始点については,初めに始点から出るときに1本,最後に始点に戻ってくるときに1本枝を消費するので,偶数本の枝を持つ.
$ \Rightarrow:始点$ vを任意に決める.$ v以外の頂点に出入りするとき,2本の枝を消費する.従ってすべての次数が偶数であるとき,入れたのであれば出ることができる. $ vに戻ってきたとき,枝は偶数本残っているはずであり,0本でなければ再び出ていくとができ,それができなくなるのは$ vを始点とした回路($ C_1)が作成されたときである.$ C_1がオイラー回路になっていないとき,$ G上で$ C_1に使われている枝を取り除き,孤立頂点ができたらそれも取り除き$ G^{\prime}を作る.このとき,$ G^{\prime}の頂点の次数はすべて偶数になっている.$ G^{\prime}には,$ C_1に含まれていた頂点$ uが存在するはずである.$ G^{\prime}上で$ uから始まる回路$ C_2を作ることが可能である.ここで,元のグラフ$ Gに戻って,$ C_1と$ C_2を連結した回路を考えることができる.これを繰り返していくとオイラー回路ができる.
ハミルトン閉路
すべての頂点をちょうど一回づつ通る閉路
頂点の重複を許容しない
辺の重複を許容しない
ディラック条件
すべての頂点$ vについて$ d(v) \geq n/2である
ディラックの定理
$ G=(V,E),$ |V| \geq 3とする.ディラック条件が成り立つとき,ハミルトン閉路が存在する
証明:ディラック条件が成り立つ$ Gにハミルトン閉路が存在しないと仮定して矛盾を導く
.$ Gに枝を追加してもディラック条件は保たれる.「これ以上枝を追加するとハミルトン閉路が存在してしまう」というところまで枝を追加する.このとき,ハミルトン道$ v_1v_2..v_{n-1}v_nが存在し,定義より$ v_1と$ v_nの間に枝はない.ディラック条件より,$ d(v_1) \geq n/2-1, d(v_n) \geq n/2-1である.従って,$ v_1は$ v_3..v_{n-1}に対して$ n/2-1以上の枝を持ち,$ v_nは$ v_2..v_{n-2}に対して$ n/2 - 1の枝を持つ.鳩の巣原理より,ある$ iがあって,枝$ (v_1, v_i),$ (v_{i-1},v_n)が存在する,このとき,ハミルトン閉路$ v_1..v_iv_n..v_{i-1}..v_1が存在する.よって矛盾.
オーレの定理
$ G=(V,E),$ |V| \geq 3とする.隣接していない任意の頂点$ v,wについて$ d(v) + d(w) \geq |V|が成り立つとき,ハミルトン閉路が存在する
Dijkstra法
計算ができるか?
平面グラフ
平面グラフと平面的グラフの違い
平面的グラフ:平面上に線が交差しないように描画できるグラフ
平面グラフ:平面的グラフを実際に平面に描画したグラフ.描画の仕方も含んでいるということになる.
オイラーの公式
連結なグラフGについて,$ nv(G) + h(G) = ne(G) + 2 である
ただし$ h(G)はGの面数
証明
.$ nv(G) + ne(G)に関する帰納法で考える
.$ nv(G) + ne(G)=1すなわち孤立頂点の時は成立
.$ nv(G) + ne(G) \leq k の任意のグラフにおいて成立すると仮定し,$ nv(G) + ne(G) = k +1の任意のグラフについて考える
次数1の頂点がある場合
その頂点と付属する枝を削除すると,$ nv(G^{\prime}) = nv(G) -1,$ ne(G^{\prime}) = nv(G) -1となり,また$ nv(G^{\prime}) + ne(G^{\prime}) = k-1であるから$ nv(G^{\prime}) + h(G^{\prime}) = ne(G^{\prime}) + 2が成立する($ h(G)は変化しない).ここから$ nv(G) + h(G) = ne(G) + 2が導かれる.
ない場合
連結性を崩さないように枝を一本削除する.このとき$ ne(G^{\prime}) = ne(G) -1となり,$ h(G^{\prime}) = h(G) - 1となる(2つの面が結合されるため).さらに$ nv(G^{\prime}) + ne(G^{\prime}) = kが成立し,帰納法の仮定から$ nv(G^{\prime}) + h(G^{\prime}) = ne(G^{\prime}) + 2となる.ここから$ nv(G) + h(G) = ne(G) + 2が導かれる($ nv(G)は変化しない).
頂点彩色
頂点彩色数:$ \chi(G)
任意の$ Gは$ \Delta(G) + 1色で頂点彩色可能
どの頂点も高々$ \Delta(G)の隣接頂点しか持たない.なので,仮にすべての隣接頂点が異なる色で塗られていたとしても$ \Delta(G)色しか使われていない.従って,$ \Delta(G) + 1番目の色で塗ることができる.
完全グラフ,奇数長閉路は$ \Delta(G)色で塗ることができない
ブルックスの定理
完全グラフ,奇数長閉路以外のグラフは$ \Delta(G)色で頂点彩色できる
定理:正則でない連結グラフは$ \Delta(G)色で頂点彩色できる
証明:全域木を作る.$ Gは正則でないので$ d(v) < \Delta(G)となるような$ vが必ず存在する.$ vを全域木の根とする.ここで,全域木の葉から彩色していくのだが,以下の手順で彩色する.
頂点$ uを彩色できるのは,全域木において$ uより葉側の頂点がすべて彩色されている場合のみである
この手順で彩色するとき,$ uは根側に1つ未彩色の隣接頂点をもつ.$ d(u) \leq \Delta(G)であるから,少なくとも1色は彩色可能な色が存在する.
また$ vに関しては,$ d(v) < \Delta(G)から,少なくとも1色は彩色可能な色が存在する.
k-頂点彩色問題
k色で彩色可能か?
1-頂点彩色問題
枝があったら彩色できない.なければできる.
2-頂点彩色問題
以下の3つは同値
2-頂点彩色可能
2部グラフである
奇数長閉路が存在しない
証明
2-頂点彩色可能 $ \Leftrightarrow 2部グラフである
2-頂点彩色可能であるとする.色によって頂点集合を2つに分割する.分割されたそれぞれの頂点集合について,その内部に枝が存在しないため,グラフは2部グラフである.
また,2部グラフであるとすると,それぞれの内部に枝がない2つの頂点集合に分割することができ,このときそれぞれの集合を同一の色に彩色すれば2-頂点彩色したことになる.
2-頂点彩色可能 $ \Leftrightarrow奇数長閉路が存在しない
まず「奇数長閉路が存在する $ \Rightarrow2-頂点彩色可能でない」を示す.これは「2-頂点彩色可能 $ \Rightarrow奇数長閉路が存在しない」の対偶である.奇数長閉路の起点から交互に色を塗っていく必要があるが,起点と終点が同じ色になってしまうので彩色不可能である.
「奇数長閉路が存在しない $ \Rightarrow2-頂点彩色可能」を示す.任意の頂点$ uを集合$ S_1に入れる.以下,$ S_kを「$ S_{k-1}と隣接しており,それまで集合$ Sに入れられていない頂点の集合」として構築していく.このとき,①2つ以上離れた$ Sに所属している頂点間には枝がない(あった場合構築方法と矛盾).②$ S内に枝がない(あるとすると奇数長閉路ができるため矛盾)が言える.このとき$ S_1S_2S_3..S_nの内部の頂点を交互に2色で塗ることで頂点彩色ができる.
集合$ S内に枝がないことを示す.集合$ S_i内に枝があると仮定する.この2頂点$ u_i, w_iが$ S_{i-1}内の①同一の頂点に枝を持つ場合と②持たない場合について考える.
①長さ3の奇数長閉路が存在するので矛盾.
②$ u_i, w_iはそれぞれ$ S_{i-1}に隣接頂点$ u_{i-1}, w_{i-1}を持つ.$ u_{i-1}, w_{i-1}は$ S_{i-1}の作り方より,$ S_{i-2}の中に隣接頂点を持つ.この議論を進めていくと,いつかは$ S_1に共通隣接頂点$ vを持つことになるが,これは奇数長閉路なので矛盾($ vに辿り着く前に共通隣接頂点が存在する場合,そこで奇数長閉路が存在することになり矛盾).
https://gyazo.com/5cbf76f76bb6790e2d6ae4e87b762e96
3-頂点彩色問題
NP完全である
4-頂点彩色問題
NP完全である
4色問題
空白の地図を,隣り合う領域の色が同じにならないように4色で彩色することができるか?という問題
平面グラフの4-頂点彩色問題に帰着できる
領域を頂点にして,隣り合う領域同士を枝でつなぐ.逆をすると逆に帰着できる.
5色問題
任意の平面グラフは5-頂点彩色可能である
補題:平面グラフには次数5以下の頂点が必ず存在する
頂点数$ kに関する帰納法
.$ k \leq 5では自明
.$ k以下で成立を仮定し,$ k+1で成立を示す
ある最小次数の頂点$ vを削除する.
このときグラフは頂点数$ kになるので5-頂点彩色できる.$ d(v) < 5であれば$ vを戻して5色目で塗れば彩色可能
.$ d(v) = 5かつ全部違う色で塗られているとき,その中で2つの色に着目し,片方の色の頂点から頂点をたどり,その2色の頂点だけからなる部分グラフを考える.この部分グラフの色を反転しても,彩色状態は崩れないが,$ vの周囲で使われる色は1色減っており,$ vを戻してその色塗ればよい.
このとき,部分グラフの中に$ vの隣接頂点が2つ含まれる可能性がある(部分グラフがぐるっと一周して$ vにたどり着く場合).この場合色を反転させても色が減らない.ところが,先程選択した2色以外の色を2つ選んで同じことをやると,今度は部分グラフが一周することはありえない(というか,ありえないように初めの2頂点を選ぶことができる).なので,この2色を反転すると1色空くので$ vを戻して色が塗れる.
辺彩色
辺彩色数: $ \chi^{\prime}(G)
定義より
$ \Delta(G) \leq \chi^{\prime}(G)
少なくともグラフの最大次数の数だけ色が必要
ビジングの定理
$ \chi^{\prime}(G) \leq \Delta(G) + 1
教科書に証明なし
ケーニッヒの定理
2部グラフ$ Gに関して
$ \chi^{\prime}(G) \leq \Delta(G)
すなわち $ \chi^{\prime}(G) = \Delta(G)
証明:枝数に関する帰納法.
枝数kの任意のグラフについて$ \chi^{\prime}(G) \leq \Delta(G)という仮定から,枝数k+1のグラフについても$ \chi^{\prime}(G) \leq \Delta(G)ということを示す.
枝数k+1のグラフGから枝を一本取り除いて枝数kのグラフ$ G^{\prime}を作り,その枝を戻したときに彩色状態を保持できるということを示す
最大流問題
枝重み付き有向グラフ$ G = (V, E), wにおいて,ソース$ sとシンク$ tの2つの頂点があるとする.このとき,以下の条件を満たす$ fを考え,$ \sum_{tに入る枝} f(e)が最大となるような$ fを求める
すべての弧$ eについて$ f(e) \leq w(e)
.$ s,$ tを除く全ての頂点$ vについて$ \sum_{vに入る枝}f(e) = \sum_{vから出る枝}f(e)
残余ネットワーク$ R
現在のフロー$ fに対して定義される枝重み付き有向グラフである.頂点は$ Gと共通.弧は$ Gの弧と同じ頂点間に同じ向きかつ重みが$ w(e) - f(e)であるものと,$ Gの弧と同じ頂点間かつ向きが逆で重みが$ f(e)であるような弧の2つがある.ただし弧の重みが0となる弧は描画しない.
入力$ Dのある弧にそって(負の向きも含めて),あとどれだけ流すことができるかを表すグラフ
増大道$ P
残余ネットワーク上で$ sから$ tに至る道
$ c(P) = P上で最も重みが小さい弧の重み
フォード・ファルカーソン法
初期フロー$ fを求める
.$ fに従って残余ネットワーク$ Rを構築する
.$ R上で増大道を探し,存在すれば更に$ c(P)だけ流すように$ fを更新する.なければ$ fを出力する.これを繰り返す.
定理:残余ネットワークに増大道が存在しないとき,$ fは最大フローである
.$ Xを,$ sから到達できるすべての頂点の集合とする.このとき,$ D上で$ Xの内部から外部へ出ていく弧(外向き弧)はすべて容量が使われており,内向き弧には全く流れていない(※).容量保存則から,$ sから出ている流れ(フロー)と外向き弧の容量の合計は等しい.ところで,$ Xから外に出力できる流れの最大量は外向き弧の容量の合計に等しい.従って$ fは最大フローである.
マッチング
$ (V, E)において$ M \subseteq Eであり,$ Mに含まれる枝と接続するどの2つの枝も同じ頂点と接続しないとき,$ Mをマッチングという.$ Mに含まれる枝の数$ |M|をサイズという.
極大マッチング
$ Mに他のどの枝を追加してもマッチングにならないとき,$ Mを極大マッチングという
最大マッチング
$ Mのサイズが$ Gから得られるマッチングのなかで最大のとき,最大マッチングという
極大だが最大ではないマッチング
○ー○=○ー○
極大だが最大ではない
○=○ー○=○というマッチングがある
完全マッチング
すべての頂点が含まれるマッチング
このとき$ |M| = |V|/2である
2部グラフのマッチング
$ G = (U, V, E)とする.また,$ |U| = |V|とする.
ホール条件:$ S \subseteq Uなる$ Sを考える.$ \delta(S)を「$ Sの頂点のうち少なくとも1つと隣接する$ V内の頂点の集合」とするとき,すべての$ Sについて$ |\delta(S)| \geq |S|である
ホールの定理
$ Gがホール条件を満たすことと,$ Gが完全マッチングを持つことは同値である.
交互道
$ Gのマッチング$ Mにおいて,$ Mの枝と$ E- Mの枝を交互に通るような道を交互道という
増大道
交互道のうち,終わりの枝と始まりの枝が$ Mに含まれないものを増大道という
増大道の枝の役割を入れ替えたもの(マッチングに含まれていた枝をマッチングから削除し,含まれなかったものをマッチングに追加したもの)もマッチングである.このとき,マッチングのサイズが1増加している
.$ Mが増大道を持たないことと,$ Mが最大マッチングであることは同値である
証明:$ Mが増大道を持つことと,$ Mが最大マッチングでないことは同値,を示す
増大道を持つとき,入れ替え操作を行うと$ Mのサイズが増加するので,$ Mは最大マッチングでない
.$ Mが最大マッチングでないとき,最大マッチング$ M^*が存在して$ |M| < |M^*|である.このとき,$ G = (U, V, (M \lor M^*))を考える.このとき並列枝を許容する.このグラフの連結成分は道か閉路であり,$ Mと$ M^*の枝が交互に出現する.$ |M| < |M^*|であるから,$ M^*から始まって$ M^*で終わるような奇数長の道が必ず1つ存在する(閉路と偶数長の道は同じ数の$ Mと$ M^*の枝を持つため).$ M^*の枝は$ Mに含まれないことから,この道は$ Mにおいての増大道にほかならない.
ハンガリー法
任意のマッチング$ Mを求める
.$ M上の増大道を発見したら,役割を入れ替えて$ Mを更新する.発見できなければ$ Mを最大マッチングとして出力する
どのように発見するのか?$ Mに含まれない$ Uの頂点$ uから交互道をtraverseしていく(既に通った枝は通らない).