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

Author

zephyr

Description

In undirected graphs, a self-loop is an edge connecting the same vertex, and multi-edges are multiple edges connecting the same pair of vertices. From now on, we consider undirected graphs without self-loops and possibly with multi-edges. We say that a graph is an -graph if a graph consisting of a single edge can be obtained from by repeatedly applying the following two operations.

B-operation

When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices.

C-operation

When one edge connects vertices and , another edge connects and (where ), and there is no other edge incident to , remove the vertex and replace the two edges with a new edge connecting and .

Answer the following questions.

(1) Let be a complete graph of vertices. Answer whether each of and is an -graph or not.

(2) Show that every -graph is planar.

(3) Give the maximum number of edges of an -graph with vertices without multi-edges, with a proof. Also, give such an -graph attaining the maximum for general , with an explanation.

(4) Give an -time algorithm which, given an undirected graph with vertices and edges as an input, determines whether it is an -graph or not. Explain also the graph data structures used in the algorithm for realizing -operations and -operations.

Kai

(1)

: The complete graph consists of 3 vertices and 3 edges, forming a triangle. Since there are no multi-edges in , the -operation does not apply. To apply the -operation, we need a vertex with exactly two incident edges, connecting to vertices and . In , each vertex is connected to two others, so we can apply the -operation to any vertex, forming an edge between the remaining two vertices, and applying the -operation again will reduce the graph to a single edge. Therefore, is an -graph.

: The complete graph consists of 4 vertices and 6 edges, forming a tetrahedron. Similar to , there are no multi-edges, so the -operation does not apply. For the -operation, we need a vertex with exactly two incident edges. In , each vertex is connected to three others, so we cannot directly apply the -operation. Hence, is not an -graph.

(2)

Planar graphs are graphs that can be embedded in the plane without edge crossings.

Every -graph is planar. This can be shown by considering the operations allowed on -graphs:

• The -operation simplifies the graph by removing multi-edges, which does not affect planarity.
• The -operation reduces the number of vertices while maintaining planarity because it replaces a vertex of degree 2 with a single edge, which is a planar transformation.

Since a single edge is trivially planar and the operations preserve planarity, every -graph must be planar.

(3)

The maximum number of edges in an -graph with vertices without multi-edges is .

Proof:

• In an -graph, the -operation reduces multi-edges to a single edge, and there are no multi-edges in the final graph.
• The -operation reduces the number of vertices by 1 while maintaining the number of edges. Therefore, the number of edges in the final graph is .

(4)

To determine if a given undirected graph with vertices and edges is an -graph, we can use the following algorithm:

1. Graph Representation: Use an adjacency list to store the graph. This allows efficient traversal and modification.
2. Initialize: Mark all vertices as unvisited.
3. Identify and Apply -operation:
   • For each pair of vertices, check for multi-edges.
   • If multi-edges exist, replace them with a single edge.
4. Identify and Apply -operation:
   • Traverse the graph to identify vertices of degree 2.
   • For each vertex with degree 2 connecting vertices and , remove and replace edges and with a single edge .
5. Repeat Steps 3 and 4 until no more or operations can be applied.
6. Check Result: If the graph reduces to a single edge, it is an -graph. Otherwise, it is not.

Graph Data Structures:

• Adjacency List: Efficiently stores the graph and allows for quick traversal and edge modification.
• Degree List: Maintains the degree of each vertex for quick identification of vertices suitable for the -operation.

The algorithm runs in time since each edge and vertex is processed a constant number of times.

Knowledge

图论 平面图 算法

难点解题思路

识别和应用 和 操作是确定 -图的关键。对于复杂图的处理，可以通过维护邻接表和度列表来优化操作。

解题技巧和信息

对于确定图的性质问题，特别是涉及特定操作的图，可以通过模拟操作并逐步简化图结构来判断。理解操作对图结构的影响是关键。

重点词汇

• Self-loop 自环
• Multi-edges 多重边
• Planar 平面
• Complete graph 完全图
• Algorithm 算法

参考资料

1. "Introduction to Graph Theory" by Douglas B. West, Chapter 4
2. "Graph Theory" by Reinhard Diestel, Chapter 5