CBMS-2015-10

题目来源：Question 10 日期：2024-08-01 题目主题：CS-图论-二分图

Solution

Question 1: Incidence Matrix of the Graph $G$

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:

$$\begin{array}{ccccccccc}& e_1& e_2& e_3& e_4& e_5& e_6& e_7& e_8\\ v_1& 1& 1& 0& 0& 0& 0& 0& 0\\ v_2& 0& 0& 1& 1& 0& 0& 0& 0\\ v_3& 0& 0& 0& 0& 1& 1& 0& 0\\ v_4& 0& 0& 0& 0& 0& 0& 1& 1\\ v_5& 0& 0& 1& 0& 0& 0& 1& 0\\ v_6& 1& 0& 0& 1& 0& 0& 0& 0\\ v_7& 0& 0& 0& 0& 1& 0& 0& 0\\ v_8& 0& 1& 0& 0& 0& 1& 0& 1\end{array}$$

Question 2: Perfect Matchings of $G$

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:

1. $M_1=\{(v_1,v_6),(v_2,v_5),(v_3,v_7),(v_4,v_8)\}$
2. $M_2=\{(v_1,v_8),(v_2,v_6),(v_3,v_7),(v_4,v_5)\}$

Question 3: A Tree is Always a Bipartite Graph

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.

1. 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.

2. Inductive Hypothesis: Remove the leaf node $v$ and the edge $(u,v)$ from $\mathbf{T}$. The resulting graph ${\mathbf{T}}^{\prime }$ is a tree with $n$ vertices. By the induction hypothesis, ${\mathbf{T}}^{\prime }$ is bipartite. Thus, there exists a 2-coloring of ${\mathbf{T}}^{\prime }$ such that no two adjacent vertices share the same color.

3. Coloring $\mathbf{T}$: Extend the 2-coloring from ${\mathbf{T}}^{\prime }$ 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}}^{\prime }$.

   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.

Question 4: A Bipartite Graph Does Not Contain a Circuit with an Odd Number of Edges

Proof:

Assume for contradiction that a bipartite graph contains an odd cycle.

1. 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$.
2. Consider a cycle starting from a vertex $v\in U$. As we traverse the cycle, we must alternate between $U$ and $V$.
3. 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.

知识点

二分图匹配树图论

重点词汇

• Bipartite graph: 二分图
• Incidence matrix: 关联矩阵
• Matching: 匹配
• Perfect matching: 完美匹配
• Tree: 树
• Cycle: 回路

参考资料

1. “Graph Theory with Applications” by Bondy and Murty, Chap. 2
2. “Introduction to Graph Theory” by Douglas B. West, Chap. 1 and 4