グラフ理論

科目名	グラフ理論
旧カリキュラム名	グラフ理論
教員名	齋藤　明
単位数	2	学年	2	開講区分	文理学部（他学部生相互履修可）
科目群	情報科学科
学期	前期	履修区分	選択必修

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

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

その他
教科書	恵羅博、小川健次郎、土屋守正、松井泰子『離散数学』横浜図書 2004年第1版
参考書	加納幹雄『情報科学のためのグラフ理論』朝倉書店 2001年第1版教科書は１年次の「離散数学」で用いた離散数学一般の教科書である。そのため本講義の内容を完全にはカバーしていない。教科書がカバーしていない内容については、他の書籍を入手せずとも理解できるように講義を進める。しかし興味のある学生は上記参考書を読んでみるとよい。
成績評価の方法及び基準	レポート(30%)、授業内テスト(70%) 上記15回の講義とは別の時間を設け、試験を行う。詳細は第12回の講義で述べる。
オフィスアワー	毎週火曜日及び水曜日の 12:10～13:00 をオフィスアワーとする。可能であれば電子メールにてアポイントを取ること。電子メールアドレスは授業初回時に伝える。アポイントを取らずに来室することも可能だが、アポイントを取ってきた人がいる場合には、そちらを優先する。