アルゴリスト

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

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のカットセットで、こうして得られるカットセット全体の集合。

参考