東京大学 新領域創成科学研究科 メディカル情報生命専攻 2015年8月実施 問題10
Author
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 \(L = c_1c_2 \dots c_n (n \geq 2)\). Let \(s_{i,k}\) denote \(c_i \dots c_{i+k-1}\), the substring of length \(k (\geq 1)\) that starts from position \(i\) in \(L\). Let \(G_{L,k}\) denote a directed graph such that the vertex set is \(\{s_{i,k} \mid i = 1, \dots, n - k + 1 \}\), and the set of labeled arcs is \(\{ (s_{i,k}, s_{i+1,k}, i) \mid i = 1, \dots, n - k \}\), The 3rd argument \(i\) is the label. Answer the following questions.
(1) When \(L = ACACA\), the vertex set and labeled arc set of \(G_{L,2}\) are \(\{AC, CA\}\) and \(\{(AC, CA, 1), (CA, AC, 2), (AC, CA, 3)\}\), respectively. List all Eulerian paths and cycles in \(G_{L,2}\).
(2) When \(L = GCGCGCAGCG\), list all Eulerian paths and cycles in each of \(G_{L,3}\) and \(G_{L,4}\).
(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.
在有向图中，一条路径是连接一系列顶点的一条或多条弧。一个环是起点和终点在同一个顶点的路径。欧拉路径（或环）是一条恰好遍历每条弧一次的路径（或环）。
接下来，我们从字符串 \(L = c_1c_2 \dots c_n (n \geq 2)\) 创建一个有向图。令 \(s_{i,k}\) 表示从 \(L\) 中位置 \(i\) 开始的长度为 \(k (\geq 1)\) 的子串 \(c_i \dots c_{i+k-1}\)。令 \(G_{L,k}\) 表示一个有向图，其顶点集为 \(\{s_{i,k} \mid i = 1, \dots, n - k + 1 \}\)，标记弧的集合为 \(\{ (s_{i,k}, s_{i+1,k}, i) \mid i = 1, \dots, n - k \}\)，第三个参数 \(i\) 是标签。回答以下问题。
(1) 当 \(L = ACACA\) 时，\(G_{L,2}\) 的顶点集和标记弧集分别为 \(\{AC, CA\}\) 和 \(\{(AC, CA, 1), (CA, AC, 2), (AC, CA, 3)\}\)。列出 \(G_{L,2}\) 中的所有欧拉路径和环。
(2) 当 \(L = GCGCGCAGCG\) 时，列出 \(G_{L,3}\) 和 \(G_{L,4}\) 中的所有欧拉路径和环。
(3) 如果一个顶点的进入弧的数量等于离开弧的数量，则该顶点是平衡的。如果每个顶点都是平衡的，则有向图是平衡的。如果有向图从任意顶点到任意顶点都有路径，则它是连通的。证明一个有欧拉环的有向图是连通且平衡的。
(4) 反之，如果一个图是连通且平衡的，证明该图有一个欧拉环。
Kai
(1)
Given \(L = ACACA\), we construct \(G_{L,2}\) as follows:
Vertex set: \(V = \{AC, CA\}\)
Labeled arc set: \(E = \{(AC, CA, 1), (CA, AC, 2), (AC, CA, 3)\}\)
To find all Eulerian paths and cycles, we need to traverse all arcs exactly once.
Eulerian paths:
- \((AC, CA, 1) \rightarrow (CA, AC, 2) \rightarrow (AC, CA, 3)\)
- \((CA, AC, 2) \rightarrow (AC, CA, 3) \rightarrow (AC, CA, 1)\)
- \((AC, CA, 3) \rightarrow (CA, AC, 2) \rightarrow (AC, CA, 3)\)
There are no Eulerian cycles in \(G_{L,2}\).
(2)
For \(G_{L,3}\)
Vertex set: \(V = \{GCG, CGC, GCA, CAG, AGC\}\)
Labeled arc set:
Eulerian cycle (also as Eulerian path):
For \(G_{L,4}\)
Vertex set:
Labeled arc set:
Eulerian path:
There are no Eulerian cycles in \(G_{L,4}\).
(3)
Let \(G = (V, E)\) be a directed graph with an Eulerian cycle \(C\).
Note: We assume that \(G\) 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 \(G\) is not connected. Then there exist vertices \(u, v \in V\) such that there is no path from \(u\) to \(v\). However, the Eulerian cycle \(C\) visits every edge in \(G\) exactly once, which means it visits every non-isolated vertex at least once. Therefore, \(C\) provides a path from \(u\) to \(v\), contradicting our assumption. Thus, \(G\) must be connected.
Balance
Let \(v \in V\) be any non-isolated vertex in \(G\). Every time the Eulerian cycle \(C\) enters \(v\), it must also leave \(v\), including the starting/ending vertex which is entered in the last step of the cycle. Therefore, the number of edges entering \(v\) is equal to the number of edges leaving \(v\). Since this is true for all non-isolated vertices, \(G\) is balanced.
(4)
Let \(G = (V, E)\) be a connected and balanced directed graph. We will prove this by constructing an Eulerian cycle.
- Start at any vertex \(v_0 \in V\).
- Choose any outgoing arc and follow it to the next vertex.
- Continue this process, each time choosing an unused arc, until we return to \(v_0\).
This process must terminate because:
a) The graph is balanced, so we can always leave a vertex we've entered (except possibly \(v_0\)).
b) The number of arcs is finite, so we must eventually return to \(v_0\).
Let's call the cycle we've constructed \(C\). If \(C\) includes all arcs in \(G\), we're done. If not, consider the subgraph \(G' = (V', E')\) where \(V'\) is the set of vertices incident to unused arcs, and \(E'\) is the set of unused arcs.
- \(G'\) is balanced: The balance of vertices in \(G'\) is unaffected by removing the equal number of incoming and outgoing arcs in \(C\).
- \(G'\) is connected to \(C\): If it weren't, \(G\) would not be connected.
Choose a vertex \(v'\) in \(G'\) that's also in \(C\). Start a new cycle \(C'\) from \(v'\) in \(G'\) using the same process as before. We can then combine \(C\) and \(C'\) into a larger cycle.
Repeat this process until all arcs are used. The result is an Eulerian cycle in \(G\).
Knowledge
图论 欧拉路径 有向图 连通性 平衡性
难点思路
- 构建从字符串到有向图的映射关系
- 在给定的图中找出所有的欧拉路径和欧拉回路
- 理解并
- 证明欧拉回路与图的连通性和平衡性之间的关系
解题技巧和信息
- 欧拉路径和欧拉回路的定义：欧拉路径是遍历图中每条边恰好一次的路径，欧拉回路是起点和终点相同的欧拉路径。
- 构建有向图：注意字符串到图的映射关系，特别是顶点和边的定义。
- 寻找欧拉路径和回路：从任意顶点开始，每次选择一条未使用的边，直到无法继续为止。
- 证明技巧：使用反证法和构造法来证明定理。
- 图的性质：理解连通性和平衡性对欧拉回路存在性的影响。
重点词汇
- Eulerian path 欧拉路径
- Eulerian cycle 欧拉回路
- Directed graph 有向图
- Connected graph 连通图
- Balanced graph 平衡图
- Vertex 顶点
- Arc 弧（有向边）
- Cycle 环
参考资料
- Bondy, J.A. and Murty, U.S.R. (2008). Graph Theory. Springer. Chapter 5: Eulerian Graphs.
- Diestel, R. (2017). Graph Theory (5th ed.). Springer. Chapter 1: The Basics.
- 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.