0937132人目の素数さん
2018/07/13(金) 03:52:44.37ID:cHaDvtca最小全域木(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)となる」
であることを用いて良いとする