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

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

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

総評

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

＜解答のポイント＞
ダイクストラ法に関する基本的な問題。ダイクストラ法自体は過去問でも頻出であり、（1）、（3）は全く同じ問題が過去にも出題されている。しかし、（2）では、計算量をより厳しく評価することが求められるようになっており、やや難度が上がっている。

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

(i)

解説

ダイクストラ法の正当性に関する定理の証明問題。幅優先探索やプリム法の正当性の証明と同様に、パスとカットの論理を用いて証明する。等号を示すために、二方向からの不等号を示す。片方の不等号は距離の定義からほとんど明らかで、もう片方の不等号については、最短路の一つを取り出して、カットとの関係を考える。