|
授業計画
|
|
1
|
グラフ理論への興味を持ってもらうため、パズルを２題ほど出題し、グラフを用いてそれらを解いてみる。
|
|
2
|
グラフの定義と基本的な用語を学ぶ。頂点、辺、同形といった概念を学習する。
|
|
3
|
近傍と次数の概念を学ぶ。また握手定理とその証明を学ぶ。
|
|
4
|
完全グラフ、２部グラフなど特殊なグラフの定義とそれらの性質を学ぶ。また２つ以上のグラフから１つのグラフを作り出す演算操作もいくつか学ぶ。
|
|
5
|
道、閉路といった概念を学ぶ。またグラフの連結性の概念を学習し、連結グラフの性質を調べる。
|
|
6
|
グラフの最短路問題と、その解法であるダイクストラ法を学ぶ。実際の例題を解くことで理解を深めたい。
|
|
7
|
グラフの連結度、辺連結度の概念を学ぶ。特に連結度、辺連結度、最小次数に関する不等式を学習する。
|
|
8
|
木の定義を学び、その性質を調べる。また連結グラフの全域木の性質を調べる。
|
|
9
|
探索木の概念を学び、深さ優先探索のアルゴリズムを学ぶ。
|
|
10
|
ネットワークフローを学ぶ。ネットワークの定義から入り、ネットワークの最大流と最小カットの定義を学習し、それらの性質を調べる。
|
|
11
|
最大流、最小カットを求めるアルゴリズムを学ぶ。例題を自ら解くことによって理解を深めるようにしたい。
|
|
12
|
グラフの平面性の概念を学び、オイラーの公式を学習する。
|
|
13
|
グラフの彩色を学ぶ。Brooks の定理とその証明に現れる彩色アルゴリズムの理解を目指す。
|
|
14
|
グラフの辺彩色を学ぶ。Vizing の定理とその証明に現れるアルゴリズムの理解を目指す。
|
|
15
|
これまで学んできたことの復習と補足を行う。
|