東京大学 新領域創成科学研究科 メディカル情報生命専攻 2014年8月実施 問題10
Author
Description
A bipartite graph is an undirected graph whose nodes can be divided into two groups such that any two nodes in a group are not connected by an edge. Answer the following questions about bipartite graphs.
(1) Write the incidence matrix of the following graph \(G\).
(2) A matching in a graph is a set of edges without common nodes. A perfect matching is a matching that covers all nodes of the graph. List all perfect matchings of \(G\).
(3) Prove that a tree is always a bipartite graph.
(4) Prove that a bipartite graph does not contain a circuit with an odd number of edges.
二分图是一个无向图，其节点可以分为两组，使得组内的任意两个节点不通过边连接。回答以下关于二分图的问题。
(1) 写出以下图 \(G\) 的关联矩阵。
(2) 图中的一个匹配是一组没有公共节点的边。完美匹配是覆盖图中所有节点的匹配。列出图 \(G\) 的所有完美匹配。
(3) 证明树总是一个二分图。
(4) 证明二分图不包含奇数条边的回路。
Kai
(1)
The incidence matrix of a graph is a matrix with rows representing the vertices and columns representing the edges, where the entry is 1 if the vertex is incident to the edge, and 0 otherwise.
For the given bipartite graph \(G\):
Vertices in group 1 (BLACK_NODES): \(v_1, v_2, v_3, v_4\)
Vertices in group 2 (WHITE_NODES): \(v_5, v_6, v_7, v_8\)
Edges:
- \(e_1 = (v_1, v_6)\)
- \(e_2 = (v_1, v_8)\)
- \(e_3 = (v_2, v_5)\)
- \(e_4 = (v_2, v_6)\)
- \(e_5 = (v_3, v_7)\)
- \(e_6 = (v_3, v_8)\)
- \(e_7 = (v_4, v_5)\)
- \(e_8 = (v_4, v_8)\)
The incidence matrix M is:
(2)
A perfect matching in a bipartite graph is a matching that covers all vertices, meaning every vertex is connected to exactly one edge in the matching. For graph \(G\), we find all sets of edges such that each vertex is matched exactly once:
- \(M_1 = \{(v_1, v_6), (v_2, v_5), (v_3, v_7), (v_4, v_8)\}\)
- \(M_2 = \{(v_1, v_8), (v_2, v_6), (v_3, v_7), (v_4, v_5)\}\)
(3)
Proof:
To prove that any tree is a bipartite graph, we need to show that its vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent. We use the method of 2-coloring and mathematical induction to establish this.
Base Case: A tree with a single vertex (trivial tree) is bipartite, as it can be divided into two sets where one set is empty and the other contains the single vertex. Thus, it can trivially be colored using two colors.
Inductive Step: Assume that all trees with \(n\) vertices are bipartite. We will prove that a tree with \(n+1\) vertices is also bipartite.
-
Graph Structure: Let \(\mathbf{T} = (V, E)\) be a tree with \(n+1\) vertices. Since \(\mathbf{T}\) is a tree, it is connected and acyclic by definition. Let \(v\) be a leaf node of \(\mathbf{T}\) (a vertex with degree 1) and \(u\) be its parent.
-
Inductive Hypothesis: Remove the leaf node \(v\) and the edge \((u, v)\) from \(\mathbf{T}\). The resulting graph \(\mathbf{T}'\) is a tree with \(n\) vertices. By the induction hypothesis, \(\mathbf{T}'\) is bipartite. Thus, there exists a 2-coloring of \(\mathbf{T}'\) such that no two adjacent vertices share the same color.
-
Coloring \(\mathbf{T}\): Extend the 2-coloring from \(\mathbf{T}'\) to \(\mathbf{T}\) by assigning to \(v\) the opposite color of \(u\). This extension is valid because:
- \(v\) is only adjacent to \(u\) (since \(v\) is a leaf).
- \(u\) was already assigned a color in \(\mathbf{T}'\).
Thus, \(\mathbf{T}\) can be colored using two colors without any two adjacent vertices sharing the same color.
Conclusion: Since the base case holds and the inductive step shows that if any tree with \(n\) vertices is bipartite, then any tree with \(n+1\) vertices is also bipartite, by mathematical induction, all trees are bipartite graphs. This means that the vertex set of any tree can be partitioned into two sets where no two vertices within the same set are adjacent.
(4)
Proof:
Assume for contradiction that a bipartite graph contains an odd cycle.
- In a bipartite graph, the vertices can be divided into two sets, \(U\) and \(V\), where every edge connects a vertex from \(U\) to \(V\).
- Consider a cycle starting from a vertex \(v \in U\). As we traverse the cycle, we must alternate between \(U\) and \(V\).
- If the cycle length is odd, then when we return to the starting vertex \(v \in U\), we should have traversed an even number of edges to reach a vertex in \(U\), as every two steps should take us back to a vertex in the same set.
However, since the cycle is odd, an odd number of edges would require the last vertex to be in the opposite set (i.e., in \(V\) if starting from \(U\)), contradicting the assumption that the cycle is closed and returns to \(v \in U\).
Thus, a bipartite graph cannot contain an odd cycle.
Knowledge
二分图 匹配 树 图论
重点词汇
- Bipartite graph: 二分图
- Incidence matrix: 关联矩阵
- Matching: 匹配
- Perfect matching: 完美匹配
- Tree: 树
- Cycle: 回路
参考资料
- "Graph Theory with Applications" by Bondy and Murty, Chap. 2
- "Introduction to Graph Theory" by Douglas B. West, Chap. 1 and 4