東京大学 新領域創成科学研究科 メディカル情報生命専攻 2017年8月実施 問題10
Author
Description
Answer the following questions regarding graphs.
(1) Prove that the sum of the vertex degrees of an undirected graph is equal to the number of edges times two.
(2) Prove the following proposition: If a graph \(\mathbf{G(V, E)}\) with vertex set \(\mathbf{V}\) and edge set \(\mathbf{E}\) is a tree, \(\left| \mathbf{E} \right| = \left| \mathbf{V} \right| - 1\).
(3) Given an undirected graph \(\mathbf{G(V, E)}\) and a set of edges \(\mathbf{T \subseteq E}\), the graph \(\mathbf{S(V, T)}\) is called a spanning tree, if \(\mathbf{S}\) is a tree. Among all spanning trees of a weighted graph, those with the minimum sum of weights are called minimum spanning trees. Show a minimum spanning tree of the following graph.
(4) Assume that \(\mathbf{S(V, T)}\) and \(\mathbf{S'(V, T')}\) are different spanning trees of graph \(\mathbf{G}\). Prove the following proposition: For any edge \(\mathbf{e' \in T' - T}\), there is an edge \(\mathbf{e \in T - T'}\) such that \((\mathbf{T - \{e\}}) \cup \{\mathbf{e'}\}\) forms a spanning tree.
回答以下关于图的问题。
(1) 证明无向图的顶点度数之和等于边数的两倍。
(2) 证明以下命题：如果图 \(\mathbf{G(V, E)}\) 的顶点集 \(\mathbf{V}\) 和边集 \(\mathbf{E}\) 是一棵树，那么 \(\left| \mathbf{E} \right| = \left| \mathbf{V} \right| - 1\)。
(3) 给定一个无向图 \(\mathbf{G(V, E)}\) 和一组边 \(\mathbf{T \subseteq E}\)，如果 \(\mathbf{S}\) 是一棵树，则图 \(\mathbf{S(V, T)}\) 称为生成树。在所有加权图的生成树中，权重和最小的称为最小生成树。展示下图的最小生成树。
(4) 假设图 \(\mathbf{G}\) 的生成树 \(\mathbf{S(V, T)}\) 和 \(\mathbf{S'(V, T')}\) 不同。证明以下命题：对于 \(\mathbf{T' - T}\) 中的任何边 \(\mathbf{e'}\)，存在 \(\mathbf{T - T'}\) 中的边 \(\mathbf{e}\) 使得 \((\mathbf{T - \{e\}}) \cup \{\mathbf{e'}\}\) 形成一棵生成树。
Kai
(1)
In an undirected graph \(\mathbf{G(V, E)}\), each edge \(\mathbf{e} \in \mathbf{E}\) connects two vertices, contributing to the degree of both vertices. Therefore, each edge increases the sum of the vertex degrees by 2. Mathematically,
where \(\deg(v)\) denotes the degree of vertex \(v\), and \(\left| \mathbf{E} \right|\) denotes the number of edges. This is known as the Handshaking Lemma.
(2)
A tree is a connected acyclic graph. For a graph \(\mathbf{G(V, E)}\) to be a tree, it must satisfy the following properties:
- It is connected.
- It contains no cycles.
- The number of edges \(\left| \mathbf{E} \right| = \left| \mathbf{V} \right| - 1\).
To prove this, we use induction on the number of vertices \(\left| \mathbf{V} \right|\).
Base Case: For \(\left| \mathbf{V} \right| = 1\), there are no edges, so \(\left| \mathbf{E} \right| = 0 = 1 - 1\).
Inductive Step: Assume the statement is true for a tree with \(n\) vertices, i.e., it has \(n-1\) edges. Consider adding a new vertex \(v\) to the tree. To maintain the tree properties, \(v\) must be connected to exactly one existing vertex, adding one new edge. Thus, the new tree has \(n+1\) vertices and \(n\) edges, maintaining the property \(\left| \mathbf{E} \right| = \left| \mathbf{V} \right| - 1\).
Hence, by induction, the proposition is proved.
(3)
To find the minimum spanning tree, we can use Kruskal's algorithm or Prim's algorithm. Here, we will use Kruskal's algorithm.
- Sort the edges by weight:
- A-C (2)
- B-D (4)
- D-E (4)
- A-B (5)
- B-C (7)
- B-E (8)
-
C-E (9)
-
Select edges in order of weight, ensuring no cycles are formed:
- A-C (2)
- B-D (4)
- D-E (4)
- A-B (5)
Thus, the minimum spanning tree includes edges A-C, B-D, D-E, and A-B.
(4)
Given two different spanning trees \(\mathbf{S(V, T)}\) and \(\mathbf{S'(V, T')}\) of graph \(\mathbf{G}\), and an edge \(\mathbf{e' \in T' - T}\), consider adding \(\mathbf{e'}\) to \(\mathbf{S(V, T)}\). This addition creates exactly one cycle, since \(\mathbf{S(V, T)}\) is initially acyclic.
In this cycle, there must be at least one edge \(\mathbf{e}\) that is in \(\mathbf{T}\) but not in \(\mathbf{T'}\) (because if every edge in the cycle were in \(\mathbf{T}\), \(\mathbf{e'}\) would not be in the cycle). Removing this edge \(\mathbf{e}\) from \(\mathbf{T}\) breaks the cycle, restoring the tree property.
Therefore, \((\mathbf{T - \{e\}}) \cup \{\mathbf{e'}\}\) forms a spanning tree.
Knowledge
图论 最小生成树 Kruskal算法 数学归纳法
重点词汇
- vertex 顶点
- edge 边
- degree 度
- spanning tree 生成树
- minimum spanning tree 最小生成树
- cycle 环
参考资料
- "Introduction to Graph Theory" by Douglas B. West, Chapter 1
- "Graph Theory with Applications" by Bondy and Murty, Section 2.1