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

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

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

総評

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

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

＜解答のポイント＞

最大流・最小カットについての典型問題。典型問題ではあるが、証明と解答の分量が多いため、すらすらと書けるようになっておかないと、時間内に全て解答するのは難しい。グラフ理論、特に最大流・最小カットでは、うまく記号を設定することで記述を簡潔にする工夫が大事になってくる。

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

$$
E^+(v):=E(\{v\},V\setminus\{v\}), \quad E^-(v):=E(V\setminus\{v\},\{v\})
$$

とおく。

(i)

解説

最大流・最小カットでは必ず出題される典型問題。和をとる枝を、$${s}$$に出入りする枝から、$${X}$$に出入りする枝に変換することで証明する。