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

标签：

• Kyoto-University
• Minimum-Spanning-Tree
• Mathematics.Graph-Theory.Kruskal-Algorithm

Author

祭音Myyura

Description

English Version

Let be the set of non-negative reals, and let be a network that consists of a simple connected graph and an edge weight function

Let .

For a partition

of , let denote the set of edges between distinct vertex subsets . Denote by the set of all partitions of .

Let

be a minimum spanning tree obtained from by Kruskal's algorithm, where is added to as the -th tree edge.

For forests

and

let , , be the partition formed by the connected components of the forest , where

Choose a real value for each partition as follows:

and

Answer the following questions.

(i) Give a description of Kruskal's algorithm to find a minimum spanning tree of .

(ii) Prove that each edge admits an index

which satisfies the conditions:

and

(iii) Prove that

holds for each .

(iv) Prove that

holds for each .

(v) Prove that

holds for each edge .

Kai

(i)

Kruskal's algorithm sorts all edges in non-decreasing order of their weights. Starting from the empty forest , it scans the edges in this order. Whenever the current edge connects two different connected components of the current forest, the edge is added. If the current edge would create a cycle, it is skipped. The algorithm stops when edges have been added. The resulting graph is a minimum spanning tree.

(ii)

Let be any edge.

For each , the partition is the partition of into the connected components of the forest .

Therefore,

if and only if the two endpoints and of belong to different connected components of .

As increases, the forest gains more edges. Hence connected components can only merge; they never split. Therefore, once and become contained in the same connected component, they remain in the same connected component for all later forests.

Thus, the sequence of truth values of the condition has the following form:

Since , every edge has endpoints in different connected components of . Hence

Since is a spanning tree, all vertices are in one connected component. Hence

Therefore the following maximum

is well-defined and satisfies

Then, by the monotonicity of connected components, we have

(iii)

Fix .

At the beginning of the -th step of Kruskal's algorithm, the current forest is

Let . Then the endpoints of belong to two distinct connected components of . Hence adding to would not create a cycle.

Thus is an admissible edge at the -th step of Kruskal's algorithm.

By Kruskal's rule, is chosen as a minimum-weight admissible edge at this step. Therefore,

Since was arbitrary, we have

(iv)

When , we have

So the claim holds.

Now suppose . By the definition of ,

and

Hence

(v)

Let be arbitrary.

By part (ii), there exists an index such that

Moreover, by the definition of , the only partitions that may have nonzero -values are

Therefore,

By part (iv), taking , we obtain

Since , part (iii), applied with , gives

Therefore,

Thus,

holds for every edge .