東京大学 新領域創成科学研究科 メディカル情報生命専攻 2018年8月実施 問題10

Author

zephyr

Description

Answer the following questions regarding undirected graphs. A simple graph is a graph that does not contain any multi-edges or self-loops. A walk is defined as a connected sequence of edges.

(1) Prove that, for any graph , the number of nodes whose degree is odd is always even.

(2) Write the adjacency matrix of the following graph, and show that the number of walks of length 2 between nodes 1 and 4 is equal to the -element of .

  1 -- 2
  | \  |
  |  \ |
  3 -- 4

(3) Prove that, for any simple graph with some adjacency matrix , the number of walks of length between nodes is equal to the element of .

(4) Assume that a simple connected graph has two or more nodes. Prove that has at least two nodes with identical degree.

---

回答以下关于无向图的问题。简单图是指不包含任何多重边或自环的图。行走被定义为边的连接序列。

(1) 证明对于任何图 ，度数为奇数的节点数总是偶数。

(2) 写出以下图的邻接矩阵 ，并证明节点 1 和 4 之间长度为 2 的路径数等于 的 元素。

  1 -- 2
  | \  |
  |  \ |
  3 -- 4

(3) 证明对于任何具有某个邻接矩阵 的简单图 ，节点 之间长度为 的路径数等于 的 元素。

(4) 假设一个简单连通图 有两个或更多节点。证明 至少有两个度数相同的节点。

Kai

(1)

To prove this statement, we will use the Handshaking Lemma, which states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges. Mathematically, for a graph with vertices and edges , we have:

where is the degree of vertex .

Now, consider the sum of the degrees of all vertices. Each degree is either even or odd. Let's denote the number of vertices with odd degree as and the number of vertices with even degree as . Therefore, we have:

Since the sum of the degrees is even (because it equals ), and the sum of an even number of even numbers is even, the sum of an even number of odd numbers is also even. Therefore, the number of odd-degree vertices, , must be even.

Thus, the number of nodes whose degree is odd is always even.

(2)

The given graph is:

  1 -- 2
  | \  |
  |  \ |
  3 -- 4

The adjacency matrix of this graph is:

To find the number of walks of length 2 between nodes 1 and 4, we need to compute the matrix :

The -element of is 3, which means there are 3 walks of length 2 between nodes 1 and 4. The walks are:

(3)

We use induction on to prove this statement.

Base case: For , the number of walks of length 1 between nodes and is given by the adjacency matrix . If there is an edge between and , then , otherwise . Hence, the number of walks of length 1 between nodes and is , which is the element of .

Inductive step: Assume the statement is true for , i.e., the number of walks of length between nodes and is the element of . We need to show it is true for .

The number of walks of length from node to node is the sum of the walks of length from to all intermediate nodes and then taking one step from to . Mathematically, this is:

This is precisely the matrix multiplication of and , and the result is the element of .

By induction, the number of walks of length between nodes and is equal to the element of for all .

(4)

This proof uses the Pigeonhole Principle.

Let be a simple connected graph with nodes where . The degree of a node (vertex) in a simple graph can range from to . In a connected graph with , no node can have degree 0, so the possible degrees range from to .

However, we now have vertices but only different possible degrees. According to the Pigeonhole Principle, if we assign different items (in this case, vertices) into different categories (possible degrees), at least one category must contain more than one item.

Therefore, there must be at least two vertices in the graph that share the same degree.

Knowledge

图论 邻接矩阵 鸽巢原理 抽屉原理 数学归纳法

重点词汇

• degree 度
• adjacency matrix 邻接矩阵
• walk 步长
• connected 连通
• simple graph 简单图
• pigeonhole principle 鸽巢原理

参考资料

1. "Introduction to Graph Theory" by Douglas B. West, Chap. 1 and 2
2. "Discrete Mathematics and Its Applications" by Kenneth H. Rosen, Chap. 10