辺の重みが異なる場合
最小全域木問題が厄介なのは、グラフに重みが同じ最小全域木が複数存在することがあり得る点です。例えば \(G\) の全ての辺の重みが \(1\) の場合、\(G\) の全ての全域木が重み \(V-1\) の最小全域木です。最小全域木が複数あるとアルゴリズムの開発が複雑になるので、最小全域木が一つだけだと仮定できれば話が単純になります。
幸いにも、最小全域木が唯一であることを保証する簡単な条件があります。
命題 7.1 連結グラフ \(G\) の辺の重みが全て異なる場合、\(G\) は唯一の最小全域木を持つ1。
証明 適当なグラフ \(G\) が二つの最小全域木 \(T, T^{\prime}\) を持つとする。\(G\) に含まれる辺の組が同じ重みを持つことをこれから示す。この証明が本質的に使っているのは、貪欲アルゴリズムの正しさの証明に用いた交換の議論である。
二つの全域木にはお互いに相手に存在しない辺が含まれる。\(e\) を \(T \backslash T^{\prime}\) に含まれる重みが最小の辺、\(e^{\prime}\) を \(T^{\prime} \backslash T\) に含まれる重みが最小の辺とする (重みが最小の辺が複数ある場合には適当に選ぶ)。一般性を失うことなく \(w(e) \leq w(e^{\prime})\) と仮定する。
部分グラフ \(T^{\prime} \cup \lbrace e \rbrace\) にはちょうど一つの閉路 \(C\) が含まれ、\(C\) は \(e\) を通る。\(e^{\prime\prime}\) を \(C\) に含まれて \(T\) に含まれない辺とする。\(T\) は木だから、そのような辺は必ず存在する (\(e^{\prime\prime} = e^{\prime}\) かもしれないし、そうでないかもしれない)。\(e \in T\) と \(e^{\prime\prime} \notin T\)より \(e^{\prime\prime} \neq e\) であり、よって \(e^{\prime\prime} \in T^{\prime} \backslash T\) である。したがって \(w(e^{\prime\prime}) \geq w(e^{\prime}) \geq w(e)\) が分かる。
全域木 \(T^{\prime\prime} = T^{\prime} + e - e^{\prime\prime}\) を考える (\(T^{\prime\prime}\) は \(T\) に等しいかもしれない)。このとき \(w(T^{\prime\prime}) = w(T^{\prime}) + w(e) - w(e^{\prime\prime}) \leq w(T^{\prime})\) となるが、\(T^{\prime}\) は最小全域木なので、\(w(T^{\prime\prime}) = w(T^{\prime})\) となる。つまり、\(T^{\prime\prime}\) もまた最小全域木である。したがって \(w(e) = w(e^{\prime\prime})\) であり、証明したい式が得られた。 \(\Box\)
procedure \(\texttt{ShorterEdge}\)(\(i,j,k,l\))
if \(w(i, j) < w(k, l)\) then
return \((i, j)\)
else if \(w(i, j) > w(k, l)\) then
return \((k, l)\)
else if \(\min(i, j) < \min(k, l)\) then
return \((i, j)\)
else if \(\min(i, j) > \min(k, l)\) then
return \((k. l)\)
else if \(\max(i, j) < \max(k, l)\) then
return \((i, j)\)
else
\(\color{maroon}{\langle \langle \max(i, j) > \max(k, l) \rangle \rangle}\)
return \((k. l)\)
同じ重みを持つ辺が複数ある場合の一貫した辺の選び方を決めておけば、辺の重みが異なるグラフに対するアルゴリズムを同じ重みを持つ辺のあるグラフに対するアルゴリズムに変形できます。上に示したのは一例です。\(\textsc{ShorterEdge}\) は四つの (異なるとは限らない) 頂点 \(i,j,k,l\) を受け取り、\((i, j)\) と \((k, l)\) のどちらが "短い" かを返します (入力は無向グラフであり、\((i, j)\) と \((j, i)\) が同じ辺を表すことに注意してください)。
命題 7.1 より、この選び方を使えば任意のグラフの最小木が唯一となります。よって、これからこの章では辺の重さが異なるグラフが常に与えられ、その最小全域木は常に一つだけであると仮定しても問題ありません。つまり「グラフの最小全域木を... (the minimum spanning tree ...)」と書いたとしても曖昧さは生じません。
-
この命題の逆は正しくありません。同じ重みの辺を持つ連結グラフでも最小全域木が唯一であることがあります。自明な例として、\(G\) が木の場合を考えてみてください！[return]