グラフ理論の基礎：スパニングツリー・連結性・距離をわかりやすく解説

スパニングツリー（全域木）とは

木（ツリー）とは、閉路（サイクル）を含まない連結グラフのことです。ここでいう閉路とは、同じ辺を2度使わずに、あるノードから出発して再びそのノード自身へ戻ってこられる経路を指します。

連結グラフGに対するスパニングツリー（全域木）とは、Gのすべての頂点を含む木として定義されます。

スパニングツリーは、インターネットのルーティングアルゴリズムなどで広く実装されています。インターネット上では、コンピュータ（ノード）同士が多数の冗長な物理回線で接続されていることが多く、スパニングツリーを構築することでループのない効率的な経路を実現できます。

グラフに含まれるスパニングツリーの総数についても見てみましょう。n個の頂点を持つ完全グラフの場合、スパニングツリーの総数はケイリーの公式（Cayley's Formula）により nⁿ⁻² 個と求められます。ここで n はグラフ内のノード数を表します。つまり完全グラフの場合、この問題は「n個のノードを持つ異なるラベル付き木を数える」ことと等価になります。

連結性（Connectivity）

数学およびコンピュータサイエンスにおいて、連結性はグラフ理論における最も基本的な概念の一つです。

連結性とは、残りのノードを互いに孤立した部分グラフへ分断するために取り除く必要のある要素（ノードまたは辺）の最小数を表します。

この概念は、ネットワークフロー問題の理論とも密接に関連しています。

上図のグラフは、破線で示された辺を取り除くと非連結になります。

頂点連結度（Vertex Connectivity）：グラフを非連結にするために削除が必要なノードの最小数を指します。「点連結度」あるいは単に「連結度」と呼ばれることもあります。

辺連結度（Edge Connectivity）：グラフから削除することで非連結となる辺の最小数を指し、「線連結度」とも呼ばれます。

なお、非連結グラフの辺連結度は0であり、橋（ブリッジ）と呼ばれる辺を持つ連結グラフの辺連結度は1となります。

距離（Distance）

二つのノード間の距離は、最小共通祖先（LCA: Lowest Common Ancestor）を用いて計算できます。以下の式を使用します。

Dist(d1, d2) = Dist(root, d1) + Dist(root, d2) − 2×Dist(root, lca)
'd1' と 'd2'：与えられた2つのキー
'root'：与えられた二分木の根
'lca'：d1 と d2 の最小共通祖先
Dist(d1, d2)：d1 と d2 の間の距離