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

Author

祭音Myyura

Description

日本語版

を点集合 ，枝集合 から成る単純連結無向グラフとし，各枝 には実数値の重み が付与されている． 点の部分集合 に対し と の間の枝の集合を と記す． 枝の部分集合 に対して , と定める．以下の問いに答えよ．

(i) , を の部分木とし， の最小木には木 を含むものが存在すると仮定する． を の中で重み最小の枝とする．このとき の最小木には を含むものが存在することを証明せよ．

(ii) 最小木を求めるプリム法を記述し，その正当性を証明せよ．

(iii) を の最小木とする．このとき の任意の全域木 に対して が成り立つことを証明せよ．

English Version

Let be 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 subset of vertices, let denote the set of edges between and . For a subset of edges, define and . Answer the following questions.

(i) Let , be a subtree of and assume that one of the minimum spanning trees of contains the tree . Let be an edge with the minimum weight among the edges in . Prove that one of the minimum spanning trees of contains

(ii) Describe Prim’s method for computing a minimum spanning tree and prove its correctness.

(iii) Let be a minimum spanning tree of . Prove that holds for every spanning tree of .

Kai

(i)

Let be one minimum spanning tree that contains the tree .

From the connectivity of , we know that there exists an edge that connects and , i.e. . We substitute edge by edge and let denote thetree after substitution, i.e. .

Since is an edge with the minimum weight among the edges in , we know that .

Hence

Hence is a minimum spanning tree of contains

(ii)

PrimAlgorithm(G=(V, E)):
    choose an arbitrary vertex s in V
    F = {}
    X = {s}
    while X is not equal to V do:
        find an edge e = uv (u in X and v in V\X) of minimum weight among E(X)
        F = F + {e}
        X = X + {v}
    
    output F

We prove the correctness of Prim's algorithm by induction.

The induction hypothesis will be that after each iteration, the tree is a subgraph of some minimum spanning tree .

This is trivially true at the start, since initially is just a single node and no edges.

Suppose that at some point in the algorithm we have which a subgraph of some minimum spanning tree . Since the Prim's algorithm finds an edge of minimum weight, from (i) we know that there exists a minimum spanning tree of that contains . This maintains the induction, so proves the correctness.

(iii)

Prove by contradiction: Assume that there exists a spanning tree of such that . Obviously .

Let be an edge of maximum weight in . The graph contains a cycle (called the fundamental cycle of with respect to ).

Since , for every edge we have

Since is a path from to in , there exists an edge that connects .

Then we have

i.e. the tree is a spanning tree of lower weight than , a contradiction.