最小全域木

グラフ理論において、最小全域木（MST）または最小重み全域木とは、連結された辺重み付き無向グラフの辺のサブセットであり、サイクルがなく、かつ可能な最小の辺重みで全ての頂点を連結するものである。 ^[¹^]つまり、辺重みの合計が可能な限り小さい全域木である。 ^[²^]より一般的には、任意の辺重み付き無向グラフ（必ずしも連結されているとは限らない）には、連結成分の最小全域木の和集合である最小全域森が存在する。

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

物件

多重性の可能性

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

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

独自性

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

証拠：

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

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

最小コスト部分グラフ

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

サイクルプロパティ

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

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

カットプロパティ

この図は、MST のカット特性を示しています。T $は$ 、与えられたグラフの唯一の MST です。S = { A , B , D , E } の場合 $、 V - S = {C, F}$ となり $、カット (S, V - S$ $) を横切るエッジには 3$ つの可能性があり、それらは元のグラフのエッジ $BC$ 、 $EC$ 、 $EF$ です。e はカットの最小重みエッジの 1 つであるため、 $S \cup {e}$ は MST $T$ の一部となります。

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

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

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

最小コスト優位性

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

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

収縮

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

アルゴリズム

以下のすべてのアルゴリズムにおいて、 $m$ はグラフのエッジの数、 $n$ は頂点の数を表します。

古典的なアルゴリズム

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

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) 3)$ です。

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

より高速なアルゴリズム

複数の研究者が、より計算効率の良いアルゴリズムを見つけようと試みてきた。

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

既知の複雑度を持つ最速の非ランダム化比較ベースアルゴリズムは、ベルナール・シャゼルによるもので、近似優先度キューであるソフトヒープに基づいています。 ^{[ 7 ]}^{[ 8 ]}その実行時間は $O (mα (m, n))$ で、 $αは$ アッカーマン関数の古典的な関数逆です。関数 $α$ は非常にゆっくりと増加するため、実際的な目的においては4以下の定数とみなすことができます。したがって、シャゼルのアルゴリズムはほぼ線形時間で実行されます。

特殊な場合における線形時間アルゴリズム

密なグラフ

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

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

整数値の重み

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

平面グラフ

平面グラフの問題を線形時間で解く決定論的アルゴリズムが知られています。^{[ 12 ]}^{[ 13 ]}平面グラフのオイラー特性により、 $m \leq 3n - 6 \in O (n)なので、これは$ $O (n)$ の時間で行われます。

決定木

ノードとエッジは固定されているが重みが不明なグラフ $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 2$ より小さい。
したがって、最適なDTの内部ノードの数は以下より少ない。 $2r²$ 。
各内部ノードは2つのエッジを比較します。エッジの数は最大で $r 2$ なので、比較の異なる回数は最大で $r 4$ です。
したがって、潜在的なDTの数は以下より少ない。

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

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

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

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

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

これは以下より小さい

2^{2^{r^{2}+o(r)}}.

最適なアルゴリズム

セス・ペティとビジャヤ・ラマチャンドランは、証明可能な最適性を持つ決定論的比較ベースの最小全域木アルゴリズムを発見した。 ^{[ 4 ]}以下は、そのアルゴリズムの簡略化された説明である。

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

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

並列分散アルゴリズム

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

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

ランダムな重みを持つ完全グラフ上の最小全域木

アラン・M・フリーズは、 n個の頂点を持つ完全グラフにおいて、エッジの重みが独立同分布の確率変数であり、分布関数が $F$ 満足 $F'(0)>0$ そしてnが+∞に近づくとMSTの期待重みは $\zeta (3)/F'(0)$ 、どこ $\zeta$ はリーマンゼータ関数（より具体的には $\displaystyle \zeta (3)$ アペリー定数）。フリーズとスティールは確率収束も証明した。スヴァンテ・ヤンソンはMSTの重みに関する中心極限定理を証明した。

一様乱数重みの場合 $[0,1]$ 小さな完全グラフの場合、最小全域木の正確な期待サイズが計算されている。^{[ 16 ]}

分数変異

MSTには分数版があり、各エッジが「分数的に」出現することが許容されます。形式的には、グラフ(V,E)の分数全域集合とは、 E上の非負関数fであり、 Vの任意の非自明な部分集合W（つまり、Wは空集合でもVと等しくもない）に対して、 WのノードとV \ Wのノードを結ぶすべてのエッジに関するf ( e )の合計が少なくとも1であるものです。直感的には、f ( e )は全域集合に含まれるeの割合を表します。最小分数全域集合とは、合計が1以上である分数全域集合のことです。 $\sum _{e\in E}f(e)\cdot w(e)$ できるだけ小さい。

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

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

その他のバリエーション

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

アプリケーション

最小全域木は、コンピュータネットワーク、電気通信ネットワーク、輸送ネットワーク、給水ネットワーク、電力網（前述のように、最初に考案されたのは電力網）などのネットワークの設計に直接応用されています。^{[ 33 ]}また、巡回セールスマン問題を近似するChristofides アルゴリズム^[³⁴^]、多端子最小カット問題（単端子の場合は最大フロー問題と同等）を近似するアルゴリズム^[³⁵^] 、最小コスト加重完全マッチングを近似するアルゴリズム^[³⁶^]など、他の問題のアルゴリズムのサブルーチンとして呼び出されます。

最小全域木に基づくその他の実用的な応用例としては、以下のようなものがある。

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

参考文献

↑ "scipy.sparse.csgraph.minimum_spanning_tree - SciPy v1.7.1 マニュアル"。Numpy および Scipy ドキュメント — Numpy および Scipy ドキュメント。2021-12-10に取得。最小全域木は、接続されているすべてのノードを接続するエッジのサブセットで構成され、エッジの重みの合計を最小化するグラフです。
↑ "networkx.algorithms.tree.mst.minimum_spanning_edges" . NetworkX 2.6.2 ドキュメント. 2021-12-13取得.最小全域木は、エッジの重みの合計が最小となるグラフ（木）の部分グラフです。全域森は、グラフの各連結成分の全域木の和集合です。
↑ 「重み付きグラフの最小全域木は、与えられた重みで同じ数のエッジを持つか？」 . cs.stackexchange.com . 2018年4月4日取得。
1 2 3 4 5 Pettie, Seth; Ramachandran, Vijaya (2002)、「最適な最小全域木アルゴリズム」(PDF)、Journal of the Association for Computing Machinery、49 (1): 16–34、doi : 10.1145/505241.505243、MR 2148431、S2CID 5362916 。
↑ Karger, David R. ; Klein, Philip N. ; Tarjan, Robert E. (1995), "最小全域木を見つけるためのランダム化線形時間アルゴリズム", Journal of the Association for Computing Machinery , 42 (2): 321– 328, doi : 10.1145/201019.201022 , MR 1409738 , S2CID 832583
↑ Pettie, Seth; Ramachandran, Vijaya (2002)、「最小全域木、並列接続性、および集合最大値アルゴリズムにおけるランダム性の最小化」、第13回ACM-SIAM離散アルゴリズムシンポジウム（SODA '02）論文集、カリフォルニア州サンフランシスコ、713–722ページ、ISBN 978-0-89871-513-2{{citation}}: CS1 maint: 場所の発行元が見つかりません (リンク)。
1 2 Chazelle, Bernard (2000)、「逆アッカーマン型複雑度を持つ最小全域木アルゴリズム」、Journal of the Association for Computing Machinery、47 (6): 1028–1047、doi : 10.1145/355541.355562、MR 1866456、S2CID 6276962 。
↑ Chazelle, Bernard (2000)、「ソフトヒープ：最適なエラー率を持つ近似優先度キュー」、Journal of the Association for Computing Machinery、47 (6): 1012–1027、doi : 10.1145/355541.355554、MR 1866455、S2CID 12556140 。
↑ Fredman, ML; Tarjan, RE (1987). "Fibonacci heaps and their uses in improved network optimization algorithms" . Journal of the ACM . 34 (3): 596. doi : 10.1145/28869.28874 . S2CID 7904683 .
↑ Gabow, HN ; Galil, Z.; Spencer, T.; Tarjan, RE (1986). "無向グラフおよび有向グラフにおける最小全域木を見つけるための効率的なアルゴリズム". Combinatorica . 6 (2): 109. doi : 10.1007/bf02579168 . S2CID 35618095 .
↑ Fredman, ML ; Willard, DE (1994)、「最小全域木と最短経路のための二分法アルゴリズム」、Journal of Computer and System Sciences、48 (3): 533– 551、doi : 10.1016/S0022-0000(05)80064-9、MR 1279413 。
↑松井智美 (1995-03-10). 「平面グラフ上の最小全域木問題」.離散応用数学. 58 (1): 91– 94. doi : 10.1016/0166-218X(94)00095-U . ISSN 0166-218X .
↑ Cheriton, David; Tarjan, Robert Endre (1976 年 12 月). "最小全域木の探索" . SIAM Journal on Computing . 5 (4): 724– 742. doi : 10.1137/0205051 . ISSN 0097-5397 .
↑ Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), "Concurrent threads and optimal parallel minimum spanning trees algorithm", Journal of the Association for Computing Machinery , 48 (2): 297– 323, doi : 10.1145/375827.375847 , MR 1868718 , S2CID 1778676 。
↑ Pettie, Seth; Ramachandran, Vijaya (2002), "最小全域森を見つけるためのランダム化時間作業最適並列アルゴリズム" (PDF) , SIAM Journal on Computing , 31 (6): 1879– 1895, doi : 10.1137/S0097539700371065 , MR 1954882 。
↑ Steele, J. Michael (2002), "ランダムな辺長を持つグラフの最小全域木", Mathematics and computer science, II (Versailles, 2002) , Trends Math., Basel: Birkhäuser, pp. 223– 245, MR 1940139
1 2マーティン・グレッシェル; Lovász, ラスロー; Schrijver, Alexander (1993)、「幾何学的アルゴリズムと組み合わせ最適化」、アルゴリズムと組み合わせ、第 1 巻。2 (第 2版)、Springer-Verlag、ベルリン、土井: 10.1007/978-3-642-78240-4、ISBN 978-3-642-78242-8MR 1261419
↑ゲイリー、マイケル・R. ;ジョンソン、デイビッド・S. (1979).コンピュータと難解性：NP完全性理論への手引き. 数学科学シリーズ（第1版）. ニューヨーク：WHフリーマン社. ISBN 9780716710455. MR 0519066 . OCLC 247570676 . . ND12
↑ Gabow, Harold N. (1977), "重み付き全域木を順序通りに生成する2つのアルゴリズム", SIAM Journal on Computing , 6 (1): 139–150 , doi : 10.1137/0206011 , MR 0441784 。
↑ Eppstein, David (1992), " k 個の最小全域木の発見", BIT , 32 (2): 237– 248, doi : 10.1007/BF01994879 , MR 1172188 , S2CID 121160520 。
↑ Frederickson, Greg N. (1997), "動的な2エッジ接続性とk最小全域木のための両義的なデータ構造" , SIAM Journal on Computing , 26 (2): 484–538 , doi : 10.1137/S0097539792226825 , MR 1438526 。
↑ Jothi, Raja; Raghavachari, Balaji (2005)、「容量制約付き最小全域木問題とそのネットワーク設計における変種に対する近似アルゴリズム」、ACM Trans. Algorithms、1 (2): 265–282、doi : 10.1145/1103963.1103967、S2CID 8302085
↑ Hu, TC (1961), "最大容量経路問題", Operations Research , 9 (6): 898–900 , doi : 10.1287/opre.9.6.898 , JSTOR 167055 。
↑ McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (2005). "Non-projective dependency parsing using spanning tree algorithms" (PDF) . Proc. HLT/EMNLP .
↑ Simas, Tiago; Correia, Rion B.; Rocha, Luis M. (2021), "複雑ネットワークの距離バックボーン", Journal of Complex Networks , 9 (6) cnab021, arXiv : 2103.04668 , doi : 10.1093/comnet/cnab021 , PMID 38348382 。
↑ Rozum, Jordan C.; Rocha, Luis M. (2021), "The ultrametric backbone is the union of all minimum spanning forests", Journal of Physics: Complexity , 5 (3): 035009, doi : 10.1088/2632-072X/ad679e , PMID 39131403 この記事には、 CC BY 4.0ライセンスの下で利用可能なこの情報源からのテキストが含まれています。
↑ Spira, PM; Pan, A. (1975), "On finding and updating spanning trees and shortest paths" (PDF) , SIAM Journal on Computing , 4 (3): 375– 380, doi : 10.1137/0204032 , MR 0378466 。
↑ Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), "連結性、最小全域木、2エッジ、および双方向連結性のための多対数決定論的完全動的アルゴリズム", Journal of the Association for Computing Machinery , 48 (4): 723– 760, doi : 10.1145/502090.502095 , MR 2144928 , S2CID 7273552 。
↑ Chin, F.; Houck, D. (1978), "最小全域木を更新するためのアルゴリズム", Journal of Computer and System Sciences , 16 (3): 333–344 , doi : 10.1016/0022-0000(78)90022-3。
↑ Chang, RS; Leu, SJ (1997)、「最小ラベル付き全域木」、Information Processing Letters、63 (5): 277– 282、doi : 10.1016/s0020-0190(97)00127-0。
↑ 「ボトルネック・スパニング・ツリーに関するすべて」。flashing-thoughts.blogspot.ru。2010年6月5日。 2018年4月4日取得。
↑ 「アーカイブされたコピー」(PDF)。2013年6月12日にオリジナル(PDF)からアーカイブされました。2014年7月2日に取得。{{cite web}}: CS1 maint: タイトルとしてアーカイブされたコピー (リンク)
↑ Graham, RL ; Hell, Pavol (1985)、「最小全域木問題の歴史について」、Annals of the History of Computing、7 (1): 43– 57、Bibcode : 1985IAHC....7a..43G、doi : 10.1109/MAHC.1985.10011、MR 0783327、S2CID 10555375
↑ Nicos Christofides、「巡回セールスマン問題に対する新しいヒューリスティックの最悪ケース分析」、レポート388、カーネギーメロン大学産業経営大学院、1976年。
↑ダールハウス、E.;ジョンソン, DS州;パパディミトリウ, スイス連邦共和国;シーモア, PD ;ヤナカキス、M. (1994 年 8 月)。「多端子カットの複雑さ」(PDF)。SIAM ジャーナルオンコンピューティング。23 (4): 864–894。土井: 10.1137/S0097539792225297。2004 年 8 月 24 日のオリジナル(PDF)からアーカイブ。2012 年12 月 17 日に取得。
↑ Supowit, Kenneth J.; Plaisted, David A.; Reingold, Edward M. (1980). Heuristics for weighted perfect matching . 12th Annual ACM Symposium on Theory of Computing (STOC '80). New York, NY, USA: ACM. pp. 398–419 . doi : 10.1145/800141.804689 .
↑ Sneath, PHA (1957年8月1日). 「分類学へのコンピュータの応用」 . Journal of General Microbiology . 17 (1): 201– 226. doi : 10.1099/00221287-17-1-201 . PMID 13475686 .
↑浅野隆、バッタチャリヤ博、キール正、ヤオ文雄( 1988)。最小全域木と最大全域木に基づくクラスタリングアルゴリズム。第4回計算幾何学シンポジウム (SCG '88)。第1巻、pp. 252–257。doi : 10.1145/73393.73419。
↑ Gower, JC; Ross, GJS (1969). "最小全域木と単連結クラスタ分析". Journal of the Royal Statistical Society . C (応用統計学). 18 (1): 54– 64. doi : 10.2307/2346439 . JSTOR 2346439 .
↑ Päivinen, Niina (2005年5月1日). "スケールフリーのような構造の最小全域木によるクラスタリング". Pattern Recognition Letters . 26 (7): 921–930 . Bibcode : 2005PaReL..26..921P . doi : 10.1016/j.patrec.2004.09.039 .
↑ Xu, Y.; Olman, V.; Xu, D. (2002年4月1日). "グラフ理論的アプローチを用いた遺伝子発現データのクラスタリング：最小全域木の応用" . Bioinformatics . 18 (4): 536– 545. doi : 10.1093/bioinformatics/18.4.536 . PMID 12016051 .
↑ Dalal, Yogen K.; Metcalfe, Robert M. (1 December 1978). "Reverse path forwarding of broadcast packets" . Communications of the ACM . 21 (12): 1040– 1048. doi : 10.1145/359657.359665 . S2CID 5638057 .
↑ Ma, B.; Hero, A.; Gorman, J.; Michel, O. (2000). Image registration with minimum spanning tree algorithm (PDF) . International Conference on Image Processing. Vol. 1. pp. 481– 484. doi : 10.1109/ICIP.2000.901000 . 2022年10月9日にオリジナルからアーカイブされた(PDF) 。
↑ P. Felzenszwalb、D. Huttenlocher: 効率的なグラフベースの画像セグメンテーション。 IJCV 59(2) (2004 年 9 月)
↑ Suk, Minsoo; Song, Ohyoung (1984年6月1日). "最小全域木を用いた曲線特徴抽出". Computer Vision, Graphics, and Image Processing . 26 (3): 400– 411. doi : 10.1016/0734-189X(84)90221-4 .
↑ Tapia, Ernesto; Rojas, Raúl (2004). "最小全域木構築と記号優位性を用いたオンライン手書き数式の認識" (PDF) . Graphics Recognition. Recent Advances and Perspectives . Lecture Notes in Computer Science. Vol. 3088. Berlin Heidelberg: Springer-Verlag. pp. 329–340 . ISBN 978-3-540-22478-52022年10月9日にオリジナルからアーカイブされた（PDF）。
↑ Ohlsson, H. (2004).最小全域木を用いた低複雑度FIRフィルタの実装. 第12回IEEE地中海電気工学会議（MELECON 2004）. 第1巻. pp. 261–264 . doi : 10.1109/MELCON.2004.1346826 .
↑ RM、アスンサン; MCネベス。 G. カマラ; C. ダコスタフレイタス (2006)。「最小スパニングツリーを使用した社会経済的地理単位の効率的な地域化手法」。地理情報科学の国際ジャーナル。20 (7): 797–811 . Bibcode : 2006IJGIS..20..797A。土井: 10.1080/13658810600665111。S2CID 2530748。
↑ Devillers, J.; Dore, JC (1989年4月1日). "毒性学における最小全域木 (MST) 法のヒューリスティックな有効性". Ecotoxicology and Environmental Safety . 17 (2): 227–235 . Bibcode : 1989EcoES..17..227D . doi : 10.1016/0147-6513(89)90042-0 . PMID 2737116 .
↑森浩、都築聡 (1991 年 5 月 1 日) 「最小全域木法を用いたトポロジー可観測性解析の高速手法」IEEE Transactions on Power Systems 6 ( 2): 491– 500. Bibcode : 1991ITPSy...6..491M . doi : 10.1109/59.76691 .
↑ Filliben, James J.; Kafadar, Karen ; Shier, Douglas R. (1983年1月1日). "2次元曲面の均質性の検定". Mathematical Modelling . 4 (2): 167– 189. doi : 10.1016/0270-0255(83)90026-X .
↑ Kalaba, Robert E. (1963), Graph Theory and Automatic Control (PDF)、2016年2月21日にオリジナル(PDF)からアーカイブ済み
↑ Mantegna, RN (1999).金融市場における階層構造. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193–197.
↑ Djauhari, M., & Gan, S. (2015).株式市場分析におけるネットワークトポロジーの最適性問題. Physica A: Statistical Mechanics and Its Applications, 419, 108–114.

さらに読む

オカール・ボルフカによる最小スパニングツリー問題 (1926 年の両方の論文の翻訳、コメント、歴史) (2000)ヤロスラフネシェトジル、エヴァミルコヴァ、ヘレナネセトリロヴァ。 (セクション 7 では彼のアルゴリズムが示されていますが、これはプリムのアルゴリズムとクラスカルのアルゴリズムを組み合わせたもののように見えます。)
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。『アルゴリズム入門』第2版。MIT PressおよびMcGraw-Hill、2001年。ISBN 0-262-03293-7第23章：最小全域木、561～579ページ。
Eisner, Jason (1997).最小全域木のための最先端アルゴリズム：チュートリアルディスカッション。原稿、ペンシルベニア大学、4月。78ページ。
クロムコウスキー、ジョン・デイビッド。「長年経ってもなお溶けない」、『人種と民族関係年鑑』第17版（2009年マグロウヒル）（米国全土の民族的多様性の人口統計学的分析方法として最小全域木を使用）。

外部リンク

Boost Graph Library (BGL) で実装されています。
ストーニーブルック大学アルゴリズムリポジトリ - 最小全域木コード
QuickGraph for .Net に実装されています

[Numpy_and_Scipy_Documentation_—_Numpy_and_Scipy_documentation-1] "scipy.sparse.csgraph.minimum_spanning_tree - SciPy v1.7.1 マニュアル"。Numpy および Scipy ドキュメント — Numpy および Scipy ドキュメント。2021-12-10に取得。最小全域木は、接続されているすべてのノードを接続するエッジのサブセットで構成され、エッジの重みの合計を最小化するグラフです。

[NetworkX_2.6.2_documentation-2] "networkx.algorithms.tree.mst.minimum_spanning_edges" . NetworkX 2.6.2 ドキュメント. 2021-12-13取得.最小全域木は、エッジの重みの合計が最小となるグラフ（木）の部分グラフです。全域森は、グラフの各連結成分の全域木の和集合です。

[3] 「重み付きグラフの最小全域木は、与えられた重みで同じ数のエッジを持つか？」 . cs.stackexchange.com . 2018年4月4日取得。

[PettieRamachandran2002-4] 1 2 3 4 5 Pettie, Seth; Ramachandran, Vijaya (2002)、「最適な最小全域木アルゴリズム」(PDF)、Journal of the Association for Computing Machinery、49 (1): 16–34、doi : 10.1145/505241.505243、MR 2148431、S2CID 5362916 。

[5] Karger, David R. ; Klein, Philip N. ; Tarjan, Robert E. (1995), "最小全域木を見つけるためのランダム化線形時間アルゴリズム", Journal of the Association for Computing Machinery , 42 (2): 321– 328, doi : 10.1145/201019.201022 , MR 1409738 , S2CID 832583

[6] Pettie, Seth; Ramachandran, Vijaya (2002)、「最小全域木、並列接続性、および集合最大値アルゴリズムにおけるランダム性の最小化」、第13回ACM-SIAM離散アルゴリズムシンポジウム（SODA '02）論文集、カリフォルニア州サンフランシスコ、713–722ページ、ISBN 978-0-89871-513-2{{citation}}: CS1 maint: 場所の発行元が見つかりません (リンク)。

[Chazelle2000-7] 1 2 Chazelle, Bernard (2000)、「逆アッカーマン型複雑度を持つ最小全域木アルゴリズム」、Journal of the Association for Computing Machinery、47 (6): 1028–1047、doi : 10.1145/355541.355562、MR 1866456、S2CID 6276962 。

[8] Chazelle, Bernard (2000)、「ソフトヒープ：最適なエラー率を持つ近似優先度キュー」、Journal of the Association for Computing Machinery、47 (6): 1012–1027、doi : 10.1145/355541.355554、MR 1866455、S2CID 12556140 。

[9] Fredman, ML; Tarjan, RE (1987). "Fibonacci heaps and their uses in improved network optimization algorithms" . Journal of the ACM . 34 (3): 596. doi : 10.1145/28869.28874 . S2CID 7904683 .

[10] Gabow, HN ; Galil, Z.; Spencer, T.; Tarjan, RE (1986). "無向グラフおよび有向グラフにおける最小全域木を見つけるための効率的なアルゴリズム". Combinatorica . 6 (2): 109. doi : 10.1007/bf02579168 . S2CID 35618095 .

[11] Fredman, ML ; Willard, DE (1994)、「最小全域木と最短経路のための二分法アルゴリズム」、Journal of Computer and System Sciences、48 (3): 533– 551、doi : 10.1016/S0022-0000(05)80064-9、MR 1279413 。

[12] 松井智美 (1995-03-10). 「平面グラフ上の最小全域木問題」.離散応用数学. 58 (1): 91– 94. doi : 10.1016/0166-218X(94)00095-U . ISSN 0166-218X .

[13] Cheriton, David; Tarjan, Robert Endre (1976 年 12 月). "最小全域木の探索" . SIAM Journal on Computing . 5 (4): 724– 742. doi : 10.1137/0205051 . ISSN 0097-5397 .

[14] Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), "Concurrent threads and optimal parallel minimum spanning trees algorithm", Journal of the Association for Computing Machinery , 48 (2): 297– 323, doi : 10.1145/375827.375847 , MR 1868718 , S2CID 1778676 。

[15] Pettie, Seth; Ramachandran, Vijaya (2002), "最小全域森を見つけるためのランダム化時間作業最適並列アルゴリズム" (PDF) , SIAM Journal on Computing , 31 (6): 1879– 1895, doi : 10.1137/S0097539700371065 , MR 1954882 。

[16] Steele, J. Michael (2002), "ランダムな辺長を持つグラフの最小全域木", Mathematics and computer science, II (Versailles, 2002) , Trends Math., Basel: Birkhäuser, pp. 223– 245, MR 1940139

[:1-17] 1 2マーティン・グレッシェル; Lovász, ラスロー; Schrijver, Alexander (1993)、「幾何学的アルゴリズムと組み合わせ最適化」、アルゴリズムと組み合わせ、第 1 巻。2 (第 2版)、Springer-Verlag、ベルリン、土井: 10.1007/978-3-642-78240-4、ISBN 978-3-642-78242-8MR 1261419

[18] ゲイリー、マイケル・R. ;ジョンソン、デイビッド・S. (1979).コンピュータと難解性：NP完全性理論への手引き. 数学科学シリーズ（第1版）. ニューヨーク：WHフリーマン社. ISBN 9780716710455. MR 0519066 . OCLC 247570676 . . ND12

[19] Gabow, Harold N. (1977), "重み付き全域木を順序通りに生成する2つのアルゴリズム", SIAM Journal on Computing , 6 (1): 139–150 , doi : 10.1137/0206011 , MR 0441784 。

[20] Eppstein, David (1992), " k 個の最小全域木の発見", BIT , 32 (2): 237– 248, doi : 10.1007/BF01994879 , MR 1172188 , S2CID 121160520 。

[21] Frederickson, Greg N. (1997), "動的な2エッジ接続性とk最小全域木のための両義的なデータ構造" , SIAM Journal on Computing , 26 (2): 484–538 , doi : 10.1137/S0097539792226825 , MR 1438526 。

[22] Jothi, Raja; Raghavachari, Balaji (2005)、「容量制約付き最小全域木問題とそのネットワーク設計における変種に対する近似アルゴリズム」、ACM Trans. Algorithms、1 (2): 265–282、doi : 10.1145/1103963.1103967、S2CID 8302085

[23] Hu, TC (1961), "最大容量経路問題", Operations Research , 9 (6): 898–900 , doi : 10.1287/opre.9.6.898 , JSTOR 167055 。

[24] McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (2005). "Non-projective dependency parsing using spanning tree algorithms" (PDF) . Proc. HLT/EMNLP .

[25] Simas, Tiago; Correia, Rion B.; Rocha, Luis M. (2021), "複雑ネットワークの距離バックボーン", Journal of Complex Networks , 9 (6) cnab021, arXiv : 2103.04668 , doi : 10.1093/comnet/cnab021 , PMID 38348382 。

[26] Rozum, Jordan C.; Rocha, Luis M. (2021), "The ultrametric backbone is the union of all minimum spanning forests", Journal of Physics: Complexity , 5 (3): 035009, doi : 10.1088/2632-072X/ad679e , PMID 39131403 この記事には、 CC BY 4.0ライセンスの下で利用可能なこの情報源からのテキストが含まれています。

[27] Spira, PM; Pan, A. (1975), "On finding and updating spanning trees and shortest paths" (PDF) , SIAM Journal on Computing , 4 (3): 375– 380, doi : 10.1137/0204032 , MR 0378466 。

[28] Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), "連結性、最小全域木、2エッジ、および双方向連結性のための多対数決定論的完全動的アルゴリズム", Journal of the Association for Computing Machinery , 48 (4): 723– 760, doi : 10.1145/502090.502095 , MR 2144928 , S2CID 7273552 。

[29] Chin, F.; Houck, D. (1978), "最小全域木を更新するためのアルゴリズム", Journal of Computer and System Sciences , 16 (3): 333–344 , doi : 10.1016/0022-0000(78)90022-3。

[30] Chang, RS; Leu, SJ (1997)、「最小ラベル付き全域木」、Information Processing Letters、63 (5): 277– 282、doi : 10.1016/s0020-0190(97)00127-0。

[31] 「ボトルネック・スパニング・ツリーに関するすべて」。flashing-thoughts.blogspot.ru。2010年6月5日。 2018年4月4日取得。

[32] 「アーカイブされたコピー」(PDF)。2013年6月12日にオリジナル(PDF)からアーカイブされました。2014年7月2日に取得。{{cite web}}: CS1 maint: タイトルとしてアーカイブされたコピー (リンク)

[33] Graham, RL ; Hell, Pavol (1985)、「最小全域木問題の歴史について」、Annals of the History of Computing、7 (1): 43– 57、Bibcode : 1985IAHC....7a..43G、doi : 10.1109/MAHC.1985.10011、MR 0783327、S2CID 10555375

[34] Nicos Christofides、「巡回セールスマン問題に対する新しいヒューリスティックの最悪ケース分析」、レポート388、カーネギーメロン大学産業経営大学院、1976年。

[35] ダールハウス、E.;ジョンソン, DS州;パパディミトリウ, スイス連邦共和国;シーモア, PD ;ヤナカキス、M. (1994 年 8 月)。「多端子カットの複雑さ」(PDF)。SIAM ジャーナルオンコンピューティング。23 (4): 864–894。土井: 10.1137/S0097539792225297。2004 年 8 月 24 日のオリジナル(PDF)からアーカイブ。2012 年12 月 17 日に取得。

[36] Supowit, Kenneth J.; Plaisted, David A.; Reingold, Edward M. (1980). Heuristics for weighted perfect matching . 12th Annual ACM Symposium on Theory of Computing (STOC '80). New York, NY, USA: ACM. pp. 398–419 . doi : 10.1145/800141.804689 .

[37] Sneath, PHA (1957年8月1日). 「分類学へのコンピュータの応用」 . Journal of General Microbiology . 17 (1): 201– 226. doi : 10.1099/00221287-17-1-201 . PMID 13475686 .

[38] 浅野隆、バッタチャリヤ博、キール正、ヤオ文雄( 1988)。最小全域木と最大全域木に基づくクラスタリングアルゴリズム。第4回計算幾何学シンポジウム (SCG '88)。第1巻、pp. 252–257。doi : 10.1145/73393.73419。

[39] Gower, JC; Ross, GJS (1969). "最小全域木と単連結クラスタ分析". Journal of the Royal Statistical Society . C (応用統計学). 18 (1): 54– 64. doi : 10.2307/2346439 . JSTOR 2346439 .

[40] Päivinen, Niina (2005年5月1日). "スケールフリーのような構造の最小全域木によるクラスタリング". Pattern Recognition Letters . 26 (7): 921–930 . Bibcode : 2005PaReL..26..921P . doi : 10.1016/j.patrec.2004.09.039 .

[41] Xu, Y.; Olman, V.; Xu, D. (2002年4月1日). "グラフ理論的アプローチを用いた遺伝子発現データのクラスタリング：最小全域木の応用" . Bioinformatics . 18 (4): 536– 545. doi : 10.1093/bioinformatics/18.4.536 . PMID 12016051 .

[42] Dalal, Yogen K.; Metcalfe, Robert M. (1 December 1978). "Reverse path forwarding of broadcast packets" . Communications of the ACM . 21 (12): 1040– 1048. doi : 10.1145/359657.359665 . S2CID 5638057 .

[43] Ma, B.; Hero, A.; Gorman, J.; Michel, O. (2000). Image registration with minimum spanning tree algorithm (PDF) . International Conference on Image Processing. Vol. 1. pp. 481– 484. doi : 10.1109/ICIP.2000.901000 . 2022年10月9日にオリジナルからアーカイブされた(PDF) 。

[44] P. Felzenszwalb、D. Huttenlocher: 効率的なグラフベースの画像セグメンテーション。 IJCV 59(2) (2004 年 9 月)

[45] Suk, Minsoo; Song, Ohyoung (1984年6月1日). "最小全域木を用いた曲線特徴抽出". Computer Vision, Graphics, and Image Processing . 26 (3): 400– 411. doi : 10.1016/0734-189X(84)90221-4 .

[46] Tapia, Ernesto; Rojas, Raúl (2004). "最小全域木構築と記号優位性を用いたオンライン手書き数式の認識" (PDF) . Graphics Recognition. Recent Advances and Perspectives . Lecture Notes in Computer Science. Vol. 3088. Berlin Heidelberg: Springer-Verlag. pp. 329–340 . ISBN 978-3-540-22478-52022年10月9日にオリジナルからアーカイブされた（PDF）。

[47] Ohlsson, H. (2004).最小全域木を用いた低複雑度FIRフィルタの実装. 第12回IEEE地中海電気工学会議（MELECON 2004）. 第1巻. pp. 261–264 . doi : 10.1109/MELCON.2004.1346826 .

[48] RM、アスンサン; MCネベス。 G. カマラ; C. ダコスタフレイタス (2006)。「最小スパニングツリーを使用した社会経済的地理単位の効率的な地域化手法」。地理情報科学の国際ジャーナル。20 (7): 797–811 . Bibcode : 2006IJGIS..20..797A。土井: 10.1080/13658810600665111。S2CID 2530748。

[49] Devillers, J.; Dore, JC (1989年4月1日). "毒性学における最小全域木 (MST) 法のヒューリスティックな有効性". Ecotoxicology and Environmental Safety . 17 (2): 227–235 . Bibcode : 1989EcoES..17..227D . doi : 10.1016/0147-6513(89)90042-0 . PMID 2737116 .

[50] 森浩、都築聡 (1991 年 5 月 1 日) 「最小全域木法を用いたトポロジー可観測性解析の高速手法」IEEE Transactions on Power Systems 6 ( 2): 491– 500. Bibcode : 1991ITPSy...6..491M . doi : 10.1109/59.76691 .

[51] Filliben, James J.; Kafadar, Karen ; Shier, Douglas R. (1983年1月1日). "2次元曲面の均質性の検定". Mathematical Modelling . 4 (2): 167– 189. doi : 10.1016/0270-0255(83)90026-X .

[52] Kalaba, Robert E. (1963), Graph Theory and Automatic Control (PDF)、2016年2月21日にオリジナル(PDF)からアーカイブ済み

[53] Mantegna, RN (1999).金融市場における階層構造. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193–197.

[54] Djauhari, M., & Gan, S. (2015).株式市場分析におけるネットワークトポロジーの最適性問題. Physica A: Statistical Mechanics and Its Applications, 419, 108–114.

[

[

[ 3 ]

[

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[

[

[ 33 ]

[

[

[

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[

[ 42 ]

[ 43 ]

[ 44 ]

[

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]