東京大学 情報理工学系研究科 コンピュータ科学専攻 2023年8月実施 専門科目 問題3
Author
Description
Let
Answer the following questions:
(1) Describe an algorithm to check whether or not
(2) Describe a
(3) Let
(4) Describe a
设
回答以下问题:
(1) 描述一个算法来检查
(2) 描述一个
(3) 设
(4) 描述一个
Kai
(1)
Algorithm
To check whether the graph
- Start from an arbitrary vertex
and perform DFS or BFS. - Mark all visited vertices during the search.
- 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
, where and . This is because, in the worst case, you will visit every vertex and every edge exactly once.
(2)
Algorithm
To find a spanning tree
- Start from an arbitrary vertex
and initialize as an empty set of edges. - Perform DFS or BFS, adding each edge traversed to
until all vertices are visited. - The resulting set of edges
forms a spanning tree.
Time Complexity
- The time complexity of this algorithm is
because each edge is considered exactly once.
(3)
Proof
Let
- Since
is not a cut vertex, removing from does not disconnect the graph. Therefore, there exists another path in that connects the components formed by the removal of . - Let
be an edge in that connects two components of . - Adding edge
to will create a cycle because is a spanning tree. - Remove
from the cycle, and you will obtain a new spanning tree . The edge replaces , forming , which is also a spanning tree.
Thus, replacing edge
(4)
Algorithm
To find all cut vertices of
- Perform a DFS traversal of
, numbering the vertices in the order they are visited. - For each vertex
, maintain two values: - DFS number: The order in which the vertex was visited.
- Low number: The lowest DFS number reachable from
using back edges.
- A vertex
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 there is a child
such that no vertex in the subtree rooted at can reach a vertex higher up in the DFS tree than .
Time Complexity
- The time complexity of Tarjan's algorithm is
, which is much more efficient than .
Knowledge
DFS 图论 连通性 生成树 割点 切点
解题技巧和信息
- 图的连通性检查: DFS 和 BFS 是检查图的连通性的基本工具。
- 生成树构造: DFS 或 BFS 都可以用来构造图的生成树,时间复杂度为
。 - 割点的寻找: Tarjan 算法是寻找割点的经典算法,其时间复杂度为
,适合大规模图的处理。
重点词汇
- Cut vertex: 割点
- Spanning tree: 生成树
- Depth-First Search (DFS): 深度优先搜索
- Connected graph: 连通图
参考资料
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms." MIT Press, Chapter 22, "Elementary Graph Algorithms".
- Robert Tarjan, "Depth-First Search and Linear Graph Algorithms", SIAM Journal on Computing, 1972.