京都大学 情報学研究科 数理工学専攻 2015年8月実施 グラフ理論

Author

祭音Myyura

Description

を節点集合 ，枝集合 から成る連結な単純無向グラフとし，各枝 に実数値の重み を与える．枝の部分集合 は，グラフ が非連結であり，この性質の下で極小であるとき のカットセットと呼ばれる．以下の (i)-(iv) の各命題について，真であれば証明を，偽であれば反例を与えよ．

(i) を の一つのカットセットとし， を の中で枝重みが最小である枝とする．このとき， の任意の最小木は枝 を含む．

(ii) を の一つのカットセットとし， を の中で枝重みが最小である枝とする．このとき， には枝 を含む最小木が存在する．

(iii) を の一つのカットセットとし， を の中で枝重みが最大である枝とする．このとき， には枝 を含まない最小木が存在する．

(iv) を の一つの閉路とし， を の中で枝重みが最小である枝とする．このとき， には枝 を含まぬ最小木が存在する．

Kai

(i)

Counterexample:

(ii)

Let denote a minimum spanning tree of s.t. . Since is a cut-set contains , there exists an edge s.t. is an edge of , otherwise is not connected.

Let . Note that is an edge of of minimum weight, i.e.

which implies that , i.e., is also a minimum spanning tree and .

Therefore, has a minimum spanning tree which contains edge .

(iii)

Counterexample:

(iv)

Counterexample: