最小性
最小性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/10 17:55 UTC 版)
この証明には背理法を用いる。 Y {\displaystyle Y} が最小全域木でないとすると、別に最小全域木が一つ以上存在する。それらの中から、 Y {\displaystyle Y} と共通する辺の数が最も多い木 Y 1 {\displaystyle Y_{1}} を選ぶ。 Y {\displaystyle Y} に含まれ Y 1 {\displaystyle Y_{1}} には含まれない辺の中で、本アルゴリズムによって Y {\displaystyle Y} に最初に追加される 辺 e {\displaystyle e} について考える。 Y 1 ∪ e {\displaystyle Y_{1}\cup {e}} には閉路が存在する。 Y {\displaystyle Y} は木であるので、閉路を形成する辺を全部含むことはない。したがって、この閉路には Y {\displaystyle Y} には含まれない辺 f が存在する。 Y 2 = Y 1 ∪ e ∖ f {\displaystyle Y_{2}=Y_{1}\cup {e}\setminus {f}} も全域木であるから、その重みは Y 1 {\displaystyle Y_{1}} より小さいはずがなく、e の重みは f より小さいはずがない。ここで別の背理法を用いて f の重みが e より小さいはずがないことを証明する。 Y {\displaystyle Y} に追加する辺は常に重みの小さいほうから選んでいた。したがって、 仮に f の重みが e より小さいとすると、f は e より以前に検討されたはずで、 部分森 Y 3 ⊂ Y ∩ Y 1 {\displaystyle Y_{3}\subset Y\cap Y_{1}} への追加をするか調べたはずである（e は Y 1 {\displaystyle Y_{1}} に含まれない辺の中で Y {\displaystyle Y} に最初に追加された辺であるため、 Y {\displaystyle Y} を形成する過程で e を追加する前の段階の Y {\displaystyle Y} の部分森は Y 1 {\displaystyle Y_{1}} の部分森でもある）。しかし f は Y 1 {\displaystyle Y_{1}} で閉路を形成していないので、 Y 3 {\displaystyle Y_{3}} においても閉路を形成しないはずであり、木に追加されていたはずである。これは、 f が Y {\displaystyle Y} に含まれない辺であるということに反する。よって、f の重みは e より小さいことはない。 以上により、 e と f は同じ重みであることが示される。したがって Y 2 {\displaystyle Y_{2}} も最小全域木である。しかし Y 2 {\displaystyle Y_{2}} は Y 1 {\displaystyle Y_{1}} よりも Y {\displaystyle Y} と共通する辺が1つ多い。これは Y 1 {\displaystyle Y_{1}} の定義と矛盾する。（証明終）
※この「最小性」の解説は、「クラスカル法」の解説の一部です。
「最小性」を含む「クラスカル法」の記事については、「クラスカル法」の概要を参照ください。
- 最小性のページへのリンク
