＊＊＊＊＊

科目名平成28年度入学者	＊＊＊＊＊
科目名平成27年度以前入学者	グラフ理論
教員名	斎藤　明
単位数	2	学年	2	開講区分	文理学部
科目群	情報科学科
学期	前期	履修区分	選択必修

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

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

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