アルゴリスト

アルゴリズムについてのブログ

treeの性質 - グラフ理論入門6

閉路を含まないグラフをforestと定義し、連結なforestをtreeと呼ぶ。

定理: グラフTに点がn個あるとき、以下の命題は同値。

  1. Tはtree
  2. Tに閉路がなく、辺がn-1ある
  3. Tは連結で、辺がn-1ある
  4. Tは連結ですべての辺はbridge
  5. Tの任意の2点を結ぶ道は1本
  6. Tに閉路はなく、新しい辺をどのように付け加えても1個の閉路ができる

証明: n=1の場合は自明。n ≧ 2のときは、[1 => 2] 定義より、Tに閉路はないので、任意辺を除去すると2つのグラフに分離されてどちらもtreeである。帰納法より、2つの木の辺の本数は点より1だけ小さいので、Tの辺数はn-1。[2 => 3] Tが非連結なら、Tの各連結成分は閉路のない連結グラフなので、各成分の点の数は辺より1多い。よっってTの点の数の和は辺数の合計より2多いことになり、Tに辺がn-1本あるという事実に矛盾。[3 => 4] Tの任意辺を除去してできるグラフにはnの点とn-2の辺があり、このページの2つ目の定理より非連結である必要がある。[4=>5] Tは連結なので、任意の2点は1本以上の道で結ばれている。もし2本の道で結ばれている2点があれば、閉路が存在し、すべての辺がbridgeであることに反する。[5=>6] もしTに閉路があれば、その閉路の任意の2点は2本以上の道で結ばれていることになり矛盾。一本の辺eをTに加えると、eの両端点はTにおいてすでに結ばれているので閉路ができる。[6=>1] Tが非連結と仮定。Tの1つの成分の点と他の成分の点を結ぶ辺を付加しても閉路はできない。□

  • forest Gにはn個の点とk個の成分があるとすると、Gにはn-k本の辺がある。
  • treeのn点の次数の和は辺数の2倍、つまり2n-2になる。よって、n ≧ 2なら、n点のtreeには端点が少なくとも2個ある。
  • 連結グラフGがあるとき、閉路を選んで1本の辺を除去しても、残りは連結。閉路がなくなるまで繰り返すと、残ったグラフはtreeとなり、Gの全点を連結する。これをGのspanning treeという。
  • より一般に、Gを任意グラフとしてn点とm辺とk成分があるとすれば、Gの各成分にspanning treeの手続きを実行して得られたものはspanning forestという。
  • 除去される辺の本数はGのcycle rank γ(G) = m - n + k で表す。
  • spanning treeの辺の本数 cutset rank ξ(G) = n-k も定義できる。

定理: TがグラフGのspanning forestなら、

  1. GのすべてのcutsetはTと共通な辺を持つ。
  2. Gのすべての閉路はTの補グラフと共通な辺を持つ。

証明: [1]  C^* をGのカットセットとする。これを除去すると、Gのある成分が2つの部分グラフHとKに分離する。このとき、Tはspanning forestなので、Hの点とKの点を結ぶ辺がTに含まれる。[2] CはGの閉路で、Tの補グラフと共通の辺は持たないと仮定すると、CはTに含まれてしまうので矛盾。

  • spanning forest Tに関連した基本閉路集合は、Tに含まれていないGの任意の辺をTに付加することで閉路が1つでき、こうしてできる閉路全体の集合。基本集合の中の閉路の個数はグラフの閉路階数に等しい。
  • Tに関連した基本カットセット集合は、Tの任意辺を除去してTの点集合は互いに素な2つn点集合VとWに分割され、Vの点とWの点を結ぶGの辺のすべてからなる集合はGのカットセットで、こうして得られるカットセット全体の集合。

参考

ハミルトングラフ - グラフ理論入門5

すべての点を1度だけ通ってもとに戻る閉じた小道が存在するなら、その閉路をハミルトングラフという。すべての点を通る道がある場合は半ハミルトングラフ。知られている定理の多くは「Gに十分の多くな辺があれば、Gはハミルトンである」という形をしており、この中で有名なものはDiracの定理として知られる。それよりもより一般的なものはO.Oreによるもの。

定理: 単純グラフGにはn(≧3)個の点があるとする。隣接していない任意の2点vとwについて、 deg(v) + deg(w) \geq n が成立するならGはハミルトングラフ。

証明: 定理が偽とする。Gはハミルトングラフではないが、n個の点を持ち、点次数に関する上の条件を満足しているとする。もう1本どんな辺を付け加えてもハミルトングラフになると仮定してもよい。したがってGにはすべての点を含む道  v_1,...,v_nがある。しかし、Gはハミルトングラフではないので、道の始点 v_1と終点 v_nは隣接しない。よって deg(v_1)+deg(v_n) \geq nである。したがって、点 v_i v_1に隣接し、 v_{i-1} v_nに隣接するような2つの点 v_i v_{i-1}が存在する。このときGは  v_1,v_2,...,v_{i-1},v_n,v_{n-1},...,v_{i+1} ,v_i ,v_1 となるハミルトン閉路があることになり矛盾。□

系(Dirac): 単純グラフGにn(≧3)個の点があるとすると、すべての点vについて deg(v) \geq \frac{1}{2}nならばGはハミルトングラフである。

証明: 任意の2点v,wについて deg(v)+deg(w) \geq nなのでOreの定理から直ちに証明できる。

参考

オイラーグラフ - グラフ理論入門4

連結グラフGのすべての辺を含む閉じたtrailがあるとき、Gはオイラーグラフという。

補題: Gの点の次数がすべて2以上ならGには閉路がある。

証明: Gにループや多重辺があるときに閉路があることは自明なので、Gは単純グラフと仮定できる。vがGの任意の点とすると、vに隣接する v_1を選び、同様に  i \geq 1に対して v_iに隣接する  v_{i+1} を選び、walkを作る。Gの点は有限なので、いずれは前に選んだ点をもう一度選ぶことになる。このような点 v_kは、walk上の2つの v_kの間の部分を閉路とする。□

定理: 連結グラフGがオイラーグラフであるための必要十分条件は、Gの点の次数がすべて偶数であること。

証明: 各点の次数が偶数とする。Gは連結なので、次数はどの点も2以上で、補題より閉路Cを含む。CにGのすべての辺が含まれているなら証明が終わるので、そうでない場合を考える。GからCの辺を除去して得られるグラフHの辺数はより少なくなり、どの点の次数も偶数である。帰納法により、各成分にはオイラー小道がある。Gの連結性より、Hの各成分はCと1つ以上の点を共有するので、Gのオイラー小道が次のように作れる。Cの辺をたどり、Hの孤立点でない点が現れたらその点を含むHの成分のオイラー小道を辿ってその点に戻り、またCの辺をたどることを続けて、Hの他の成分の点が現れたら同じことをする。これを繰り返し、終了したときに出発点に戻る。□

系: 連結グラフがオイラーグラフであるための必要十分条件は、その辺集合が互いに素な閉路に分割できること。

系: 連結グラフが半オイラーグラフであるための必要十分条件は、ちょうど2個だけ奇数次の点があること。

定理 (Fleuryのアルゴリズム): Gはオイラーグラフとする。以下のアルゴリズムは実行可能で、結果としてGのオイラー小道を作る。

  1. たどった辺は除去する。もし孤立点が生じたらそれも除去する。
  2. どの段階でも、他にたどる辺がない場合は橋をたどらない。

証明: まずどの段階でもアルゴリズムが実行可能であることを示す。 点vに到達したと仮定する。v ≠ uならば、残っている部分グラフHは連結でuとvだけ奇数次。次の辺を除去してもHが非連結にならないことを示すことで続行可能と示せる。そうでないと仮定すると、橋vwがあり、H-vwのwを含む成分Kにはuを含まない。点wはKにおいて奇数次なので、Kには他にも奇数次の点があることになり矛盾。v=uの場合も同様。次にオイラー小道が得られることを示す。uに接続している最期の辺が用いられるとき、Gにはたどられていない辺が残っていない。残っていたとすると、これらの辺に隣接している辺で以前にたどられた辺のあるものを除去したとき、そのグラフは非連結になったはずで、矛盾。□

参考

連結性 - グラフ理論入門3

  • グラフGのwalk  v_0 \rightarrow ... \rightarrow v_m v_0, v_mはそれぞれ始点と終点といい、walkの辺の本数が長さである。walkの辺がすべて異なる場合、trailという。さらに点がすべて異なるならpathという。 v_0 = v_mなら閉じているという。
  • グラフの各2点の間に道があるとき、かつそのときに限り、グラフは連結であるという。グラフGの閉路がすべて偶数長であるとき、かつそのときに限り、Gは2部グラフである。
  • 連結グラフGのdisconnecting setとは、それを除去するとGが非連結になる辺の集合。どの真部分集合もdisconnecting setではないようなdisconneccting setをcutsetという。cutsetの辺をすべて除去すれば、成分が2つあるグラフになる。cutsetが1本の辺eであるとき、eはbridgeと呼ぶ。Gが連結である時、Gのedge-connectivity  \lambda(G)とはGの最小なカットセットの大きさのこと。 \lambda(G) \geq kのときk-辺連結という。
  • 連結グラフGのseparating setとは点集合で、それを除去するとGが非連結となるもの。separating setが1個の点vだけのときはそれをcut-vertexという。Gのvertex connectivity  \kappa(G)はGの最小な分離集合の大きさ。
  •  \kappa(G) \leq \lambda(G)

定理: Gが二部グラフであるとき、閉路はすべて偶数長である。

証明: Gは二部グラフなので、点集合を2つの互いに素な点集合AとBに分割できる。Gの各辺はAとBの点を結ぶ。 v_0 \rightarrow ... \rightarrow v_m \rightarrow v_0はGの閉路として、始点 v_0 はAに含まれると仮定できる。このとき、 v_1, v_3, ...はBに含まれ、それ以外はAに含まれる。終点 v_0はAに含まれるので、 v_mはBに含まれ、この閉路の長さは偶数長である。□

単純連結グラフは、閉路がないときに辺数が最も少なく、完全グラフのときに最も多い。

定理: Gはn個の点を持つ単純グラフであるとする。Gにはk個の成分があるとき、Gの辺の本数mは  n-k \leq m \leq \frac{1}{2}(n-k)(n-k+1) を満たす。

証明: Gが空グラフのときは自明。Gができるだけ少ない辺数 m_0を持つなら、Gから任意辺を除去すると成分数が1増えてk+1になり、点数はn、辺数は m_0 -1である。帰納法により、 m_0-1 \geq n-(k+1)なので  m_0 \geq n-kとなり下界が求まる。次に、Gが成分数kのグラフで辺数が一番多いとすると、Gの各成分は完全グラフとできる。2つの成分 C_i, C_jがあり、 |V(C_i)|=n_i, |V(C_j)|=n_j, n_i \geq n_j \gt 1とすると、 C_i n_i+1 C_j n_j-1の点を持つ完全グラフで置き換えると、辺数は  n_i - n_j + 1 > 0だけ増加するので、Gはn-k+1個の点からなる完全グラフ1つとk-1個の孤立点からできているので上界が求まる □

この定理から、 \frac{1}{2}(n-1)(n-2)+1以上の辺があれば連結であることもわかる。

参考

グラフの例 - グラフ理論入門2

  • 空グラフ(null graph): 辺集合が空であるグラフ。
    空グラフ
  • 完全グラフ(complete graph)  K_n 辺の数は  \frac{1}{2}n(n-1)
    完全グラフ
  • 閉路グラフ(cycle graph)  C_n
    閉路グラフ
  • 道グラフ(path graph)  P_n 閉路から1つの辺を除去したもの
    道グラフ
  • 車輪(wheel)  W_n 閉路に点を1つ加えて他のすべての点と結んだもの
    車輪
  • 正則グラフ(regular graph): どの点の次数も同じグラフ。3次正則グラフで有名な例はPetersen graphがある https://en.wikipedia.org/wiki/Petersen_graph
    ピータスングラフ
  • プラトングラフ(Platonic graph): 正多面体の頂点と辺から作られたグラフhttps://link.springer.com/article/10.1007/s40995-018-0646-1
    プラトングラフ
  • 二部グラフ: グラフの点集合をAとBに分割し、Gのすべての辺がAの点とBの点を結ぶようにしたグラフ  K_{r,s}。Aの各点がBの各点とちょうど1本の辺で結ばれているなら完全2部グラフ(complete bipartite graph)という。r+sの点とrsの辺がある。
    完全2部グラフ
  • 単純グラフの補グラフ(complement)  \bar{G} 点集合 V(G)を持ち、2点が隣接するのはGにおけるそれらが隣接していないときかつそのときに限るような単純グラフのこと。https://commons.wikimedia.org/wiki/File:Complement_graph.svg
    補グラフ

参考

グラフとは - グラフ理論入門1

グラフ

  • 図のP,Q,R,S,Tはノードといい、それらを結ぶ線はエッジという。ノードとエッジを合わせてグラフという。エッジに方向がないグラフは無向グラフ、方向があるグラフは有向グラフという。エッジに重みを与える場合、重み付きグラフという。
  • ノードの次数とは、そのノードをつなぐエッジの本数のこと。
  • 2つのグラフがあるとき、片方のグラフで2点がエッジで結ばれるとき、他方のグラフの対応する2点がエッジで結ばれているとき、かつそのときに限り2つのグラフは同じ。
  • 2つの点を複数のエッジで結んでいるときは多重辺(multiple edges)と呼ぶ。1つの点をそれ自身とエッジで結ぶなら、ループと呼ぶ。多重辺やループを含まないグラフを単純グラフ(simple graph)という。
  • 歩道 (walk) はある点から別の点への行き方で、連結した辺の列で表せる。
  • どの点も高々1度しか現れない歩道は道 (path)という。始点と終点が一致する道は閉路(cycle)という。
  • すべての辺あるいはすべての点をちょうど1回ずつ通って始点に戻る歩道を含むグラフをそれぞれオイラーグラフ(Eulerian graph)、ハミルトングラフ(Hamiltonian graph)という。
  • 任意の2点が道で結ばれているグラフは連結グラフ(connected graph)といい、2つ以上のかたまりからなるなら非連結グラフ(disconnected graph)という。
  • 任意の2点の間に道が1本しかない連結グラフを木(tree)という。
  • 交差のない形に書き表せるなら平面的グラフ(planar graph)という。
  • 隣り合ったノードに別の色を塗るとして、何色使う必要があるかという問題を彩色問題という。平面的グラフであれば4色で塗れるが、これを4色定理(four-colour theorem)という。
  • 何人かの女性がそれぞれ何人かの男性を知っているとして、どの女性も知り合いの男性と結婚できる組み合わせを考えるための条件を探すという問題は結婚問題(marriage problem)という。
  • 結婚問題に関連して、グラフにおいて与えられた2点を結ぶ素な道を求める問題がある。
  • Pは工場、Rは市場、エッジは商品が送られるルートとする。各ルートには容量が与えられ、エッジの数字は通過可能な最大容量とする。このときの問題は、工場から市場まで最大でどれだけ送れるかである。

参考