プリム法 正しさの証明

ウィキペディア

プリム法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/12/05 08:32 UTC 版)

正しさの証明

P を重み付き連結グラフとする。プリム法の繰り返しでは、毎回ある部分グラフからその外部へと接続している辺を探し出す。P は連結グラフなので、全ての頂点に常に道が存在する。プリム法の出力 Y に追加される辺と頂点はつねに接合しているため、Y は木である。Y₁ が P の最小全域木であるとする。Y₁=Y なら、Y は最小全域木である。そうでない場合、Y にあって Y₁ にない辺のうち、Y の構築時に最初に追加された辺を e とし、e が追加される以前に追加された辺に接合している頂点の集合を V とする。e の端点の一方は V にあり、もう一方はそうではない。Y₁ は P の全域木なので、Y₁ にはその2つの端点をつなぐ道がある。その道をたどると、V 内の頂点から V 外の頂点への辺 f に必ず遭遇する。さて、Y に e を追加した時の繰り返しにおいて、e よりも f の方が重みが小さければ f が追加されていただろう。しかし f は追加されなかったので、次の結論が得られる。

w(f) ≥ w(e)

Y₁ から f を除いて e を追加したグラフを Y₂ とする。Y₂ が連結グラフであり、Y₁ と同数の辺を持ち、辺の重みの総和が Y₁ より小さいことは容易に示すことができる。従って、これも P の最小全域木であり、e を含み、それ以前に V の構築の際に追加された全ての辺を含んでいる。以上を繰り返し適用していくと、Y と全く同じ P の最小全域木を得られる。以上から、Y は最小全域木であることがわかる。

最小全域木問題の他のアルゴリズムとしてクラスカル法やブルーフカ法がある。