【院試解答】 京都大学 情報学研究科 数理工学コース グラフ理論 2025年度入学

【院試解答】 京都大学 情報学研究科 数理工学コース グラフ理論 2025年度入学

令和6(2024)年に実施された、京都大学情報学研究科京都大学情報学研究科数理工学コース（令和7(2025)年度4月期入学修士課程）の筆記試験、専門科目「グラフ理論」の解答例です。もし誤字・脱字や、解答の誤りを見つけた場合には、連絡いただけると対応します。
解答一つ一つ、解説も含めて丁寧に作成しているので、無料では書くことが難しいです。応援する気持ちも込めてワンコインで購入していただけると励みになります。
また、京都大学情報学研究科京都大学情報学研究科数理工学コース及び大阪大学大学院情報科学研究科（IST）情報数理学専攻に関してなら、他の科目・年度の解答・解説のリクエストも受け付けています。

問題

有限集合 $${A}$$ に属する要素の個数を $${|A|}$$ と書く。節点集合 $${V}$$ および枝集合 $${E}$$ からなる単純連結無向グラフ $${G = (V, E)}$$ が与えられたものとする。ただし $${|V| \geq 3}$$ とする。始点 $${s \in V}$$ を一つ選ぶ。任意の節点 $${v \in V}$$ に対し、$${s}$$ から $${v}$$ への最短路における枝の本数を $${\text{dist}(v)}$$ と書き、$${s}$$ から $${v}$$ への最短路の総数を $${σ(v)}$$ と書く。さらに、$${d_{\max} = \max_{v \in V} \text{dist}(v)}$$ とし、整数 $${i = 0, 1, \dots, d_{\max}}$$ に対して $${V_i = \{ v \in V | \text{dist}(v) = i \}}$$ とする。以下の問いに答えよ。

(i) $${d_{\max}}$$ および $${V_i}$$, $${i = 0, 1, \dots, d_{\max}}$$ を $${O(|E|)}$$ 時間で計算する方法を示せ。

(ii) すべての $${v \in V}$$ に対して $${σ(v)}$$ を $${O(|E|)}$$ 時間で計算する方法を示せ。

(iii) ある節点 $${t \in V \setminus \{ s \}}$$ と節点の部分集合 $${U \subseteq V \setminus \{ s, t \}}$$ に対して、$${s}$$ から $${t}$$ への最短路のうち、$${U}$$ に属する節点を少なくとも 1 個通過するものの個数を $${O(|E|)}$$ 時間で計算する方法を示せ。

(iv) ある節点 $${t \in V \setminus \{ s \}}$$ と節点の部分集合 $${U \subseteq V \setminus \{ s, t \}}$$、整数 $${1 \leq k \leq |U|}$$ に対して、$${s}$$ から $${t}$$ への最短路のうち、$${U}$$ に属する節点を少なくとも $${k}$$ 個通過するものが存在するかどうかを $${O(|E|)}$$ 時間で判定する方法を示せ。

総評

＜難易度評価＞ 易、やや易、標準、やや難、難の5段階評価。

(i)やや易、(ii)標準、(iii)標準、(iv)難

＜解答のポイント＞

幅優先探索とその結果を応用するアルゴリズムを考える。そのときには、本問のように距離による節点集合の分割$${V_0,\dots,V_{d_{\max}}}$$を考えることが有効であることが多い。例えば他には、二部グラフの判定問題などがある。実は本問は、2015年度入学の基礎科目「アルゴリズム基礎」とほとんど同じ問題である。そのため、過去問を解いたことのある者は、比較的簡単に解くことができただろう。その一方で、全問とも記述量も多く、最終問題は過去問と比べて難易度が上がっているので、初見で時間内に全問を解くのは難しい。

以下、ベクトルであっても太字では書かないこととする。また、$${I}$$を単位行列、$${O}$$を零行列とする。
また、$${X,Y\subset V}$$に対して、

$$
E(X,Y):=\{(u,v)\in E\mid u\in X, v\in Y\}
$$

とおく。

(i)

解説

幅優先探索の典型的な問題。アルゴリズムを与えよ、方法を求めよ、という問題では（おそらく）アルゴリズムの正当性の証明などは求められず、疑似コードを書くだけでよいと思われる。ただ、間違っていた時に部分点を取るために、アルゴリズムの説明を付け加えられるとなお良い。また、アルゴリズムを記述する際に、筆者のお薦めとしては「出力」「初期化」「実行」「計算量」の4つに分けて記述すると、見やすくなる。