期待される線形時間MSTアルゴリズム

アルゴリズムの各反復は、ボルフカのアルゴリズムを改良したもので、ボルフカステップと呼ばれる。

入力：孤立頂点を持たないグラフG 1 各頂点vに対して、 vに接続する最も軽いエッジを選択します。 2ステップ 1 で選択したエッジで接続されているGの各コンポーネントを単一の頂点に置き換えることにより、 縮約グラフG'を作成します。3. G' から孤立頂点、自己ループ、非最小反復エッジをすべて削除します 。出力：ステップ1で選択されたエッジと縮約されたグラフG'

ボルフカのステップは、ボルフカのアルゴリズムの内側のループに相当し、Gのエッジ数をmとすると、 O ( m ) の時間で実行されます。さらに、各エッジは最大で 2 回 (各接続頂点によって 1 回ずつ) 選択できるため、ステップ 1 後の切断されたコンポーネントの最大数は、頂点数の半分になります。したがって、ボルフカのステップでは、グラフの頂点数が少なくとも 2 分の 1 に減り、Gの頂点数をnとすると、少なくともn /2 個のエッジが削除されます。

Borůvka ステップの実行例

各反復において、アルゴリズムは最小全域木から除外される特定の特性を持つエッジを削除します。これらはF-heavy エッジと呼ばれ、次のように定義されます。グラフH上の森をFとします。F-heavy エッジとは、頂点uとvを接続するエッジeで、その重みがF内のuからvへのパス上の最も重いエッジの重みよりも厳密に大きいものです。(パスがFに存在しない場合は、その重みは無限大とみなされます)。F-heavy でないエッジはすべてF-lightです。FがGの部分グラフである場合、サイクル特性により、G内の F-heavy エッジはGの最小全域木には含まれません。森が与えられた場合、F-heavy エッジは最小全域木検証アルゴリズムを使用して線形時間で計算できます。 ^{[ 2 ] [ 3 ]}

補題- Gの各辺を確率pで独立に含めて形成されたGの部分グラフをHとし、Hの最小全域森をFとする。GにおけるF-light辺の期待値は、 nをGの頂点数としたとき、最大でn/pである。

補題を証明するために、GのエッジがHに追加されるとき、それらを調べます。GのF-lightエッジの数は、Hのエッジが選択される順序に依存しません。これは、 Hの最小全域森がすべての選択順序で同じであるためです。証明のために、G のエッジを、エッジの重みが最も軽いものから最も重いものへと順に 1 つずつ選択して、H のエッジを選択することを考えます。e を現在考慮されているエッジとします。e の端点がHの 2 つの非連結成分にある場合、eはそれらの成分を接続する最も軽いエッジであり、 Hに追加されると、カット特性によりFになります。これは、 e がHに追加されるかどうかに関係なく、eがF-lightであることも意味します。これは、その後、より重いエッジのみが考慮されるためです。e の両端点がHの同じ成分にある場合、サイクル特性により、 e は (常に) F-heavy になります。エッジeは、確率pでH に追加されます。

Hに追加できるF-lightエッジの最大数はn -1です。これは、Hの最小全域木にはn -1 個のエッジがあるためです。H にn -1 個の F-light エッジが追加されると、サイクル特性により、後続のエッジは F-light ではなくなります。したがって、 Gの F-light エッジの数は、n -1 個の F-light エッジが実際にHに追加される前にHに対して考慮された F-light エッジの数によって制限されます。任意の F-light エッジは確率pで追加されるため、これは、 n -1 回表が出るまで確率pでコインを投げることに相当します。コイン投げの総数は、Gの F-light エッジの数に等しくなります。コイン投げの回数の分布は、パラメータn -1 とpを持つ逆二項分布で与えられます。これらのパラメータの場合、この分布の期待値は ( n -1)/ pです。

再帰的な部分問題で行われる作業を無視すると、アルゴリズムの 1 回の実行で行われる作業の総量は、入力グラフのエッジ数に比例します。ステップ 1 は定数時間で実行されます。Borůvka ステップは、 Borůvka ステップのセクションで述べたように、エッジ数に比例する時間で実行できます。ステップ 3 はエッジを反復処理し、各エッジに対して 1 枚のコインを投げるため、エッジ数に比例します。ステップ 4 は、修正された線形時間最小全域木検証アルゴリズムを使用して線形時間で実行できます。^{[ 2 ] [ 3 ]} アルゴリズムの 1 回の実行で行われる作業はエッジ数に比例するため、アルゴリズムの 1 回の完全な実行 (すべての再帰呼び出しを含む) で行われる作業は、元の問題とすべての再帰的な部分問題のエッジの総数に定数倍を掛けたものに制限されます。

アルゴリズムを1回呼び出すごとに最大2つの部分問題が生成されるため、部分問題の集合は二分木を形成します。Borůvkaステップ1回で頂点の数は少なくとも2分の1に減少するため、2回のBorůvkaステップ後には頂点の数は4分の1に減少します。したがって、元のグラフがn個の頂点とm個のエッジを持つ場合、木の深さdでは、各部分問題は最大でn /4d^個の頂点を持つグラフ上に存在します。また、この木は最大でlog4n_個のレベルを持ちます。

再帰ツリーについて考察するために、ステップ 3 の再帰呼び出しにおけるサブ問題を左の子の問題とし、ステップ 5 の再帰呼び出しにおけるサブ問題を右の子の問題とします。ツリーの各左パスのエッジ数を数えることで、元の問題とすべてのサブ問題におけるエッジの総数を数えます。左パスは右の子またはルートから始まり、左の子のパスで到達可能なすべてのノードを含みます。二分木の左パスは、右の図で青色の丸で囲まれています。

左子問題の各エッジは、親問題のエッジ（Borůvkaステップで縮約されたエッジを除く）から確率1/2で選択されます。親問題にx個のエッジがある場合、左子問題のエッジの期待値は最大でx /2です。xをランダム変数Xに置き換えると、期待値の線形性により、左子問題Yのエッジの期待値は次のように与えられます。${\displaystyle E[Y]\leq E[X]/2}$したがって、左パスの先頭にある問題の期待エッジ数がkである場合、左パスの各部分問題の期待エッジ数の合計は最大で$\sum_{d=0}^{\infty}{\frac{k}{2^{d}}}=2k}$（等比数列を参照）。根にはm個の辺があるので、期待される辺の数は、 2mに各右部分問題の期待される辺の数の2倍を加えた数に等しくなります。

各右部分問題における期待されるエッジ数は、左部分問題の最小全域木をFとしたときの親問題におけるF-フライトエッジの数に等しい。サンプリング補題により、F-フライトエッジの数は部分問題の頂点数の 2 倍以下である。深さdの部分問題の頂点数はn /4 ^dなので、すべての右部分問題における頂点の総数は次式で与えられる。${\displaystyle \sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2}$したがって、元の問題とすべての部分問題におけるエッジの期待値は最大で 2 m + nです。孤立頂点のないグラフの場合、 n は最大で 2 mなので、アルゴリズムは期待時間O ( m ) で実行されます。

最悪の場合の実行時間は、Borůvka のアルゴリズムの実行時間と同等です。これは、すべてのエッジが各呼び出しで左または右のサブ問題に追加される場合に発生します。この場合、アルゴリズムはBorůvka のアルゴリズムと同一であり、 n個の頂点とm個のエッジを持つグラフではO (min{ n ² , m log n })で実行されます。