東京大学 新領域創成科学研究科 メディカル情報生命専攻 2025年1月実施 問題8
Author
祭音Myyura
Description
頂点集合を 、辺集合を とする無向グラフを とする。 に含まれない辺の集合 を辺集合とする無向グラフ を の補グラフと呼ぶ。 の任意の 2 頂点間に道があるとき は連結と呼ぶ。
(1) と が同時に連結グラフとなる例を示せ。
(2) が連結グラフか否かを -時間で検査するアルゴリズムを設計せよ。
(3) と のどちらかは連結グラフとなることを証明せよ。
Kai
(1)
頂点集合:
の辺集合:
は という一本の道になるため、すべての頂点間に道があり連結です。
の辺集合:
における辺のつながりをたどると、 という一本の道になります。したがって、 もすべての頂点間に道があり連結です。
(2)
深さ優先探索（DFS）または幅優先探索（BFS）を用いて、ある頂点から到達可能な頂点を列挙することで検査できる。
(3)
が連結グラフである場合は題意を満たすため、 が非連結グラフであると仮定したとき、補グラフ が必ず連結グラフになることを証明する。
このとき、頂点集合 は互いに素で空でない2つ以上の部分集合（連結成分）に分割できる。
を2つの空でない集合 と に分割し、 かつ とし、 において の頂点と の頂点を結ぶ辺が一つも存在しない状態とする。
補グラフ の辺集合 の定義により、 に存在しない辺はすべて に存在する。したがって、 に属する任意の頂点と、 に属する任意の頂点を結ぶ辺は、すべて に存在する。
において、任意の2頂点 間に道が存在すること（つまり連結であること）を、以下の3つのケースに分けて示す。
- かつ の場合:前述の通り、 の頂点と の頂点の間には必ず辺が存在するため、 には直接結ぶ辺 が存在する。
- の場合: は空ではないため、任意の頂点 を一つ選ぶことができる。 には辺 および が必ず存在するため、 という道が存在する。
- の場合: は空ではないため、任意の頂点 を一つ選ぶことができる。同様に、 には辺 および が存在するため、 という道が存在する。
以上のすべてのケースにおいて、任意の2頂点間に道が存在することが示された。よって、 が非連結であるならば、 は必ず連結グラフとなる。ゆえに、 と のうち少なくとも一方は連結グラフである。