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

Author

祭音Myyura

Description

日本語版

を節点集合 ，枝集合 から成る連結な単純無向グラフとし，各枝 には実数値の重み が与えられているとする． の全域木 に対して，補木の枝 を含む の基本閉路を ，木の枝 を含む の基本カットセットを と書く．以下の問いに答えよ．

(i) の全域木 が最小木であるとき，次の条件(C)が成り立つことを証明せよ．

条件(C): 補木の任意の枝 とその基本閉路の各枝 に対して が成り立つ．

(ii) 条件(C)を満たす任意の全域木 は次の条件(K)を満たすことを証明せよ．

条件(K): 全域木 の任意の枝 とその基本カットセットの各枝 に対して が成り立つ．

(iii) の全域木 に対して条件(K)が成り立つとき， は最小木であることを証明せよ．

(iv) 次の命題が真であれば証明を，偽であれば反例を与えよ．

「 が最小木を二つ持つとき， には同じ重みを持つ枝が少なくとも２本存在する．」

English Version

Let denote a simple and connected undirected graph with a vertex set and an edge set such that each edge is weighted by a real value . For a spanning tree of , let denote the fundamental cycle containing an edge , and denote the fundamental cut-set containing an edge . Answer the following questions.

(i) Prove that every minimum spanning tree of satisfies the next condition (C).

(C): For every edge each edge satisfies .

(ii) Prove that any spanning tree satisfying condition (C) also satisfies the next condition (K).

(K): For every edge , each edge satisfies .

(iii) Prove that any spanning tree of satisfying condition (K) is a minimum spanning tree.

(iv) Prove or disprove the next proposition, giving a proof or a counterexample.

"When has two minimum spanning trees, some two edges in have the same weight."

Kai

(i)

Assume that for an edge there exists an edge such that .

Let be a tree constructed by substituting edge with edge . It is obviously that is a spanning tree and

which is contradictory to the fact that is a minimum spanning tree.

Therefore, for every edge each edge satisfies .

(ii)

Assume that for an edge , there exists an edge such that .

Let be a tree constructed by substituting edge with edge . By definition of fundamental cut-set we know that the removal of disconnects into exactly two components and and edge connects the two components. Thus is a spanning tree and

which is contradictory to the fact that is a minimum spanning tree.

Therefore, For every edge , each edge satisfies .

(iii)

Let denote a spanning tree of that satisfy condition (K). Let denote a minimum spanning tree of .

Suppose that . Then there exists an edge .

Consider the fundamental cut-set , since is connected, there must exist an edge and .

Let , by condition (C) we have

and

which means that, compared to , is "closer" to .

Continue the above process until we get a spanning tree , then we have

that is, spanning tree is a minimum spanning tree.

(iv)

Let and are two distinct minimum spanning trees of , assume that edges' weights of are distinct.

Consider the edge of minimum weight among all the edges that are contained in exactly one of or . W.l.o.g we assume that .

Then, consider the fundamental cycle of , there exists an edge but . By assumption we know that .

Note that is a spanning tree and we have

which is contradictory to the fact that is a minimum spanning tree.

Therefore, when has two minimum spanning trees, some two edges in have the same weight.