無料🆓【院試解答】 京都大学 情報学研究科 数理工学コース サンプル問題A グラフ理論

【院試解答】 京都大学 情報学研究科 数理工学コース サンプル問題A グラフ理論

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

総評

＜難易度評価＞ 易、やや易、標準、やや難、難の5段階評価。
(i)やや易
(ii)やや難
(iii)標準

＜解答のポイント＞
幅優先探索にまつわる問題。数学的な証明などはなく、アルゴリズムの記述とグラフの具体例の列挙が出題された。幅優先探索の基本的な問題であるが、(ii)は少し工夫が必要であり、難しいと感じるかもしれない。しかし、2025年度の問題は、(ii)の考え方を応用した、より難しい問題が出題されたので、(ii)を含め、本問題はきちんと理解しておくことが重要である。
以下、ベクトルであっても太字では書かないこととする。また、$${I}$$を単位行列、$${O}$$を零行列とする。

(i)

解説

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

解答

幅優先探索を行う。求めるアルゴリズムは次のようになる。

出力：
各$${v\in R(s;G)\setminus\{s\}}$$に対して、$${p(v)}$$は1つの最短路木における$${v}$$の親を表す。また、$${S=R(s;G)}$$となる。

初期化：$${S:=\{s\}}$$、$${Q:=\{s\}}$$(FIFOキュー)、$${p(s):=s}$$。

実行：

$$
\begin{align}
& \text{while } Q\neq\emptyset \text{ do} \\
& \quad u:=\text{dequeue}(Q) \\
& \quad \text{for each } (u,v)\in E \text{ do} \\
& \quad \quad \text{if } v\not\in S \text{ then} \\
& \quad \quad \quad S:=S\cup\{v\} \\
& \quad \quad \quad \text{enqueue}(Q,v) \\
& \quad \quad \quad p(v):=u \\
& \quad \quad \text{end if} \\
& \quad \text{end for} \\
& \text{end while}
\end{align}
$$

上のアルゴリズムを実行後、$${s}$$から$${t}$$への最短路の1つは、点$${t, p(t), p(p(t)), \dots, s}$$をたどることで得られる。

計算量：

今、グラフ$${G=(V,E)}$$は隣接リストで貯えられているから、各頂点に隣接する辺を列挙するのに$${O(\deg(v))}$$の時間がかかる。今、(3)の各ループは$${O(1)}$$の時間で実行されるから、全体で$${O(\sum_{v\in V}\deg(v))=O(|E|)}$$の時間がかかる。

(ii)

解説

幅優先探索を応用したアルゴリズムでは、しばしば$${V_i:=\{v\in R(s;G)\mid \text{dist}(s,v;G)=i\}}$$という集合を定義して、点集合を$${V=V_0\cup V_1\cup \dots \cup V_d}$$（直和）と分割することを考える。この時に重要な性質としては、

1. $${i\neq j}$$ならば、$${V_i\cap V_j=\emptyset}$$である。

2. $${|i-j|\geq 2}$$ならば、$${V_i}$$と$${V_j}$$の間には辺が存在しない。言い換えると$${E(V_i,V_j)=\emptyset}$$である。

1は明らか。2は、もし辺があったとすると、最短距離を1小さくできてしまうことになるから矛盾する。

今回の問題では、ゴールの点$${t}$$からスタートの点$${s}$$までの最短路として、あり得るものを順に全て辿っていき、もし「どの最短路も必ず通る枝」が1本でも存在すれば、その枝を削除することで最短距離が大きくなってしまうことに着目する。

解答

$${X,Y\subset V}$$に対して、

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

とおく。また、幅優先探索により、$${R(s;G)}$$と$${\text{dist}(s,v;G),\quad v\in V}$$を求めておく。$${\text{dist}(s,v;G-e)> \text{dist}(s,v;G)}$$を満たす辺$eの存在判定アルゴリズムは次のとおりになる。

(1)$${t\notin R(s;G)}$$の場合

$$
\text{dist}(s,t;G-e)=n=\text{dist}(s,t;G),\quad \forall e\in E
$$

であるから、「存在しない」と出力する。

(2)$${t\in R(s;G)}$$の場合

$$
\begin{aligned}
d &:= \text{dist}(s,t;G) \quad(\leq n-1) \\
V_i&:= \{v\in R(s;G)\mid \text{dist}(s,v;G)=i\} & \quad (i=0,1,\dots,d) \\
\end{aligned}
$$

とおく。$${V_0=\{s\}}$$である。

出力：$${\text{dist}(s,v;G-e)> \text{dist}(s,v;G)}$$を満たす辺$eが存在すれば、「存在する」と出力する。存在しなければ、「存在しない」と出力する。

初期化：$${Q:=\{t\}}$$（訪問済み頂点の集合）

実行：

$$
\begin{align}
& \text{for each}\quad i:=d , d-1, \dots, 1 \quad \text{do} \\
& \quad n:=0\quad (\text{各ループでのカウンター。経路の数を表す。}) \\
& \quad \text{for each } v\in V_i \cap Q \text{ do} \\
& \quad \quad \text{for each } (u,v)\in E(V_{i-1},V_i) \text{ do} \\
& \quad \quad \quad n:=n+1\\
& \quad \quad \quad Q:=Q\cup\{u\} \\
& \quad \quad \text{end for} \\
& \quad \text{end for} \\
& \quad \text{if } n=1 \text{ then} \\
& \quad \quad \text{「存在する」と出力して終了} \\
& \quad \text{end if} \\
& \text{end for} \\
& \text{「存在しない」と出力して終了}
\end{align}
$$

計算量：

$${R(s;G),\text{dist}(s,v;G),d,V_i}$$を求めるのに$${O(|E|)}$$の時間がかかる。また、各ループの計算量は$${O(\deg(v))}$$であるから、全体で$${O(|E|)}$$の時間がかかる。
また、(14)の各ループの計算量は$${O(1)}$$であるから、(i)同様に実行の部分全体で$${O(|E|)}$$の時間がかかる。
全体では、$${O(|E|)}$$の時間がかかる。

(iii)

解説

$${s}$$から$${t}$$に至る時にも、$${t}$$から$${s}$$に至る時にも、必ず枝$${e}$$を通るようなグラフを考える。距離の指定があるので、点の数は4つ程度に定まる。採点の際に、あまりにバリエーションがあると、採点が難しくなるため、ある程度の制約を設けているのだとおもわれる。グラフの具体例を示す問題では、まず辺や点は多めにとっておき、その中から条件を満たすものを選ぶという方法が有効である。

解答

```mermaid
graph TD
    s((s))--> u((u))
    v((v))-->s
    u-->|e|v
    v-->t((t))
    t-->u```

#京大 #京都大学 #京大院試 #京大情報学研究科数理工学コース #京都大学大学院
#グラフ理論
#数学 #大学数学 #外部院試 #院試過去問 #院試対策 #院試解答 #大学院入試 #大学院試験 #理系大学院 #情報系