アルゴリスト

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

連結性 - グラフ理論入門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以上の辺があれば連結であることもわかる。

参考