最小スパニングツリーグラフ

Question

私は、接続されたグラフG =（V、E）V = {1,2、...、n} とコスト関数c：E-> R と第2部分グラフG 'T = {すべての頂点v∈vについては最低限のコストでネイバーを発見し、Tに新しいエッジを追加} =（V、T）

G場合' グラフは、少なくとも有しています2つの接続されたコンポーネントを頂点のセットと比較すると、 のエッジの集合（初期グラフGの）がn ull。我々は、Hの端にコスト関数を定義する。

の私はV（H）= {E、F}及びE（H）= {AE、AF、FE}あらゆるエッジe∈Eの今

E12={ab,bc,bd,ed} 
E23={eg,ef} E31={fc,fd}        
c'(ae)=min{c(ab),c(bc),c(bd),c(ed)}=4 
c'(af)=min{c(fc),c(fd)}=9 
c'(fe)=min{c(eg),c(ef)}=8 

（Hを選択しましょう）は、この最小値に達するエッジ（元のグラフGから）
のe 'で示されます。 したがって、e '= {bc、df、eg}はbc = 4、df = 9、たとえば= 8で、私のコンポーネントを接続する最小の辺なのでです。 そして、私はコスト関数c 'に対してHで最小スパニングツリーを持ち、A'はこのツリーのエッジの集合です。

だからA '= {ae、fe}（最小スパニングツリーを作成するために私のグラフHから最大コスト= afでエッジを削除した） と私は別のエッジのセットを持っている' = {e '| e∈A '}であり、 は、関数コストcに対するGの最小スパニングツリーです。

しかし、A 'からのエッジはどれもe'からのものと同じではありません。

私は間違っていますか？

Answer 1

Boruvkaのアルゴリズムを実装しているようです。あなたは表記を見れば、それは、x ∈ C とy ∈一対のノードが存在する場合、新しいノードv _C 1つの新しいノードv _Cからエッジがあると言いますC は、元のグラフGに隣接しています。つまり、G 'に対応する接続​​されたコンポーネントがGに隣接する場合、2つの新しいノードの間にエッジがあります。それらの間を走るエッジのコストは、元のグラフGのそれらのCC間を走るエッジのいずれかのコストのうちの1つである。