連結性 - グラフ理論入門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個の孤立点からできているので上界が求まる □