アルゴリズムグラフィックス

23.2-1         ，Kruskal              。              ，              。  ：   G        T，        G      ，  Kruskal             T。

直接的な考えは、入力時にエッジの順序を追加することです(つまり、同じ重みでどのエッジが保存されているかを見て、前にどれを選ぶか).どうやって証明できるのか><
ちなみにpoではこの問題を解決するために復習と思考の内容(はい、XDを考えます
関連

Kruskalアルゴリズムは,重みの最小を選択するたびに森林に加わるものであり,その本質は貪欲アルゴリズムである.

この図のすべてのエッジが異なる場合、最小生成ツリーが一意であることを証明することができる.

各辺の重み値が一意である場合、最小生成ツリーから、エッジiを1つずつ追加し、新しく生成されたリング上で最大のエッジj(重み値ei

所与の図において、最小生成ツリーの重み値及び重み値が決定するので、最小生成ツリーは一意ではなく、最小生成ツリーの形状が一意でない場合のみ

である.

は、最小生成ツリーTと任意の生成ツリーT’とを証明し、エッジをw 1<=w 2<=......<=wn、w’1<=w’2<=...<=w’nにw’i<=w’iがある

iの場合、iが最初にw’i=wn−1>=...>=wi>w’i>=w’i−1>=...>=w’1である.

ですので、{w’1...w’i}のいずれかにTを加えるか、{w 1...wi−1}とループを生成するか、{w 1...wi−1}のいずれかのエッジを生成するかを選択します.

であるため、辺e 1…ei−1を選択するとn−i+1個の連通成分があり、辺e′1…e′iを加えてもn−i個の連通成分であるが、実際には、生成ツリーT′からのものであるため、辺e′1…e′iはn−i個の連通成分

を有することができる.

だから矛盾している.

また、最小生成ツリー一意性判定

図中の各エッジについて、他のエッジをスキャンし、同じ重み値のエッジが存在する場合、そのエッジをマークする.

そしてKruskal(またはPrim)アルゴリズムを用いてMST(最小生成ツリー)を求める.

MSTを求めた後、そのMSTにマークされたエッジが含まれていなければ、MST一意を判定することができる.マークされたエッジが含まれている場合は、これらを順次取り除いてMSTを求め、求めたMSTの重み値が元のMSTの重み値と同じであれば、MSTが一意ではないと判定することができる.

ターン

  23.1-8                     ，                ，                     。（    ） 

証:最小生成木にn本の辺があるとし、任意の2本の最小生成木をそれぞれA,Bと呼び、eが1本の辺であれば、w(e)でその辺の重み値を表す.Aの辺は重み値増加順にa 1,a 2,…an w(a 1)≦w(a 2)≦…w(an)Bの辺は重み値増加順にb 1,b 2,…bnw(b 1)≦w(b 2)≦…w(bn)iを2つの辺リストに設定し、初めて異なる辺が現れる位置とし、ai≠bi w(ai)≧w(bi)の場合1木Aに辺biが含まれている場合、必ずj>iがbi=ajとなり、実際、このときw(bi)=w(aj)≧w(ai)≧w(bi)があるのでw(bi)=w(aj)=w(ai)となり、ツリーAのエッジリストでエッジaiとajを交換する位置はツリーAのエッジ重みに影響を及ぼさずシーケンステーブルがあり、2本のツリーがi番目の位置のエッジで同じエッジになる.ケース2木Aに辺biが含まれていない場合は,biを木Aに加算して輪を形成するが,Aは最小生成木であるため,この輪のいずれの辺の重み値もw(bi)より大きくなく,また,この輪に辺ajが木Bに存在しない.従って、w(aj)≦w(bi)があり、j>i(ajはBにないため)である.従って、w(bi)≦w(ai)≦w(aj)≦w(bi)があるので、w(ai)=w(aj)=w(bi)となる.ツリーAでajをbiに置き換えると、最小生成ツリーであり、ツリーAのエッジ重みシーケンステーブルに影響を与えず、シナリオ1に変換される.