組合せとグラフの理論（塩田）2024年度
授業形態ほか
- 担当教員 : 理工学部 情報科学科 塩田研一
- メールアドレスは shiota＠is.kochi-u.ac.jp です。( ＠は小文字に直してください。)
- 授業は対面で実施します。教室は 理工学部情報科学棟１階の共通講義室４ です。
- 一昨年度のオンライン教材も一部修正の上掲載しておきますが、メインは対面授業です。
教科書（必携）
- R.J.ウィルソン著，西関隆夫・西関裕子訳，
「グラフ理論入門 原書第4版」 ( 近代科学社 )，ISBN 4764902966
(電子書籍の Kindle 版もあります。)
教科書は必ず手に入れてください。
各回の教材
| 授業日 | 講義内容(予定) |
|---|
| 第1回 | 4月12日 | グラフ理論の始まり、本講義の目標 |
| 第2回 | 4月19日 | グラフの基本用語、同型、計算機上でのデータ表現 |
| 第3回 | 4月26日 | グラフの名前と形容詞、グラフの演算、連結性 |
| 第4回 | 5月10日 | 道、連結度 |
| 第5回 | 5月17日 | オイラー性、ハミルトン性 |
| 第6回 | 5月24日 | 木、全域木、幅優先探索・深さ優先探索 |
| 第7回 | 5月31日 | 閉路部分空間と電気回路への応用 |
| 第8回 | 6月7日 | 最短路問題、巡回セールスマン問題他 |
| 第9回 | 6月14日 | 平面性、オイラーの公式 |
| 第10回 | 6月21日 | 双対グラフ |
| 第11回 | 6月28日 | 点彩色、平面グラフの面彩色 |
| 第12回 | 7月5日 | ネットワークフロー |
| 第13回 | 7月12日 | 最大フロー・最小カット定理、Menger の定理 |
| 第14回 | 7月19日 | マッチング |
| 第15回 | 7月26日 | グラフ理論の最近の話題 |
宿題
- 宿題はスキャンするか写メを撮るなどして、pdf ファイル・画像ファイル等をメールに添付して提出してください。
pdf ファイルもこのページから download 出来ます。
- メールアドレスは shiota＠is.kochi-u.ac.jp です。( ＠は小文字に直してください。)
- 上手く提出できない人は相談してください。
- 宿題メールには数日のうちに添削して返信します。
指摘した個所が修正できたら再提出して頂いて構いません（それなりに加点します）。
- 宿題を複数回分まとめて提出されると見落とす危険があります。
１回分ずつ送信してください。
- 4月12日の宿題
- 4月19日の宿題
- 4月26日の宿題
e-ポートフォリオ
- この授業は e-ポートフォリオ対象科目 です。
- 宿題やプリント等を、適当なタイミングでアップロードしておいて頂ければ幸いです。
トップページ