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

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

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

総評

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

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

(i)

解説