📂グラフ理論

グラフの集合表記

定義 ¹

二つのグラフ $G_{1}$ と $G_{2}$ に対して $V(G_{1}) \cap V(G_{2}) = \emptyset$ としよう。

1. 二つのグラフの ユニオン^union $G = G_{1} \cup G_{2}$ は、頂点セット $V(G_{1}) \cup V(G_{2})$ とエッジセット $E (G_{1}) \cup E ( G_{2} )$ を持つグラフだ。
2. グラフ $H$ が他のグラフのユニオンで表されない場合、$H$ を 接続されている^connectedといい、それ以外の場合は 切断されている^disconnectedという。
3. 切断されたグラフを構成する各 接続グラフ^{connected graph}を コンポーネント^componentと呼ぶ。
4. 特にエッジ $b \in G$ の削除によりグラフが切断される場合、$b$ を ブリッジ^bridgeと呼ぶ。

説明

これらの定義は位相数学で接続性を定義する方法とよく似ている。

純粋なグラフの定義からの 接続性^{connectedness}は重要な話のように見えるが、皮肉なことに、切断されたコンポーネントは完全に個別に扱うことができるので、接続されたグラフだけを考えれば十分だ。接続性が重要でないわけではなく、通常は研究のために切断されたケースを考える必要はないということだ。

接続性が注目されるのは、実際のデータを反映した分析やランダムネットワークを扱う適用ネットワーク理論でよくある。ランダムネットワークが確かに接続グラフになるかどうかは、様々なシミュレーションなどでかなり重要な問題だ。ネットワークの接続性が保証されていない場合を考えよう。孤立ノード^{isolated Node}は、ほとんどの数学モデルでは影響力がなく、孤立ノードがなくても、ネットワークの一部だけを考慮して残りを捨てなければならない大惨事が起こる可能性がある。

定理 ²

シンプルグラフ $G$ が $n$ 個の頂点を持っているとする。$G$ が $k$ 個のコンポーネントを持っている場合、$G$ のエッジの数 $m$ は次を満たす。 $$n-k \le m \le (n-k)(n-k+1)/2$$

証明

Part 1. $n-k \le m$

$G$ がヌルグラフの場合、$n=k$ であり、$m=0$ であるため、$n-k = 0 \le 0 = m$ が成立する。

$G$ のコンポーネントが $k$ 個ある場合に $n - k \ge m$ が成立すると仮定しよう。$G$ が $k$ 個のコンポーネントを持つための最少のエッジ数を $m_{0}$ とする。ここで一つのエッジを削除すると、コンポーネントの数は $k+1$ 、エッジの数は $m_{0}-1$ となる。したがって、$n - (k + 1) \le m_{0} - 1$ であり、整理して $n - k \le m_{0}$ を得る。

これら二つの事実から、数学的帰納法により $n-k \le m$ が一般的に成立するという結論になる。

---

Part 2. $m \le (n-k)(n-k+1)/2$

$G$ のすべてのコンポーネントが完全グラフであるとしよう。すると、$1 \le j \le i \le n$ である二つの完全グラフ $K_{i}$、$K_{j}$ が存在するだろう。これら二つのグラフをそれぞれ $K_{i+1}$、$K_{j-1}$ に変えると、頂点の総数は変わらないが、エッジの総数は次のように変わる。 $$\left[ (i+1)i - i(i-1) \right]/2 - \left[ j(j-1) - (j-1)(j-2) \right]/2 = i - j + 1$$ これは正の数で、したがって、$m$ が最大化されるためには、$G$ は頂点の数が $(n-k+1)$ 個の完全グラフと、孤立頂点 $k-1$ 個を持たなければならない。この場合、$G$ のエッジの数は $(n-k)(n-(k-1))/2$ であり、求めていた結果を得る。

■