最小全域木

最小全域木( MST ) または最小重み全域木は、連結された辺重み付き無向グラフの辺のサブセットであり、すべての頂点を閉路なしで連結し、辺の重みの合計が可能な限り最小になるようにします。^[1]つまり、辺の重みの合計が可能な限り小さい全域木です。 ^[2]より一般的には、任意の辺重み付き無向グラフ (必ずしも連結されている必要はありません) には、連結コンポーネントの最小全域木の和集合である最小全域木の森が存在します。

最小全域木の使用例は多数あります。1 つの例は、新しい地域にケーブルを敷設しようとしている通信会社です。ケーブルを特定のパス (道路など) に沿ってのみ埋設するという制約がある場合、それらのパスによって接続されたポイント (家屋など) を含むグラフが存在します。パスの中には、長いため、またはケーブルをより深く埋設する必要があるため、より高価なパスもあります。これらのパスは、より大きな重みを持つエッジで表されます。エッジの重みには通貨が許容される単位です。エッジの長さは、三角不等式などの幾何学の通常の規則に従う必要はありません。そのグラフの全域木は、サイクルを持たないがすべての家屋を接続するパスのサブセットになります。複数の全域木が考えられます。最小全域木は、総コストが最も低いものであり、ケーブルを敷設するための最も安価なパスを表します。

グラフにn 個の頂点がある場合、各全域木にはn − 1 個の辺があります。

同じ重みの最小全域木が複数存在する場合があります。特に、特定のグラフのすべてのエッジの重みが同じである場合、そのグラフのすべての全域木は最小になります。

各エッジに異なる重みがある場合、一意の最小全域木は 1 つだけ存在します。これは、上記の通信会社の例など、2 つのパスのコストがまったく同じになる可能性が低い多くの現実的な状況に当てはまります。これは、全域木にも一般化されます。

証拠：

1. 逆に、 2 つの異なる MST AとBがあると仮定します。
2. AとB は同じノードを含んでいるにもかかわらず異なるため、一方に属し、他方には属さないエッジが少なくとも 1 つあります。このようなエッジのうち、重みが最小のものをe _{1とします。エッジの重みがすべて異なるため、この選択は一意です。一般性を失うことなく、} e _{1 が}Aにあると仮定します。
3. BはMSTなので、{ e 1 _} ∪ Bにはe ₁を含むサイクルCが含まれていなければなりません。
4. ツリーとして、Aにはサイクルが含まれていないため、C にはAにないエッジe ₂が存在する必要があります。
5. e _{1 は}、 AとBのどちらか一方に属するエッジの中で重みが最も小さい唯一のエッジとして選択されたため、 e ₂の重みはe ₁の重みよりも大きくなければなりません。
6. e ₁とe _{2 は}サイクルCの一部であるため、Bでe _{2 を}e ₁に置き換えると、重みが小さいスパニング ツリーが生成されます。
7. これは、 Bが MST であるという仮定と矛盾します。

より一般的には、辺の重みがすべて異なるわけではない場合、最小全域木における重みの（多重）集合のみが一意であることが確実であり、これはすべての最小全域木で同じである。^[3]

重みが正の場合、最小全域木は実際にはすべての頂点を接続する最小コストのサブグラフです。これは、サブグラフにサイクルが含まれている場合、そのサイクルに沿ったエッジを削除するとコストが削減され、接続性が維持されるためです。

グラフ内の任意のサイクルCについて、 Cのエッジeの重みがCの他のすべてのエッジの個々の重みよりも大きい場合、このエッジは MST に属することができません。

証明:反対に、 e がMST T ₁に属していると仮定します。 eを削除すると、T _{1 は}eの両端が異なるサブツリーにある 2 つのサブツリーに分割されます。 Cの残りはサブツリーを再接続するため、異なるサブツリーに端があるCのエッジfが存在します。つまり、 fの重みがeの重みより小さいため、サブツリーはT ₁より重みが小さいツリーT ₂に再接続されます。

グラフの任意のカット Cについて、 Cのカットセット内のエッジeの重みがCのカットセットの他のすべてのエッジの重みよりも厳密に小さい場合、このエッジはグラフのすべての MST に属します。

証明: e を含まないMST Tがあると仮定します。e をTに追加すると、 eでカットを一度横切り、別のエッジe'で戻るサイクルが生成されます。e' を削除すると、 Tよりも厳密に小さい重みを持つ全域木T ∖{ e' } ∪ { e }が得られます。これは、 Tが MST であった という仮定と矛盾します。

同様の議論により、カット全体で複数のエッジの重みが最小である場合、そのようなエッジはそれぞれ何らかの最小全域木に含まれます。

グラフの最小コスト エッジeが一意である場合、このエッジは任意の MST に含まれます。

証明: e がMST に含まれていない場合、 e をMST に追加した後に形成されたサイクル内の (コストが大きい) エッジのいずれかを削除すると、重みがより小さいスパニング ツリーが生成されます。

TがMST辺の木である場合、 Tを単一の頂点に縮約することができ、縮約されたグラフのMSTに Tを加えたものが縮約前のグラフのMSTを与えるという不変条件を維持する。^[4]

以下のすべてのアルゴリズムにおいて、mはグラフ内の辺の数、n は頂点の数です。

最小全域木を見つける最初のアルゴリズムは、1926 年にチェコの科学者オタカル・ボルフカによって開発されました (ボルフカのアルゴリズムを参照)。その目的は、モラビアの効率的な電気的被覆でした。アルゴリズムは一連の段階で進行します。ボルフカ ステップと呼ばれる各段階では、グラフGの各頂点に接続する最小重みのエッジで構成されるフォレストF を識別し、次のステップへの入力としてグラフG ₁ = G \ Fを形成します。ここで、 G \ F は、 Fのエッジを縮小することによってGから派生したグラフを表します(カット プロパティにより、これらのエッジは MST に属します)。各ボルフカ ステップには線形時間がかかります。各ステップで頂点の数が少なくとも半分に削減されるため、ボルフカのアルゴリズムにはO ( m log n )時間がかかります。^[4]

2 つ目のアルゴリズムはプリムのアルゴリズムで、 1930 年にVojtěch Jarníkによって発明され、 1957 年にプリム、1959 年にダイクストラによって再発見されました。基本的に、このアルゴリズムは MST ( T ) を 1 度に 1 辺ずつ拡大します。最初、Tには任意の頂点が含まれます。各ステップで、Tは、 x がTに含まれ、yがまだTに含まれていないような最小重みの辺( x、y )で拡張されます。Cut プロパティにより、Tに追加されたすべての辺はMST に含まれます。実行時間は、使用されるデータ構造に応じて、 O ( m log n )またはO ( m + n log n )のいずれかです。

一般的に使用されている3番目のアルゴリズムはクラスカルのアルゴリズムで、これもO ( m log n )の時間がかかります。

4 番目のアルゴリズムは、あまり一般的ではありませんが、クラスカルのアルゴリズムの逆である逆削除アルゴリズムです。実行時間はO( m log n (log log n ) ³ )です。

これら 4 つはすべて貪欲アルゴリズムです。多項式時間で実行されるため、このようなツリーを見つける問題はFPに含まれ、特定のエッジが MST 内にあるかどうかや最小の合計重みが特定の値を超えているかどうかを判断するなどの関連する決定問題はPに含まれます。

何人かの研究者は、より計算効率の高いアルゴリズムを見つけようと試みてきました。

エッジの重みに対する唯一の許可された操作がペアワイズ比較である比較モデルにおいて、Karger、Klein、Tarjan（1995）は、 Borůvkaのアルゴリズムと逆削除アルゴリズムの組み合わせに基づく線形時間ランダム化アルゴリズムを発見しました。^{[5] [6]}

バーナード・シャゼルによる、複雑さがわかっている最速の非ランダム比較アルゴリズムは、近似優先キューであるソフトヒープに基づいています。 ^{[7] [8]}その実行時間はO ( m α( m、n ))で、α はアッカーマン関数の古典的な逆関数です。関数αは非常にゆっくりと増加するため、実用上は 4 以下の定数と見なすことができます。そのため、シャゼルのアルゴリズムは線形時間に近い時間がかかります。

グラフが密な場合（つまり、m / n ≥ log log log n）、 Fredman と Tarjan による決定論的アルゴリズムは、 MST をO( m ) の時間で見つけます。^[9]このアルゴリズムは、いくつかのフェーズを実行します。各フェーズでは、プリムのアルゴリズムを何度も実行し、それぞれ限られた数のステップを実行します。各フェーズの実行時間はO( m + n )です。フェーズ前の頂点数がn'の場合、フェーズ後に残っている頂点の数は最大です。したがって、最大でlog* nフェーズが必要となり、密なグラフでは実行時間が線形になります。^[4]${\displaystyle {\tfrac {n'}{2^{m/n'}}}}$

密なグラフ上で線形時間で動作する他のアルゴリズムも存在する。^{[7] [10]}

辺の重みが2進数で表された整数である場合、O ( m + n )回の整数演算で問題を解決する決定論的アルゴリズムが知られています。^[11]一般的なグラフに対して、比較ベースのアルゴリズムによって線形時間で決定論的に 問題を解決できるかどうかは未解決の問題です。

ノードとエッジは固定されているが重みが不明なグラフGが与えられた場合、任意の重みの組み合わせに対する MST を計算するためのバイナリ決定木(DT) を構築することができます。 DT の各内部ノードには、2 つのエッジの比較 (例: 「 xとyの間のエッジの重みは、 wとzの間のエッジの重みより大きいか?」) が含まれます。ノードの 2 つの子は、2 つの可能な回答「はい」または「いいえ」に対応します。 DT の各リーフには、 Gからのエッジのリストがあり、それらは MST に対応します。 DT の実行時の複雑さは、 MST を見つけるために必要なクエリの最大数であり、これは DT の深さに相当します。グラフGの DT は、 Gのすべての正しい DT の中で深さが最小である場合に最適と呼ばれます。

すべての整数rに対して、総当たり探索によってr頂点上のすべてのグラフの最適な決定木を見つけることができます。この探索は 2 つのステップで進行します。

A. 潜在的なDTをすべて生成する

• r頂点にはさまざまなグラフ が存在します。${\displaystyle 2^{r \choose 2}}$
• 各グラフについて、MSTは常にr ( r -1)回の比較（例えばPrimのアルゴリズム）によって見つけることができます。
• したがって、最適な DT の深さはr ²未満になります。
• したがって、最適な DT 内の内部ノードの数は 未満になります。${\displaystyle 2^{r^{2}}}$
• すべての内部ノードは 2 つのエッジを比較します。エッジの数は最大r ²なので、比較の異なる数は最大r ⁴です。
• したがって、潜在的なDTの数は

${\displaystyle {(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}.}$

B. 正しい DT の識別 DT が正しいかどうかを確認するには、エッジの重みのすべての可能な順列をチェックする必要があります。

• このような順列の数は最大で( r ² )!です。
• 各順列について、既存のアルゴリズムを使用して指定されたグラフ上の MST 問題を解決し、その結果を DT によって与えられた答えと比較します。
• あらゆる MST アルゴリズムの実行時間は最大でr ²なので、すべての順列をチェックするために必要な合計時間は最大で( r ² + 1)!です。

したがって、 r頂点を持つすべてのグラフに対して最適なDTを見つけるために必要な合計時間は次のとおりです。^[4]

${\displaystyle 2^{r \choose 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!,}$

これは以下です

${\displaystyle 2^{2^{r^{2}+o(r)}}.}$

Seth PettieとVijaya Ramachandranは、証明可能な最適な決定論的比較ベースの最小全域木アルゴリズムを発見しました。^[4]以下は、アルゴリズムの簡略化された説明です。

1. r = log log log nとします。ここでnは頂点の数です。r 頂点上のすべての最適な決定木を見つけます。これはO ( n ) の時間で実行できます(上記の決定木を参照)。
2. グラフを、各コンポーネントに最大r個の頂点を持つコンポーネントに分割します。この分割ではソフト ヒープが使用され、グラフの少数のエッジが「破損」します。
3. 最適な決定木を使用して、各コンポーネント内の破損していないサブグラフの MST を見つけます。
4. MSTによって張られた各連結成分を単一の頂点に縮小し、密なグラフに対して時間O ( m )で動作する任意のアルゴリズムを破損していないサブグラフの縮小に適用する。
5. 破損したエッジを結果として得られるフォレストに追加し直して、最小全域木を含むことが保証され、開始グラフよりも定数倍小さいサブグラフを形成します。このグラフに最適なアルゴリズムを再帰的に適用します。

アルゴリズムのすべてのステップの実行時間は、決定木を使用するステップを除いてO ( m )です。このステップの実行時間は不明ですが、最適であることが証明されています。最適な決定木よりも優れたアルゴリズムはありません。したがって、このアルゴリズムは、実行時間の複雑さが不明であるにもかかわらず、最適であることが証明できるという独特の特性を持っています。

研究では、最小全域木問題に対する並列アルゴリズムも検討されている。プロセッサの数が線形であれば、 O (log n )時間で問題を解くことが可能である。 ^{[12] [13]}

この問題には分散方式で取り組むこともできます。各ノードをコンピューターと見なし、どのノードも自身の接続リンク以外は何も知らない場合でも、分散最小全域木を計算することができます。

アラン・M・フリーズは、 n頂点の完全グラフで、辺の重みがを満たす分布関数を持つ独立した同一分布のランダム変数である場合、 n が+∞に近づくにつれてMST の期待重みが に近づくことを示した。ここで はリーマンのゼータ関数(より正確にはアペリの定数)である。フリーズとスティールは確率の収束も証明した。スヴァンテ・ヤンソンはMST の重みの 中心極限定理を証明した。${\displaystyle F}$${\displaystyle F'(0)>0}$${\displaystyle \zeta (3)/F'(0)}$${\displaystyle \zeta}$${\displaystyle \zeta (3)}$

における一様ランダム重みについて、小さな完全グラフの最小全域木の正確な期待サイズが計算されている。^[14]${\displaystyle [0,1]}$

MST には分数変種があり、各辺が「分数的に」現れることが許されます。正式には、グラフ (V,E) の分数全域集合は、 E上の非負関数fであり、 Vのすべての非自明な部分集合W (つまり、W は空でもVと等しくもありません) について、 WのノードとV \ Wのノードを接続するすべての辺にわたるf ( e )の合計が少なくとも 1 になります。直感的には、f ( e ) は、全域集合に含まれる e の割合を表します。最小分数全域集合は、合計が可能な限り小さい 分数全域集合です。${\displaystyle \sum _{e\in E}f(e)\cdot w(e)}$

分数f ( e ) が {0,1} の範囲内にあるように強制されると、f(e)=1 であるエッジの集合T は全域集合になります。これは、すべてのノードまたはノードのサブセットが、 Tの少なくとも 1 つのエッジによってグラフの残りの部分に接続されているためです。さらに、f がを最小化する場合、結果として得られる全域集合は必然的に木になります。これは、全域集合にサイクルが含まれていれば、全域集合条件に影響を与えずにエッジを削除できるためです。したがって、最小分数全域集合問題は MST 問題の緩和であり、分数 MST 問題とも呼ばれます。${\displaystyle \sum _{e\in E}f(e)\cdot w(e)}$

分数 MST 問題は、楕円体法を使用して多項式時間で解くことができます。^{[15] : 248}ただし、 f ( e ) が半整数でなければならないという要件を追加すると(つまり、f ( e ) が {0, 1/2, 1} の範囲内にある必要がある)、問題はNP 困難になります。^{[15] : 248}これは、ハミルトン閉路問題が特殊なケースとして含まれるためです。頂点の重みなしグラフでは、重みの半整数 MST は、ハミルトン閉路の各辺に重み 1/2 を割り当てることによってのみ取得できます。 ${\displaystyle n}$${\displaystyle n/2}$

• 頂点のサブセットのシュタイナー木は、与えられたサブセットを覆う最小の木である。シュタイナー木を見つけることはNP完全である。^[16]

• k最小全域木( k -MST)は、グラフ内のk個の頂点のサブセットを最小の重みで網羅する木です。
• k最小全域木集合は、 k全域木（すべての可能な全域木のうち）の部分集合であり、その部分集合の外側の全域木はこれより重みが小さくならない。 ^{[17] [18] [19] （この問題は}k最小全域木 とは無関係であることに注意してください。）
• ユークリッド最小全域木は、平面 (または空間) 上の点である頂点間のユークリッド距離に対応する辺の重みを持つグラフの全域木です。
• 直線最小全域木は、平面 (または空間) 内の点である頂点間の直線距離に対応する辺の重みを持つグラフの全域木です。
• 分散型最小全域木は、分散型モデルへの MST の拡張であり、各ノードはコンピューターと見なされ、どのノードも自身の接続リンク以外は何も知りません。問題の数学的定義は同じですが、解決にはさまざまなアプローチがあります。
• 容量付き最小全域木は、マークされたノード（起点またはルート）を持ち、ノードに接続された各サブツリーにはc個以下のノードが含まれる木です。cは木容量と呼ばれます。CMSTを最適に解くことはNP困難ですが、^[20] Esau-WilliamsやSharmaなどの優れたヒューリスティックスは、多項式時間で最適に近い解を生成します。
• 次数制約付き最小全域木は、与えられた数dに対して、各頂点が最大d個の他の頂点と接続される MST です。d = 2の場合は巡回セールスマン問題 の特殊なケースであるため、次数制約付き最小全域木は一般にNP 困難です。
• 樹状突起は有向グラフの MST の変形であり、 Chu–Liu/Edmonds アルゴリズムを使用して時間内に解くことができます。${\displaystyle O(E+V\log V)}$
• 最大全域木は、他のすべての全域木の重み以上の重みを持つ全域木です。このような木は、エッジの重みを-1倍し、新しいグラフでMST問題を解いた後、プリムやクラスカルなどのアルゴリズムを使用して見つけることができます。最大全域木内のパスは、グラフの2つのエンドポイント間の最も広いパスです。つまり、すべての可能なパスの中で、最小重みのエッジの重みを最大化します。^{[21]最大全域木は、}自然言語の構文解析アルゴリズム^[22]や条件付きランダムフィールドのトレーニングアルゴリズムに応用されています。
• 動的MST問題は、元のグラフの辺の重みの変更や頂点の挿入/削除後に、以前に計算されたMSTを更新する問題である。^{[23] [24] [25]}
• 最小ラベル付け全域木問題とは、グラフ内の各辺が重みではなく有限のラベルセットのラベルに関連付けられている場合に、ラベルの種類が最も少ない全域木を見つけることである。^[26]
• ボトルネックエッジは、全域木の中で最も重みの大きいエッジである。グラフにボトルネックエッジの重みがより小さい全域木が含まれていない場合、全域木は最小ボトルネック全域木（またはMBST）である。MSTは必ずMBSTである（カットプロパティによって証明可能）が、MBSTは必ずしもMSTであるわけではない。^{[27] [28]}
• 最小コスト スパニング ツリー ゲームは、最適なスパニング ツリーを構築するためのコストをプレイヤー間で分担する必要がある協力ゲームです。
• 最適ネットワーク設計問題とは、予算制約の下で、すべてのノード ペア間の最短経路の合計が可能な限り小さくなるように、スパニング ツリーを含むセットを計算する問題です。

最小全域木は、コンピュータネットワーク、電気通信ネットワーク、交通ネットワーク、水道ネットワーク、電力網（前述のように、最初に発明されたのは電力網）などのネットワーク設計に直接応用されています。^[29]最小全域木は、巡回セールスマン問題[ ^30]の近似、多端子最小カット問題（単一端子の場合は最大フロー問題に相当）^[31]の近似 、最小コスト重み付き完全マッチング^[32]の近似など、他の問題のアルゴリズムでサブルーチンとして呼び出されます。

最小全域木に基づくその他の実用的なアプリケーションには次のものがあります。

• 分類学[ ^33]
• クラスター分析：平面上の点のクラスタリング、^[34] 単一リンククラスタリング（階層的クラスタリング法）、^[35]グラフ理論的クラスタリング、^[36]遺伝子発現データのクラスタリング。^[37]
• コンピュータネットワークにおけるブロードキャスト用のツリーの構築。^[38]
• 画像登録^[39]とセグメンテーション^[40] –最小全域木ベースのセグメンテーションを参照。
• コンピュータビジョンにおける曲線特徴抽出^[41]
• 数式の手書き認識。 ^[42]
• 回路設計：有限インパルス応答フィルタで使用される効率的な複数の定数乗算を実装する。 ^[43]
• 社会地理学的地域の地域化、均質で連続した地域への地域のグループ化。^[44]
• 生態毒性データの比較^[45]
• 電力システムにおける位相的観測可能性^[46]
• 二次元材料の均質性の測定^[47]
• ミニマックスプロセス制御[ ^48]
• 最小全域木は金融市場を説明するためにも使用できます。^{[49] [50]}相関行列は、任意の2つの株式間の相関係数を計算することによって作成できます。この行列は複雑なネットワークとして位相的に表現でき、最小全域木を構築して関係を視覚化できます。

• Otakar Boruvka による最小全域木問題 (1926 年の 2 つの論文の翻訳、コメント、履歴) (2000) Jaroslav Nešetřil、Eva Milková、Helena Nesetrilová。 (第 7 節では、Prim と Kruskal を組み合わせたような彼のアルゴリズムが紹介されています。)
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第 2 版。MIT Pressおよび McGraw-Hill、2001 年。ISBN 0-262-03293-7。第 23 章: 最小全域木、pp. 561–579。 
• Eisner, Jason (1997)。「最小全域木のための最新アルゴリズム: チュートリアルディスカッション」原稿、ペンシルバニア大学、4 月。78 ページ。
• Kromkowski, John David. 「Still Unmelted after All These Years」、Annual Editions、Race and Ethnic Relations、17/e (2009 McGraw Hill) (米国全土の民族的多様性の人口統計分析方法として最小全域木を使用)。

ウィキメディア・コモンズには、最小全域木に関連するメディアがあります。

• BGLで実装されたBoost Graph Library
• ストーニーブルックアルゴリズムリポジトリ - 最小全域木コード
• QuickGraph for .Net に実装