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

标签：

• Kyoto-University
• Minimum-Spanning-Tree
• Prim-Algorithm

Author

祭音Myyura

Description

日本語版

$G$ を点集合 $V$，枝集合 $E$ から成る単純連結無向グラフとし，各枝 $e\in E$ には実数値の重み $w(e)$ が付与されている． 点の部分集合 $X \subseteq V$ に対し $X$ と $V \setminus X$ の間の枝の集合を $E(X)$ と記す． 枝の部分集合 $S \subseteq E$ に対して $w(S) \triangleq \sum_{e \in S} w(e)$, $w_{\text{max}} (S) \triangleq \max_{e \in S} w(e)$ と定める．以下の問いに答えよ．

(i) $(X, F)$, $X \neq V$ を $G$ の部分木とし，$G$ の最小木には木 $(X, F)$ を含むものが存在すると仮定する．$a_F = uv \in E(X)$ を $E(X)$ の中で重み最小の枝とする．このとき $G$ の最小木には $(X \cup \{u, v\}, F \cup \{a_F\})$ を含むものが存在することを証明せよ．

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

(iii) $(V, T^*)$ を $G$ の最小木とする．このとき $G$ の任意の全域木 $(V, T)$ に対して $w_{\text{max}}(T^*) \le w_{\text{max}}(T)$ が成り立つことを証明せよ．

English Version

Let $G$ be a simple and connected undirected graph with a vertex set $V$ and an edge set $E$ such that each edge $e\in E$ is weighted by a real value $w(e)$. For a subset $X \subseteq V$ of vertices, let $E(X)$ denote the set of edges between $X$ and $V \setminus X$. For a subset $S \subseteq E$ of edges, define $w(S) \triangleq \sum_{e \in S} w(e)$ and $w_{\text{max}} (S) \triangleq \max_{e \in S} w(e)$. Answer the following questions.

(i) Let $(X, F)$, $X \neq V$ be a subtree of $G$ and assume that one of the minimum spanning trees of $G$ contains the tree $(X, F)$. Let $a_F = uv \in E(X)$ be an edge with the minimum weight among the edges in $E(X)$. Prove that one of the minimum spanning trees of $G$ contains $(X \cup \{u, v\}, F \cup \{a_F\})$

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

(iii) Let $(V, T^*)$ be a minimum spanning tree of $G$. Prove that $w_{\text{max}}(T^*) \le w_{\text{max}}(T)$ holds for every spanning tree $(V, T)$ of $G$.

题目描述

设 $G=(V,E)$ 为带实数边权 $w(e)$ 的简单连通无向图。对 $X\subseteq V$，令 $E(X)$ 为连接 $X$ 与 $V\setminus X$ 的边集；对 $S\subseteq E$，定义

$$w(S)=\sum_{e\in S}w(e),\qquad w_{\max}(S)=\max_{e\in S}w(e).$$

回答：

1. 设 $(X,F)$（$X\ne V$）是 $G$ 的一棵子树，并假设某棵最小生成树包含 $(X,F)$。令 $a_F=uv\in E(X)$ 为 $E(X)$ 中权重最小的边。证明存在一棵最小生成树包含 $(X\cup\{u,v\},F\cup\{a_F\})$。
2. 描述求最小生成树的 Prim 算法，并证明其正确性。
3. 设 $(V,T^*)$ 是最小生成树。证明对任意生成树 $(V,T)$，
   $$w_{\max}(T^*)\le w_{\max}(T).$$

考点

• 最小生成树的割性质：用交换论证证明扩展当前子树时选择跨割最轻边仍能嵌入某棵最小生成树。
• Prim 算法正确性：以逐步保持“当前树包含于某棵最小生成树”的不变量完成证明。
• 最小瓶颈生成树性质：证明最小生成树同时最小化所用边中的最大权重。

Kai

(i)

Let $T^* = (V, E^*)$ be one minimum spanning tree that contains the tree $(X, F)$.

If $a_F \in E^*$, then $T^*$ itself contains $(X\cup{u,v},F\cup{a_F})$, so there is nothing to prove.

Since $a_F \notin E^*$, the graph $T^* \cup a_f$ contains a cycle $C$ (called the fundamental cycle of $a_f$). Hence along the cycle $C$, there must be another edge $b \neq a_F$ that also cross the same cut, i.e.,

$$b \in E^* \cap E(X)$$

We substitute edge $b$ by edge $a_F$ and let $T'$ denote the tree after substitution, i.e. $T' = (V, E^* \cup \{a_F\} \setminus \{b\})$.

Since $a_F \in E(X)$ is an edge with the minimum weight among the edges in $E(X)$, we know that $w(a_F) \le w(b)$.

Hence

$$w(T') = w(T^*) - w(b) + w(a_F) \le w(T^*).$$

Hence $T'$ is a minimum spanning tree of $G$ contains $(X \cup \{u, v\}, F \cup \{a_F\})$

(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 $T$ is a subgraph of some minimum spanning tree $T^*$.

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

Suppose that at some point in the algorithm we have $T = (X, F)$ which a subgraph of some minimum spanning tree $T^*$. Since the Prim's algorithm finds an edge $e = uv \in E(X)$ of minimum weight, from (i) we know that there exists a minimum spanning tree of $G$ that contains $(X \cup \{u, v\}, F \cup \{e\})$. Therefore the induction hypothesis is preserved after this iteration.

When the algorithm terminates, we have $X=V$. Since one new vertex and one new edge are added in each iteration, $F$ has $|V|-1$ edges and $(V,F)$ is a spanning tree. By the induction argument, $(V,F)$ is contained in some minimum spanning tree. Therefore Prim’s algorithm correctly outputs a minimum spanning tree of $G$.

(iii)

Prove by contradiction: Assume that there exists a spanning tree $T' = (V, E')$ of $G$ such that $w_{\text{max}}(T^*) > w_{\text{max}}(E')$. Obviously $T^* \neq E'$.

Let $e^{*}_{\max}=uv$ be an edge of maximum weight in $T^*$. The graph $T' \cup \{e^{*}_{\max}\}$ contains a cycle $C(e^{*}_{\max})$ (called the fundamental cycle of $e^{*}_{\max}$ with respect to $T'$).

Since $w_{\text{max}}(T^*) > w_{\text{max}}(E')$, for every edge $e \in C(e^{*}_{\max}), e \neq e^{*}_{\max}$ we have

$$w(e) \le w_{\text{max}}(E') < w_{\text{max}}(T^*) = w(e^{*}_{\max})$$

Since $C(e^{*}_{\max}) \setminus \{e^{*}_{\max}\}$ is a path from $u$ to $v$ in $T'$, there exists an edge $f \in C(e^{*}_{\max})\setminus \{e^{*}_{\max}\}$ that connects $T^* \setminus \{e^{*}_{\max}\}$.

Then we have

$$w(T^* \setminus \{e^{*}_{\max}\} + \{f\}) = w(T^*) - w(e^{*}_{\max}) + w(f) <w(T^*)$$

i.e. the tree $T^* \setminus \{e^{*}_{\max}\} + \{f\}$ is a spanning tree of lower weight than $T^*$, a contradiction.