スパニングツリー

全域木に辺を 1 つ追加するだけでサイクルが作成されます。このようなサイクルは、その木に関して基本サイクルと呼ばれます。全域木に含まれない各辺にはそれぞれ固有の基本サイクルが存在するため、基本サイクルと全域木に含まれない辺の間には 1 対 1 の対応関係があります。頂点がV個の連結グラフの場合、任意の全域木にはV  − 1 個の辺があり、したがって、辺数がE 個のグラフとその全域木の 1 つには、E − V + 1 個の基本サイクルがあります (全域木に含まれる辺の数から辺の数を引いた数。これは、全域木に含まれない辺の数を示します)。任意の全域木に対して、すべてのE − V + 1 個の基本サイクルの集合はサイクル基底、つまりサイクル空間の基底を形成します。^{[ 5 ]}        

基本サイクルの概念と双対なのが、与えられた全域木に関する基本カットセットの概念である。全域木の1つのエッジを削除するだけで、頂点は互いに素な2つの集合に分割される。基本カットセットは、同じ分割を実現するためにグラフGから削除しなければならないエッジの集合として定義される。したがって、各全域木は、全域木のエッジごとに1つずつ、 V  − 1個の基本カットセットを定義する 。^{[ 6 ]}

基本カットセットと基本サイクルの双対性は、全域木に含まれないサイクルのエッジは、そのサイクル内の他のエッジのカットセットにのみ現れること、そしてその逆もまた然り、つまりカットセット内のエッジは、そのカットセットに対応するエッジを含むサイクルにのみ現れることに注目することで確立されます。この双対性は、マトロイドの理論を用いて表現することもできます。マトロイドの理論によれば、全域木はグラフィックマトロイドの基底であり、基本サイクルは基底に1つの要素を追加して形成される集合内の唯一の回路であり、基本カットセットは双対マトロイドから同じように定義されます。^{[ 7 ]}

互いに連結していない木の集合は、森と呼ばれます。グラフにおける全域森とは、追加の要件を持つ森の部分グラフのことです。現在使用されている要件には、互いに矛盾するものが2つあり、そのうちの1つは比較的まれです。

• グラフ理論のほとんどすべての書籍や論文では、全域森をすべての頂点を網羅する森と定義しており、これはグラフの各頂点が森の頂点であることを意味するだけです。連結グラフには、エッジのない森のように、各頂点が単一頂点の木を形成するような、非連結全域森が存在する場合があります。^{[ 8 ] [ 9 ]}

• グラフ理論の著者の中には、スパニングフォレストを、与えられたグラフの最大非巡回部分グラフ、あるいは同等に、グラフの各連結成分にスパニングツリーを含む部分グラフと定義する者もいる。 ^{[ 10 ]}

これら2つの定義の混同を避けるため、Gross & Yellen (2005) は、与えられたグラフと同じ数のコンポーネントを持つ全域森 (つまり、最大森) に対して「完全全域森」という用語を提案しているが、Bondy & Murty (2008)は、この種の森を「最大全域森」と呼んでいる (最大森は必然的にすべての頂点を含むため、これは冗長である)。^{[ 11 ]}

場合によっては、t ( G )を直接計算するのは簡単です。

• Gがそれ自体木である場合、 t ( G )  =  1となります。
• Gがn 個の頂点を持つサイクルグラフC _nである場合、t ( G ) = nとなります。  
• n個の頂点 を持つ完全グラフの場合、ケイリーの公式^{[ 12 ]}は全域木の数をn ^{n − 2}として与える。  
• Gが完全二部グラフである場合${\displaystyle K_{p,q}}$、それから$t(G)=p^{q-1}q^{p-1}}$[ ^{8 ]​}
• n次元ハイパーキューブグラフの場合${\displaystyle Q_{n}}$[ ^{13 ]スパニングツリーの}数は${\displaystyle t(G)=2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$。

より一般的には、任意のグラフGに対して、キルヒホッフの行列木定理を用いて、グラフから導出された行列の行列式として、数t ( G ) を多項式時間で計算することができる。^{[ 14 ]}

具体的には、t ( G )を計算するには、グラフのラプラシアン行列を構築します。これは、行と列の両方がGの頂点によってインデックス付けされた正方行列です。行i、列jのエントリは、次の3つの値のいずれかになります。

• 頂点iの次数( i  = jの場合) 
• −1、頂点iとjが隣接している場合、または
• 頂点iとjが互いに異なり、かつ隣接していない場合は 0 を返します。

結果として得られる行列は特異行列なので、その行列式はゼロになります。しかし、任意に選択した頂点の行と列を削除すると、行列式がちょうどt ( G ) となるより小さな行列が得られます。 

Gがグラフまたは多重グラフであり、eがGの任意のエッジである場合、 Gの全域木の数t ( G ) は、削除縮約の漸化式t ( G ) = t ( G − e ) + t ( G / e )を満たします。ここで、 G − eはe を削除して得られる多重グラフであり 、G / eはGをeで縮約したものです。^{[ 15 ]}この式の項t ( G − e ) は、エッジeを使用しないGの全域木を数え、項t ( G / e ) は、 eを使用するGの全域木を数えます。              

この式において、与えられたグラフGが多重グラフである場合、または縮約によって 2 つの頂点が複数の辺で接続される場合、冗長な辺は削除してはなりません。削除すると合計値が間違ってしまうためです。例えば、 2 つの頂点をk本の辺で接続するボンドグラフには、 k個の異なる全域木が存在し、それぞれがこれらの辺のうちの 1 つで構成されています。

グラフのタット多項式は、グラフの全域木について、木の「内部活動」と「外部活動」から計算された項の合計として定義できます。引数(1,1)におけるその値は、全域木の数、または非連結グラフの場合は最大全域森の数です。^{[ 16 ]}

Tutte 多項式は削除縮約漸化式を用いて計算することもできますが、計算複雑度は高く、引数の多くの値に対して正確に計算することは#P-完全であり、保証された近似比で近似することも困難です。キルヒホッフの定理を用いて評価できる点 (1,1) は、数少ない例外の 1 つです。^{[ 17 ]}

グラフの単一全域木は、深さ優先探索または幅優先探索のいずれかによって線形時間で見つけることができます。これらのアルゴリズムはどちらも、任意の頂点vから開始して、発見した頂点の隣接をループして、未探索の隣接をそれぞれ後で探索するデータ構造に追加することによって、与えられたグラフを探索します。これらのアルゴリズムの違いは、このデータ構造が スタック(深さ優先探索の場合) か キュー(幅優先探索の場合) かです。どちらの場合も、ルート頂点v以外の各頂点を、それが発見された頂点に接続することによって全域木を形成できます。この木は、構築に使用されるグラフ探索アルゴリズムに応じて、深さ優先探索木または幅優先探索木として知られています。^{[ 18 ]}深さ優先探索木は、19 世紀の深さ優先探索の発見者にちなんで名付けられたトレモー木と呼ばれる全域木のクラスの特殊なケースです。 ^{[ 19 ]}

スパニングツリーは、並列および分散コンピューティングにおいて、プロセッサ群間の通信を維持する方法として重要です。例えば、OSIリンク層デバイスで使用されるスパニングツリープロトコルや、分散コンピューティング用のShout（プロトコル）を参照してください。しかし、逐次コンピュータでスパニングツリーを構築するための深さ優先法と幅優先法は、並列および分散コンピュータには適していません。^{[ 20 ]}その代わりに、研究者たちは、これらの計算モデルでスパニングツリーを見つけるための、より特殊なアルゴリズムをいくつか考案しました。^{[ 21 ]}

グラフ理論の特定の分野では、重み付きグラフの最小全域木を見つけることがしばしば有用です。全域木に関する他の最適化問題も研究されており、最大全域木、少なくとも k 個の頂点を張る最小木、頂点あたりのエッジ数が最小の全域木、葉の数が最大の全域木、葉の数が最小の全域木（ハミルトン経路問題と密接に関連）、最小直径全域木、最小膨張全域木などがあります。^{[ 22 ] [ 23 ]}

ユークリッド平面などの幾何学的空間における有限個の点の集合についても、最適全域木問題が研究されてきました。このような入力に対して、全域木は、与えられた点を頂点とする木となります。木の品質は、グラフの場合と同様に、各辺の重みとして点のペア間のユークリッド距離を用いて測定されます。したがって、例えば、ユークリッド最小全域木は、ユークリッド辺重みを持つ完全グラフにおけるグラフ最小全域木と同じです。ただし、最適化問題を解くためにこのグラフを構築する必要はありません。例えば、ユークリッド最小全域木問題は、ドロネー三角形分割を構築し、その結果得られた三角形分割に線形時間平面グラフ最小全域木アルゴリズムを適用することで、 O ( n  log n )の時間でより効率的に解くことができます。^{[ 22 ]} 

すべての全域木の中から等しい確率でランダムに選択された全域木を均一全域木と呼びます。ウィルソンのアルゴリズムは、与えられたグラフ上でランダムウォークを行い、このウォークによって生成されたサイクルを消去するプロセスによって、多項式時間で均一全域木を生成するために使用できます。^{[ 24 ]}

ランダムに、ただし均一ではない全域木を生成する代替モデルとして、ランダム最小全域木があります。このモデルでは、グラフのエッジにランダムな重みが割り当てられ、その後、重み付きグラフの最小全域木が構築されます。^{[ 25 ]}

グラフには指数関数的に多くの全域木が存在する可能性があるため、それらをすべて多項式時間で列挙することは不可能です。しかし、木ごとにすべての全域木を多項式時間で列挙するアルゴリズムが知られています。^{[ 26 ]}