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

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

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

総評

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

(i)標準、(ii)標準

＜解答のポイント＞

ベルマンフォード法の正当性、及びアルゴリズムについての出題。ベルマンフォード法については、グラフ理論2013年度や2019年度でも出題されている。

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

(i)

解説

負閉路の存在に関する必要十分条件の証明。ベルマンフォード法の根幹となる定理なので、よく出題されている。長さn-1以内で考えた時の距離を考える。距離に関する条件が成り立てば、負閉路が存在しないことを示す（(2)ならば(1)）のは易しい。簡約コストを頭に入れつつ、閉路の重みを下から評価し非負を示す。負閉路がなければ、距離の条件が成り立つことを示すには、対偶をとるとよい。