12.10 \(k\)-辺連結グラフ

電話網、原油パイプライン、送電線ネットワークなどをモデル化するグラフには単なる連結性だけではなく構成要素の障害に耐える連結性が求められる。連結性の強さを示す指標の一つとして「いくつの辺を消去すると連結性が失われるか」がある。二つの頂点が \(k\)-辺接続 (\(k\)-edge connected) とは、それらを切り離すために最低で \(k\) 個の「辺障害」が必要なことを意味する。より正確に言えば:

以降では「\(k\)-辺接続」および「\(k\)-辺連結」を省略して「\(k\)-接続」および「\(k\)-連結」と書く¹。

例えば、図 \(\text{12.4}\) のグラフで頂点 \(c\) と \(e\) は \(3\)-接続、\(b\) と \(e\) は \(2\)-接続、\(g\) と \(e\) は \(1\)-接続であり、\(4\)-接続な頂点は存在しない。そのためグラフ全体は \(1\)-連結でしかない。また、完全グラフ \(K_{n}\) は \((n - 1)\)-連結であり、閉路グラフ \(C_{n}\) は \(2\)-連結である。

通常の接続性 (定義 12.8.1) は \(1\)-接続性と同値である。\(2\)-接続性はカット辺 (cut edge) の概念を使うと簡潔に説明できる:

この定義から、\(2\) 個以上の頂点を持つグラフでは「\(2\)-接続」と「カット辺を持たない」が同値だと分かる。次の補題も定義から直ちに分かる:

証明 辺 \(e\) を含む閉路が存在するなら、\(e\) は明らかにカット辺でない。逆に、もし辺 \(e\) がカット辺でないなら、\(e\) を除去したグラフに \(e\) の端点を結ぶ路が存在する。その歩道に \(e\) を加えれば閉路が得られる。 ■

より一般的に言えば、もし二つの頂点間に辺素な ── 辺を共有しない ── \(k\) 個の路が存在するなら、その二頂点は \(k\)-接続である: 二頂点を切り離すには、少なくとも \(k\) 個の路から \(1\) 個ずつ辺を除去する必要がある。なお、この逆も成り立つことが知られている。つまり、二つの頂点が \(k\)-接続なら、その二頂点を結ぶ辺素な \(k\) 個の路が存在する。これは Mengerメンガー の定理 (Menger's theorem) と呼ばれるグラフ理論における基礎的な結果である。その高度な証明は本書では省略する。\(k = 2\) の場合に対する証明でさえ簡単ではない。