東京大学 情報理工学系研究科 コンピュータ科学専攻 2023年8月実施 専門科目 問題3

标签：

• Tokyo-University
• Connectivity
• Depth-First-Search
• Articulation-Point
• Spanning-Tree

Author

zephyr, 祭音Myyura

Description

Let $G = (V, E)$ be an undirected graph with no self-loops (edges joining the same vertex) nor multi-edges (two or more edges joining the same two vertices), with $|V| = n$, $|E| = m$. If there is a vertex $v$ in a connected graph $G$ such that after deleting $v$, the resulting graph is not connected, we call $v$ a cut vertex of $G$.

Answer the following questions:

(1) Describe an algorithm to check whether or not $G$ is connected. Estimate the time complexity of the algorithm.

(2) Describe a $O(m)$ time algorithm to find a spanning tree $T$, given a connected graph $G$.

(3) Let $T$ be a spanning tree of a connected graph $G$, and assume that $v$ is a non-leaf node of $T$ (i.e., the degree of $v$ in $T$ is at least two) and that $v$ is not a cut vertex of $G$. Let $e$ be an edge of $T$ that is incident with $v$. Prove that one can obtain another spanning tree of $G$ from $T$ by replacing $e$ with another edge $f \neq e$ of $G$.

(4) Describe a $o(mn)$ time algorithm, given a connected graph $G$, to find all cut vertices of $G$.

---

设 $G = (V, E)$ 为一个无向图，该图没有自环（连接到同一顶点的边）也没有重边（连接同一对顶点的两个或更多边），且 $|V| = n$，$|E| = m$。如果在一个连通图 $G$ 中有一个顶点 $v$，使得删除 $v$ 后所得的图不再连通，我们称 $v$ 为 $G$ 的割点。

回答以下问题：

(1) 描述一个算法来检查 $G$ 是否连通。估计该算法的时间复杂度。

(2) 描述一个 $O(m)$ 时间的算法，给定一个连通图 $G$，找到一棵生成树 $T$。

(3) 设 $T$ 为连通图 $G$ 的一棵生成树，并假设 $v$ 是 $T$ 的一个非叶节点（即 $v$ 在 $T$ 中的度数至少为二），并且 $v$ 不是 $G$ 的割点。令 $e$ 为 $T$ 中与 $v$ 相邻的一条边。证明通过用 $G$ 的另一条边 $f \neq e$ 替换 $e$，可以得到 $G$ 的另一棵生成树。

(4) 描述一个 $o(mn)$ 时间的算法，给定一个连通图 $G$，找到 $G$ 的所有割点。

题目描述

设 $G=(V,E)$ 为无自环、无重边的无向图， $|V|=n$、$|E|=m$。若连通图 $G$ 中的顶点 $v$ 被删除后所得图不连通，则称 $v$ 为 $G$ 的割点。回答下列问题。

（1）描述判断 $G$ 是否连通的算法，并估计时间复杂度。

（2）给定连通图 $G$，描述一个 $O(m)$ 时间算法求其生成树 $T$。

（3）设 $T$ 是连通图 $G$ 的生成树，$v$ 是 $T$ 的非叶结点（在 $T$ 中度至少为二），且 $v$ 不是 $G$ 的割点。令 $e$ 为 $T$ 中一条与 $v$ 相接的边。证明存在 $G$ 中另一条边 $f\ne e$，用 $f$ 替换 $e$ 后仍得到 $G$ 的一棵生成树。

（4）给出一个耗时为 $o(mn)$ 的算法，输入连通图 $G$，找出其所有割点。

Kai

(1)

Algorithm

To check whether the graph $G = (V, E)$ is connected, you can perform a Depth-First Search (DFS) or Breadth-First Search (BFS) starting from any vertex $v \in V$. The algorithm proceeds as follows:

1. Start from an arbitrary vertex $v_0$ and perform DFS or BFS.
2. Mark all visited vertices during the search.
3. After the search is complete, check if all vertices have been visited.

If all vertices are visited, then the graph is connected; otherwise, it is not.

Time Complexity

• The time complexity of both DFS and BFS is $O(n + m)$, where $n = |V|$ and $m = |E|$. This is because, in the worst case, you will visit every vertex and every edge exactly once.

(2)

Algorithm

To find a spanning tree $T$ for a connected graph $G$, you can use a Depth-First Search (DFS) or Breadth-First Search (BFS):

1. Start from an arbitrary vertex $v_0$ and initialize $T$ as an empty set of edges.
2. Perform DFS or BFS, adding $(x,y)$ to $T$ only when it first discovers the unvisited vertex $y$ from $x$.
3. The resulting set of edges $T$ forms a spanning tree.

Time Complexity

• With adjacency lists the time is $O(n+m)=O(m)$, since a connected graph has $m\ge n-1$.

(3)

Proof

Write $e=\{v,u\}$, and let $C$ be the component of $T-e$ containing $u$. Since $v$ is not a leaf, the other component contains a vertex different from $v$. As $G-v$ is connected, a path in $G-v$ joins these two components. Some edge $f$ of this path crosses the cut $(C,V\setminus C)$; moreover $f\ne e$. Hence

$$(T-e)+f$$

is connected and has $n-1$ edges, so it is a spanning tree.

(4)

Algorithm

To find all cut vertices of $G$ efficiently, we can use a Depth-First Search (DFS) based algorithm, known as Tarjan's algorithm:

1. Perform a DFS traversal of $G$, numbering the vertices in the order they are visited.
2. For each vertex $v$, maintain two values:
   • DFS number: The order in which the vertex was visited.
   • Low number: The smallest DFS number reachable from the subtree of $v$ using at most one back edge.
3. A vertex $v$ is a cut vertex if:
   • It is the root of the DFS tree and has more than one child.
   • It is not the root, and it has a child $u$ with $\operatorname{low}(u)\ge\operatorname{dfs}(v)$.

Time Complexity

• The time complexity is $O(n+m)$, which is $o(mn)$ for connected graphs as $n\to\infty$.

Knowledge

DFS 图论 连通性 生成树 割点 切点

解题技巧和信息

1. 图的连通性检查: DFS 和 BFS 是检查图的连通性的基本工具。
2. 生成树构造: DFS 或 BFS 都可以用来构造图的生成树，时间复杂度为 $O(m)$。
3. 割点的寻找: Tarjan 算法是寻找割点的经典算法，其时间复杂度为 $O(n + m)$，适合大规模图的处理。

重点词汇

• Cut vertex: 割点
• Spanning tree: 生成树
• Depth-First Search (DFS): 深度优先搜索
• Connected graph: 连通图

参考资料

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms." MIT Press, Chapter 22, "Elementary Graph Algorithms".
2. Robert Tarjan, "Depth-First Search and Linear Graph Algorithms", SIAM Journal on Computing, 1972.