18/07/13 03:52:44.37 cHaDvtca.net
連結無向グラフG=(V,E)に対して与えられた枝重みが全て異なるなら、
最小全域木(V,T)は一意に求められることを示せ
全域木(V,T)が最小木であることの必要十分条件が
「Tの任意の補木枝a⊆E-Tから得られる基本閉路C(a)に対し,
aの枝重みw(a)が、C(a)の任意の枝bの枝重みw(b)に対してw(a)≧w(b)となる」
若しくは
「Tの任意の枝b⊆Tから得られるbの基本カットセットS(b)に対し、
bの枝重みw(b)が、S(b)の任意の枝aの枝重みw(a)に対してw(a)≧w(b)となる」
であることを用いて良いとする