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

标签：

• 东京大学
• 连通性

Author

祭音Myyura

Description

頂点集合を $V$、辺集合を $E$ とする無向グラフを $G = (V, E)$ とする。$E$ に含まれない辺の集合 $\overline{E} = \{(u, v) \mid u, v \in V, (u, v) \notin E\}$ を辺集合とする無向グラフ $\overline{G}= (V, \overline E)$ を $G$ の補グラフと呼ぶ。$G$ の任意の 2 頂点間に道があるとき $G$ は連結と呼ぶ。

(1) $G$ と $\overline{G}$ が同時に連結グラフとなる例を示せ。

(2) $G$ が連結グラフか否かを $O(|V| + |E|)$-時間で検査するアルゴリズムを設計せよ。

(3) $G$ と $\overline{G}$ のどちらかは連結グラフとなることを証明せよ。

题目描述

设 $G=(V,E)$ 为无向图。题面把不在 $E$ 中的边记为

$$\overline E=\{(u,v)\mid u,v\in V,\ (u,v)\notin E\},$$

并称相应图为 $G$ 的补图 $\overline G$；当任意两顶点间都有路径时称图连通。

1. 给出一个 $G$ 与 $\overline G$ 同时连通的例子。

2. 设计在

   $$O(|V|+|E|)$$

   时间内判断 $G$ 是否连通的算法。

3. 证明 $G$ 与 $\overline G$ 至少有一个是连通图。

Kai

(1)

連結性に影響しない自己ループは省略する。

頂点集合: $V = \{1, 2, 3, 4\}$

$G$ の辺集合: $E = \{(1, 2), (2, 3), (3, 4)\}$

$G$ は $1 \text{---} 2 \text{---} 3 \text{---} 4$ という一本の道になるため、すべての頂点間に道があり連結です。

$\overline{G}$ の辺集合: $\overline{E} = \{(1, 3), (1, 4), (2, 4)\}$

$\overline{G}$ における辺のつながりをたどると、$3 \text{---} 1 \text{---} 4 \text{---} 2$ という一本の道になります。したがって、$\overline{G}$ もすべての頂点間に道があり連結です。

(2)

任意の頂点 $s$ から DFS または BFS を行い、訪問済み頂点数が $|V|$ なら連結、そうでなければ非連結と判定する。各頂点を高々1回、隣接リストの各辺を高々2回調べるため、時間計算量は $O(|V|+|E|)$ である。

(3)

$G$ が連結グラフである場合は題意を満たすため、$G$ が非連結グラフであると仮定したとき、補グラフ $\overline{G}$ が必ず連結グラフになることを証明する。

このとき、頂点集合 $V$ は互いに素で空でない2つ以上の部分集合（連結成分）に分割できる。 $V$ を2つの空でない集合 $A$ と $B$ に分割し、$V = A \cup B$ かつ $A \cap B = \emptyset$ とし、$G$ において $A$ の頂点と $B$ の頂点を結ぶ辺が一つも存在しない状態とする。

補グラフ $\overline{G}$ の辺集合 $\overline{E}$ の定義により、$G$ に存在しない辺はすべて $\overline{G}$ に存在する。したがって、$A$ に属する任意の頂点と、$B$ に属する任意の頂点を結ぶ辺は、すべて $\overline{G}$ に存在する。

$\overline{G}$ において、任意の2頂点 $u, v \in V$ 間に道が存在すること（つまり連結であること）を、以下の3つのケースに分けて示す。

• $u \in A$ かつ $v \in B$ の場合:前述の通り、$A$ の頂点と $B$ の頂点の間には必ず辺が存在するため、$\overline{G}$ には直接結ぶ辺 $(u, v)$ が存在する。
• $u, v \in A$ の場合:$B$ は空ではないため、任意の頂点 $w \in B$ を一つ選ぶことができる。$\overline{G}$ には辺 $(u, w)$ および $(v, w)$ が必ず存在するため、$u \text{---} w \text{---} v$ という道が存在する。
• $u, v \in B$ の場合:$A$ は空ではないため、任意の頂点 $x \in A$ を一つ選ぶことができる。同様に、$\overline{G}$ には辺 $(u, x)$ および $(v, x)$ が存在するため、$u \text{---} x \text{---} v$ という道が存在する。

以上のすべてのケースにおいて、任意の2頂点間に道が存在することが示された。よって、$G$ が非連結であるならば、$\overline{G}$ は必ず連結グラフとなる。ゆえに、$G$ と $\overline{G}$ のうち少なくとも一方は連結グラフである。