グラフ理論

科目名	グラフ理論
教員名	齋藤明
単位数	2	学年	2	開講区分	文理学部
科目群	情報科学科
学期	後期	履修区分	選択必修

授業テーマ	グラフ理論入門
授業のねらい・到達目標	駅にある路線図やコンピュータネットワークのように、点が線で結ばれたものをグラフとよぶ。グラフは情報科学の様々な局面で現れる重要な概念である。この講義では、グラフに関する様々な話題を取り上げ解説する。あまり理論に深入りせず、工学的な応用に重点を置く。受講者はグラフ理論の基礎的な諸概念と代表的なアルゴリズムを理解し、運用する力を身につける。
授業の方法	講義と演習により進める。
事前学修・事後学修，授業計画コメント	事前学修：毎回の講義の終わりに、次に進む内容と対応する教科書のページを伝えるので、授業を受ける前にそのページを読んでおき、分からない箇所に印をつけておくこと。事後学修：毎回授業内容の復習となる宿題を課す。宿題は次回授業時に提出する。

授業計画
1	グラフ理論への興味を持ってもらうため、パズルを２題ほど出題し、グラフを用いてそれらを解いてみる。 [準備] 「離散数学」で学んだ内容を復習しておくこと。
2	グラフの定義と基本的な用語を学ぶ。頂点、辺、同形といった概念を学習する。 [準備] 教科書の8～12ページを読んでおくこと。
3	近傍と次数の概念を学ぶ。また握手定理とその証明を学ぶ。 [準備] 教科書の13～19ページを読んでおくこと。
4	完全グラフ、２部グラフなど特殊なグラフの定義とそれらの性質を学ぶ。また２つ以上のグラフから１つのグラフを作り出す演算操作もいくつか学ぶ。 [準備] 教科書の19～26ページを読んでおくこと。
5	道、閉路といった概念を学ぶ。またグラフの連結性の概念を学習し、連結グラフの性質を調べる。 [準備] 教科書の33～35ページを読んでおくこと。
6	グラフの連結度、辺連結度の概念を学ぶ。特に連結度、辺連結度、最小次数に関する不等式を学習する。 [準備] 教科書の35～40ページを読んでおくこと。
7	グラフの最短路問題と、その解法であるダイクストラ法を学ぶ。実際の例題を解くことで理解を深めたい。 [準備] 教科書の40～44ページを読んでおくこと。
8	木の定義を学び、その性質を調べる。またグラフの直径、半径、中心等の概念を学ぶ。 [準備] 教科書の58～64ページを読んでおくこと。
9	探索木の概念を学び、深さ優先探索のアルゴリズムを学ぶ。 [準備] 教科書の71～81ページを読んでおくこと。
10	ネットワークフローを学ぶ。ネットワークの定義から入り、ネットワークの最大流と最小カットの定義を学習し、それらの性質を調べる。 [準備] 教科書の116～121ページを読んでおくこと。
11	最大流、最小カットを求めるアルゴリズムを学ぶ。例題を自ら解くことによって理解を深めるようにしたい。 [準備] 教科書の122～125ページを読んでおくこと。
12	グラフの平面性の概念を学び、オイラーの公式を学習する。 [準備] 教科書の85～95ページを読んでおくこと。
13	グラフの彩色を学ぶ。Brooks の定理とその証明に現れる彩色アルゴリズムの理解を目指す。 [準備] 教科書の99～105ページを読んでおくこと。
14	グラフの辺彩色を学ぶ。Vizing の定理とその証明に現れるアルゴリズムの理解を目指す。 [準備] 教科書の106～113ページを読んでおくこと。
15	これまで学んできたことの復習と補足を行う。

その他
教科書	加納幹雄『情報科学のためのグラフ理論』朝倉書店 2001年第1版
参考書	なし
成績評価の方法及び基準	授業内テスト(70%)、授業参画度(30%) 上記15回の講義とは別の時間を設け、試験を行う。詳細は第12回の講義で述べる。授業参画度は宿題の提出状況と解答状況で評価する。
オフィスアワー	毎週火曜日及び水曜日の 12:10～13:00 をオフィスアワーとする。可能であれば電子メールにてアポイントを取ること。電子メールアドレスは授業初回時に伝える。アポイントを取らずに来室することも可能だが、アポイントを取ってきた人がいる場合には、そちらを優先する。