東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年8月実施 専門科目II 問題4

Author

zephyr

Description

Consider a connected undirected graph with positive edge weights. A subgraph of obtained by removing some of the edges in is called a spanning tree of , if is a tree. The summation of weights of all the edges in a spanning tree is called the weight of the spanning tree. A minimum spanning tree of is a spanning tree of whose weight is minimum. You can assume appropriate data representation for graphs and trees in the questions below.

Answer the following questions.

(1) Let be the edge (or arbitrary one of the edges if there are multiple such edges) with the maximum weight in some arbitrary cycle in . Prove that there is a minimum spanning tree of that does not contain .

(2) Consider an arbitrary vertex subset of () for . Let be the edge (or arbitrary one of the edges if there are multiple such edges) with the minimum weight among the edges such that and . Prove that there is a minimum spanning tree that contains . Note that denotes an empty set.

(3) Describe an -time algorithm that finds an arbitrary path between two nodes on graph .

(4) Assume that we are given a graph and its minimum spanning tree . Let be the graph obtained by adding to a new edge with weight . Describe an -time algorithm that finds a minimum spanning tree of .

(5) Prove the correctness of the algorithm described in question (4).

---

考虑一个具有正边权的连通无向图 。如果 的一个子图 是一个树，则称其为 的生成树。生成树中所有边的权重之和称为生成树的权重。 的最小生成树是 的一个生成树，其权重最小。你可以在以下问题中假设图和树的适当数据表示。

回答以下问题。

(1) 设 是在 的某个任意循环 中具有最大权重的边（如果有多条这样的边，则任意选取一条）。证明存在一个不包含 的 的最小生成树。

(2) 对于 的任意顶点子集 ()，设 是权重最小的边（如果有多条这样的边，则任意选取一条），该边位于 和 的顶点之间，即 使得 且 。证明存在一个包含 的最小生成树。注意， 表示空集。

(3) 描述一个 时间的算法，用于找到图 上的两个节点 之间的任意路径。

(4) 假设我们给定一个图 及其最小生成树 。设 是通过向 中添加一条新边 ，且权重 得到的图。描述一个 时间的算法，以找到 的一个最小生成树。

(5) 证明问题 (4) 中描述的算法的正确性。

Kai

(1)

Let be an arbitrary cycle in , and let be the edge in with the maximum weight. We need to prove that there exists a minimum spanning tree (MST) that does not contain .

Proof

• Step 1: Assume is an MST that contains .
• Step 2: Consider the cycle in that includes . Since is a tree and contains all vertices of , adding to will create a cycle.
• Step 3: In the cycle , remove the edge (which has the maximum weight in ) to break the cycle, forming a new tree . Since we removed the edge with the maximum weight, has a smaller or equal total weight compared to .
• Step 4: Conclude that is also an MST, but it does not contain .

Therefore, there exists a minimum spanning tree that does not contain the edge .

(2)

Consider an arbitrary vertex subset of (). Let be the edge with the minimum weight among the edges such that and . We need to prove that there is a minimum spanning tree that contains .

Proof

• Step 1: Apply the Cut Property.** According to the Cut Property, for any cut in the graph, the minimum weight edge crossing the cut must be in the MST.
• Step 2: Define the cut associated with as the set of edges where and .
• Step 3: Since is the minimum weight edge across this cut, by the Cut Property, must be included in every MST of .

Thus, there is a minimum spanning tree that contains the edge .

(3)

Describe an -time algorithm that finds an arbitrary path between two nodes on graph .

Algorithm

1. Initialization: Initialize a stack (or queue) and mark all vertices as unvisited.
2. Depth-First Search (DFS):
   • Push the starting vertex onto the stack and mark it as visited.
   • While the stack is not empty:
     • Pop a vertex from the stack.
     • If , return the path from to .
     • For each adjacent vertex of that is not visited, push onto the stack and mark it as visited.
3. Termination: If the search ends without finding , return "No Path".

This algorithm runs in time because in the worst case, it visits each edge once.

(4)

Assume that we are given a graph and its minimum spanning tree . Let be the graph obtained by adding to a new edge with weight . Describe an -time algorithm that finds a minimum spanning tree of .

Algorithm

1. Step 1: Add the new edge to the MST . This will create a cycle in the tree.
2. Step 2: Find the maximum weight edge in this cycle.
3. Step 3: If , then the original MST is still valid.
4. Step 4: If , remove from the cycle. The resulting graph is a tree and is the new MST.

The time complexity is because finding the cycle in a tree and identifying the maximum weight edge in the cycle can be done in linear time.

(5)

Prove the correctness of the algorithm described in question (4).

Proof

• Step 1: Adding edge to the MST creates exactly one cycle, as was a tree.
• Step 2: In the cycle, removing the maximum weight edge ensures that the resulting graph is still a tree with a total weight less than or equal to the original MST.
• Step 3: If , then must be removed to maintain the minimality of the spanning tree, as introduces a smaller weight.
• Step 4: This process guarantees that the resulting tree is the MST of , thus proving the algorithm's correctness.

Knowledge

最小生成树 图论 DFS BFS 贪心算法

解题技巧和信息

• 最小生成树的关键性质可以通过切割定理和环路定理进行理解。
• 对于图中的路径查找问题，DFS 和 BFS 都是常用的线性时间算法。
• 解决最小生成树更新问题时，可以通过引入新边后检查形成的环并删除最大边的方式实现最小生成树的维护。

重点词汇

• Minimum Spanning Tree (MST) 最小生成树
• Cycle 环
• Cut Property 切割定理
• Depth-First Search (DFS) 深度优先搜索
• Breadth-First Search (BFS) 广度优先搜索

参考资料

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chap. 23: Minimum Spanning Trees.
2. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. Sections on Graph Algorithms.