東京大学 新領域創成科学研究科 メディカル情報生命専攻 2025年8月実施 問題8
Author
祭音Myyura
Description
を単純連結無向グラフとする。以下の問いに答えよ。
(1) 以下のグラフ について点 1 を根とする深さ優先探索木 をひとつ描け。
(2) を の深さ優先探索木とする。 の辺 が、 の辺に含まれないとき、 は 内の の祖先か子孫のいずれかの点であることを示せ。
の点 を取り除くとグラフが非連結になるとき、 を関節点という。
(3) (1) の について関節点を全て求めよ。
(4) は の根とする。 が 上で２つ以上の子を持つとき、 は関節点であることを示せ。
(5) は の根でないとする。以下の条件(A)を満たす 上の の子 があるとき、 は関節点で
あることを示せ。
- 条件(A): の辺で、 上の の祖先と、 かその子孫とをつなぐものは一つもない。
Kai
(1)
(2)
の辺 が の辺（木辺）に含まれないと仮定する。一般性を失わず、DFSの探索において頂点 が よりも先に発見（訪問）されたとする。
の探索中、それに接続する辺 も必ず走査される。このとき がまだ訪問されていなければ、辺 を経由して を訪問することになるため、 は の辺として追加されるはずである。しかし、前提より は に含まれないため、 から を走査した時点で、 はすでに「訪問済み」でなければならない。
つまり、 は「 が発見された後」かつ「 の探索処理が完了する前」に訪問されたことになる。DFSの性質上、これは が を始点とする再帰的な探索の過程で発見されたことを意味し、 において は の子孫となる。したがって、 は 内の の子孫（ を先に発見したと仮定した場合は祖先）のいずれかである。
(3)
の関節点は 1, 4 である。
(4)
を の根とし、 が 上で2つの子 を持つとする。
において、 を根とする部分木を 、 を根とする部分木を とする。木構造の性質上、これらは互いに素な頂点集合を持つ。
(2)で証明した通り、 のすべての非木辺は祖先と子孫を結ぶ（後退辺である）ため、互いに祖先・子孫の関係にない の頂点と の頂点を直接結ぶ辺（交差辺）は には一切存在しない。
したがって、グラフ において 内の任意の頂点から 内の任意の頂点への経路は、必ず双方の共通の祖先である根 を経由しなければならない。グラフ から を取り除くと、 と を結ぶ経路が完全に失われるため、グラフは非連結となる。よって、 は関節点である。
(5)
を の根ではない頂点とし、 を条件(A)を満たす の子とする。
において を根とする部分木を とする。
がグラフ から取り除かれた場合を考える。(2)より には交差辺が存在しないため、 内の頂点から 外の頂点へ向かう辺は、 内から自身の祖先へ向かう後退辺のみに限られる。
内の頂点の祖先は、 自身、または より上位の祖先である。しかし、条件(A)より、 内の頂点から の祖先へ直接つながる辺は一つも存在しない。ゆえに、 内の頂点から の祖先（ が根でないため、少なくとも根が一つ存在する）への経路は、すべて を経由しなければならない。
を取り除くと、 に属する頂点は の祖先を含む他のグラフ成分から完全に切り離され、グラフは非連結となる。よって、 は関節点である。