最小全域木

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

同じ重みを持つ最小全域木は複数存在する可能性がある。特に、あるグラフのすべての辺の重みが同じであれば、そのグラフのすべての全域木は最小全域木となる。

各エッジにそれぞれ異なる重みが与えられている場合、最小全域木はただ一つしか存在しません。これは、上記の通信会社の例のように、2つの経路のコストが完全に一致することはまずあり得ない、多くの現実的な状況で当てはまります。このことは、全域森にも同様に当てはまります。

証拠：

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

より一般的に言えば、エッジの重みがすべて異なるわけではない場合、最小全域木における重みの（多重）集合のみが確実に一意であり、それはすべての最小全域木で同じである。^{[ 3 ]}

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

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

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

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

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

同様の議論により、切断線上で最小重みを持つ辺が複数存在する場合、そのような辺はそれぞれ何らかの最小全域木に含まれることになる。

グラフの最小コスト辺eが一意である場合、この辺は任意の最小全域木 (MST) に含まれる。

証明: もしeが MST に含まれていなかった場合、e をMST に追加した後に形成されるサイクル内の (コストの大きい) エッジのいずれかを削除すると、より小さな重みの全域木が得られます。

Tが MST エッジの木である場合、 T を単一の頂点に縮約し ながら、縮約されたグラフとTの MSTが縮約前のグラフの MST を与えるという不変条件を維持することができます。^{[ 4 ]}

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

2つ目のアルゴリズムはプリムのアルゴリズムで、 1930年にヴォイチェフ・ヤルニクによって考案され、 1957年にプリム、1959年にダイクストラによって再発見されました。基本的には、最小全域木 ( T ) を一度に1つのエッジずつ拡張します。最初は、Tには任意の頂点が含まれています。各ステップで、Tには、 xがTに含まれ、yがまだTに含まれていない最小重みのエッジ( x , y )が追加されます。カット特性により、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以下の定数とみなすことができます。したがって、シャゼルのアルゴリズムはほぼ線形時間で実行されます。

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

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

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

• がある$\displaystyle 2^{r \choose 2}}$r個の頂点を持つ異なるグラフ 。
• 各グラフに対して、例えばプリムのアルゴリズムによって、 r ( r − 1) 回の比較を用いて常に MST を見つけることができます。
• したがって、最適なDTの深さはr ²より小さい。
• したがって、最適なDTの内部ノードの数は以下より少ない。$2r²$。
• 各内部ノードは2つのエッジを比較します。エッジの数は最大でr ²なので、比較の異なる回数は最大でr ⁴です。
• したがって、潜在的なDTの数は以下より少ない。

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

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

• このような順列の数は最大で( r ² )!です。
• 各順列について、既存のアルゴリズムを使用して与えられたグラフ上の最小全域木問題を解き、その結果を決定木（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)}}.}$

セス・ペティとビジャヤ・ラマチャンドランは、証明可能な最適性を持つ決定論的比較ベースの最小全域木アルゴリズムを発見した。 ^{[ 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 )の時間で解くことができる。^{[ 14 ] [ 15 ]}

この問題は分散的な方法でも解決できます。各ノードをコンピュータとみなし、各ノードが自身の接続リンク以外の情報は何も知らないと仮定すれば、分散最小全域木を計算することができます。