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

标签：

• Tokyo-University
• Connectivity

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, E)$ を $G$ の補グラフと呼ぶ。$G$ の任意の 2 頂点間に道があるとき $G$ は連結と呼ぶ。

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

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

(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)

深さ優先探索（DFS）または幅優先探索（BFS）を用いて、ある頂点から到達可能な頂点を列挙することで検査できる。

(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}$ のうち少なくとも一方は連結グラフである。