グラフ・ネットワーク理論
| 授業目的 |
|---|
| 情報科学や実社会において様々な数理モデルとして使用されるグラフ理論・ネットワーク理論について，数学的な基本事項と代表的なアルゴリズムを理解する． |
| 到達目標 |
| グラフに関する基本的な用語や性質を理解し，要求された問題をグラフを用いて表現できる．また，グラフに関するアルゴリズムを理解し，それを用いて各種問題を解くことができる． |
| 授業計画 | |
|---|---|
| 第1回 | グラフ理論の基本用語 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第2回 | 連結性と木 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第3回 | オイラー小径とハミルトン閉路 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第4回 | 有向グラフと探索木 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第5回 | 最小全域木とそのアルゴリズム 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第6回 | 最短道とそのアルゴリズム 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第7回 | グラフの連結度 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第8回 | ネットワークとフロー 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第9回 | 二部グラフにおけるマッチング 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第10回 | 一般のグラフにおけるマッチング 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第11回 | 最大重みマッチングと線形計画問題 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第12回 | 平面グラフ 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第13回 | グラフ彩色と4色問題 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第14回 | ラムゼー理論 【授業外学修】授業の内容を復習し，授業中に終わらなかった演習課題に取り組む |
| 第15回 | 定期試験 |