跳到主要内容

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

Author​

zephyr

Description​

In a directed graph, a path is a series of one or more arcs that connect a series of vertices. A cycle is a path that starts and ends on the same vertex. An Eulerian path (cycle, respectively) is a path (cycle) that visits every arc exactly once.

Next, we create a directed graph from string . Let denote , the substring of length that starts from position in . Let denote a directed graph such that the vertex set is , and the set of labeled arcs is , The 3rd argument is the label. Answer the following questions.

(1) When , the vertex set and labeled arc set of are and , respectively. List all Eulerian paths and cycles in .

(2) When , list all Eulerian paths and cycles in each of and .

(3) A vertex is balanced if the number of arcs entering the vertex is equal to the number of arcs leaving the vertex. A directed graph is balanced if every vertex is balanced. A directed graph is connected if it has a path from any vertex to any vertex. Prove that a directed graph with an Eulerian cycle is connected and balanced.

(4) Conversely, if a graph is connected and balanced, prove that the graph has an Eulerian cycle.

在有向图中，一条路径是连接一系列顶点的一条或多条弧。一个环是起点和终点在同一个顶点的路径。欧拉路径（或环）是一条恰好遍历每条弧一次的路径（或环）。

接下来，我们从字符串 创建一个有向图。令 表示从 中位置 开始的长度为 的子串 。令 表示一个有向图，其顶点集为 ，标记弧的集合为 ，第三个参数 是标签。回答以下问题。

(1) 当 时， 的顶点集和标记弧集分别为 和 。列出 中的所有欧拉路径和环。

(2) 当 时，列出 和 中的所有欧拉路径和环。

(3) 如果一个顶点的进入弧的数量等于离开弧的数量，则该顶点是平衡的。如果每个顶点都是平衡的，则有向图是平衡的。如果有向图从任意顶点到任意顶点都有路径，则它是连通的。证明一个有欧拉环的有向图是连通且平衡的。

(4) 反之，如果一个图是连通且平衡的，证明该图有一个欧拉环。

Kai​

(1)​

Given , we construct as follows:

Vertex set:

Labeled arc set:

To find all Eulerian paths and cycles, we need to traverse all arcs exactly once.

Eulerian paths:

There are no Eulerian cycles in .

(2)​

For ​

Vertex set:

Labeled arc set:

Eulerian cycle (also as Eulerian path):

For ​

Vertex set:

Labeled arc set:

Eulerian path:

There are no Eulerian cycles in .

(3)​

Let be a directed graph with an Eulerian cycle .

Note: We assume that does not contain any isolated vertices (vertices with both in-degree and out-degree equal to 0), or if such vertices exist, we consider them as irrelevant to the Eulerian cycle and the properties we are about to prove.

Connectedness​

Suppose is not connected. Then there exist vertices such that there is no path from to . However, the Eulerian cycle visits every edge in exactly once, which means it visits every non-isolated vertex at least once. Therefore, provides a path from to , contradicting our assumption. Thus, must be connected.

Balance​

Let be any non-isolated vertex in . Every time the Eulerian cycle enters , it must also leave , including the starting/ending vertex which is entered in the last step of the cycle. Therefore, the number of edges entering is equal to the number of edges leaving . Since this is true for all non-isolated vertices, is balanced.

(4)​

Let be a connected and balanced directed graph. We will prove this by constructing an Eulerian cycle.

  1. Start at any vertex .
  2. Choose any outgoing arc and follow it to the next vertex.
  3. Continue this process, each time choosing an unused arc, until we return to .

This process must terminate because:

a) The graph is balanced, so we can always leave a vertex we've entered (except possibly ).

b) The number of arcs is finite, so we must eventually return to .

Let's call the cycle we've constructed . If includes all arcs in , we're done. If not, consider the subgraph where is the set of vertices incident to unused arcs, and is the set of unused arcs.

  1. is balanced: The balance of vertices in is unaffected by removing the equal number of incoming and outgoing arcs in .
  2. is connected to : If it weren't, would not be connected.

Choose a vertex in that's also in . Start a new cycle from in using the same process as before. We can then combine and into a larger cycle.

Repeat this process until all arcs are used. The result is an Eulerian cycle in .

Knowledge​

图论 欧拉路径 有向图 连通性 平衡性

难点思路​

  1. 构建从字符串到有向图的映射关系
  2. 在给定的图中找出所有的欧拉路径和欧拉回路
  3. 理解并
  4. 证明欧拉回路与图的连通性和平衡性之间的关系

解题技巧和信息​

  1. 欧拉路径和欧拉回路的定义：欧拉路径是遍历图中每条边恰好一次的路径，欧拉回路是起点和终点相同的欧拉路径。
  2. 构建有向图：注意字符串到图的映射关系，特别是顶点和边的定义。
  3. 寻找欧拉路径和回路：从任意顶点开始，每次选择一条未使用的边，直到无法继续为止。
  4. 证明技巧：使用反证法和构造法来证明定理。
  5. 图的性质：理解连通性和平衡性对欧拉回路存在性的影响。

重点词汇​

  1. Eulerian path 欧拉路径
  2. Eulerian cycle 欧拉回路
  3. Directed graph 有向图
  4. Connected graph 连通图
  5. Balanced graph 平衡图
  6. Vertex 顶点
  7. Arc 弧（有向边）
  8. Cycle 环

参考资料​

  1. Bondy, J.A. and Murty, U.S.R. (2008). Graph Theory. Springer. Chapter 5: Eulerian Graphs.
  2. Diestel, R. (2017). Graph Theory (5th ed.). Springer. Chapter 1: The Basics.
  3. Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 22: Elementary Graph Algorithms.