グラフアルゴリズム(2)

連結な無向グラフの全ての頂点を含む部分グラフで木であるものをスパニング木という。

行列木定理
連結な無向グラフGのスパニング木の個数はL(G)*1の任意の対角要素に関する余因子の値に等しい。

重み付きグラフの重みを最も小さくするようなスパニング木を最小スパニング木という

グリーディ法という。
時間計算量は、頂点数をn、辺の数をmとするとO(nm)になる。

互いに素なSの部分集合S1,S2,...,Skに対して、次の2種類の命令を考える。
Union(Si,Sj)：Si←Si∪SjとしSjを消去
find(a)：aの含まれる部分集合の名前を見つける