グラフ理論が出た院試 過去問
数学の頻出テーマ
定義・定理・計算例から確かめるには:アルゴリズムとデータ構造・グラフアルゴリズム
グラフ理論を出した大学 × 年度
グラフ理論の出題例と解説の小見出し
- 名古屋大学大学院 数理情報学 2026年度 第6問 — 離散最適化
- 名古屋大学大学院 複雑系科学 2026年度 第17問 — 情3:整列・二分探索木と最短経路法
バブルソートでは右端から確定する / 平均探索コストは深さの平均で見る
- 東京都立大学大学院 情報科学域 専門科目 2026年度 第4問 — ダイクストラ法の追跡
確定順序の読み方 / 同距離候補の扱い
- 京都大学 知能情報学コース 2025年度 第3問 — F2-1 アルゴリズムとデータ構造
最短路は「通る場合」と「通らない場合」に分ける / 貪欲集合被覆とマッチング
- 京都大学 数理工学コース 2025年度 第4問 — 専門 第2問:グラフ理論
- 北海道大学大学院 情報科学専攻 情報理工学コース 専門科目 2025年度 第4問 — アルゴリズムとデータ構造
Big-Oは支配項を見る / 走査順の確認
- 京都大学 知能情報学コース 2024年度 第3問 — F2-1 アルゴリズムとデータ構造
最大直径は三角形の鎖で作る
- 京都大学 数理工学コース 2024年度 第4問 — 専門 第2問:グラフ理論
- 京都大学 社会情報学コース 2023年度 第7問 — 専門科目T2:類似度・PageRank・中心性
平均中心化 / PageRankの直観
- 京都大学 数理工学コース 2023年度 第4問 — 専門 第2問:グラフ理論
- 大阪大学 専門科目(情報数理学) 2023年度 第1問 — 情報基礎
指数時間と擬多項式時間 / 答案で落としやすい点
- 早稲田大学大学院 情報理工・情報通信専攻 専門科目 2023年度 第4問 — 情報通信ネットワーク
階層ごとに考える / 距離ベクトルの更新
- 東京大学 建築学 専門科目 2023年度 第3問 — 専門課題II 第2群(建築計画・建築史・構法)
点を伸ばす書き方
- 東京科学大学 情報通信 2023年度 第5問 — 状態遷移と最短路
状態遷移は意味から作る / Dijkstra法の空欄
- 京都大学 通信情報システムコース 2022年度 第9問 — A-9 グラフ理論
次数和の検算 / 存在例の示し方
- 京都大学 数理工学コース 2022年度 第8問 — 専門 第2問:グラフ理論
最大流最小カット定理の核 / 最小カットでは等号条件が強い
- 名古屋大学大学院 数理情報学 2022年度 第4問 — 第1科目・グラフ理論
最小色数の示し方 / 偶閉路条件と二部グラフ
- 名古屋大学大学院 数理情報学 2022年度 第11問 — 第2科目・グラフ理論
和が区間に入るかだけを見る / 5閉路が失敗する理由
- 京都大学 通信情報システムコース 2021年度 第9問 — A-9 グラフ理論
二部グラフと奇閉路 / Oreの定理の核心
- 京都大学 数理工学コース 2021年度 第2問 — 基礎 第2問:アルゴリズム基礎
最短路に含まれる枝の特徴 / 距離を増やす枝
- 京都大学 数理工学コース 2021年度 第8問 — 専門 第2問:グラフ理論
交換論法 / ボトルネック最小性
- 名古屋大学大学院 数理情報学 2020年度 第4問 — グラフ理論
極大と最大の違い / Hall条件の使いどころ
グラフ理論を解答まで読める問題
解説に加えて解答も無料で公開している1問です。院試の対策のほか、学部の授業や期末試験でグラフ理論の計算を練習する例題としても使えます。問題文は各大学の公式過去問で確認してください。
- 大阪大学 専門科目(情報数理学) 2023年度 第1問 — 情報基礎
指数時間と擬多項式時間 / 答案で落としやすい点
グラフ理論が出る試験科目
| 大学・研究科 | 試験科目名 | 出題数 | 出題年度 |
|---|---|---|---|
| 京都大学情報学研究科 | 数理工学コース | 6 | 2021〜2025(5年度) |
| 名古屋大学大学院情報学研究科 | 数理情報学 | 4 | 2020〜2026(3年度) |
| 京都大学情報学研究科 | 知能情報学コース | 2 | 2024〜2025(2年度) |
| 京都大学情報学研究科 | 通信情報システムコース | 2 | 2021〜2022(2年度) |
| 早稲田大学大学院基幹理工学研究科 | 情報理工・情報通信専攻 専門科目 | 1 | 2023 |
| 大阪大学情報科学研究科 情報基礎数学専攻 | 専門科目(情報数理学) | 1 | 2023 |
| 京都大学情報学研究科 | 社会情報学コース | 1 | 2023 |
| 北海道大学大学院情報科学院 | 情報科学専攻 情報理工学コース 専門科目 | 1 | 2025 |
| 東京科学大学工学院 情報通信系 | 情報通信 | 1 | 2023 |
| 東京大学工学系研究科 物理工学専攻 | 建築学 専門科目 | 1 | 2023 |
| 東京都立大学大学院システムデザイン研究科 情報科学域 | 情報科学域 専門科目 | 1 | 2026 |
| 名古屋大学大学院情報学研究科 | 複雑系科学 | 1 | 2026 |