グラフ理論

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

授業概要	グラフ理論入門
授業のねらい・到達目標	駅にある路線図やコンピュータネットワークのように、点が線で結ばれたものをグラフとよぶ。グラフは情報科学の様々な局面で現れる重要な概念である。この講義では、グラフに関する様々な話題を取り上げ解説する。あまり理論に深入りせず、工学的な応用に重点を置く。本講義を通して、受講者はグラフ理論の基礎的な諸概念と代表的なアルゴリズムを理解し、運用することができるようになる。この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している。
授業の方法	講義と演習により進める。演習ではプリントを配布する。プリントは授業内演習および宿題と事後学習に使用する。本授業の事前・事後学習は，各２時間の学習を目安とする。

授業計画
1	グラフ理論への興味を持ってもらうため、パズルを２題ほど出題し、グラフを用いてそれらを解いてみる。 [事前学習] インターネットで「グラフ理論」を検索し、講義内容の大まかなイメージを想像しておこう。 [事後学習] 配布する演習プリントの１番を解くこと。
2	グラフの定義と基本的な用語を学ぶ。頂点、辺、同形といった概念を学習する。 [事前学習] 教科書の8～12ページを読んでおくこと。 [事後学習] 演習プリントの５番を解くこと。
3	近傍と次数の概念を学ぶ。また握手定理とその証明を学ぶ。 [事前学習] 教科書の13～19ページを読んでおくこと。 [事後学習] 演習プリントの９番を解くこと。
4	次数列の概念と、その判定方法である Havel-Hakimi の定理を学ぶ。 [事前学習] 教科書の19～26ページを読んでおくこと。 [事後学習] 演習プリントの14番を解くこと。
5	道、閉路といった概念を学ぶ。またグラフの連結性の概念を学習し、連結グラフの性質を調べる。 [事前学習] 教科書の33～35ページを読んでおくこと。 [事後学習] 演習プリントの20番を解くこと。
6	グラフの連結度、辺連結度の概念を学ぶ。特に連結度、辺連結度、最小次数に関する不等式を学習する。 [事前学習] 教科書の35～40ページを読んでおくこと。 [事後学習] 演習プリントの26番を解くこと。
7	グラフの最短路問題と、その解法であるダイクストラ法を学ぶ。 [事前学習] 教科書の40～44ページを読んでおくこと。 [事後学習] 演習プリントの30番を解くこと。
8	木の定義を学び、その性質を調べる。またグラフの直径、半径、中心等の概念を学ぶ。 [事前学習] 教科書の58～64ページを読んでおくこと。 [事後学習] 演習プリントの32番を解くこと。
9	探索木の概念を学び、深さ優先探索のアルゴリズムを学ぶ。 [事前学習] 教科書の71～81ページを読んでおくこと。 [事後学習] 演習プリントの34番を解くこと。
10	ネットワークフローを学ぶ。特にネットワークの最大流と最小カットの定義を学習する。 [事前学習] 教科書の116～121ページを読んでおくこと。 [事後学習] 演習プリントの35番を解くこと。
11	最大流、最小カットを求めるアルゴリズムを学ぶ。 [事前学習] 教科書の122～125ページを読んでおくこと。 [事後学習] 演習プリントの36番を解くこと。
12	グラフの平面性の概念を学び、オイラーの公式を学習する。 [事前学習] 教科書の85～95ページを読んでおくこと。 [事後学習] 演習プリントの37番を解くこと。
13	グラフの彩色を学ぶ。Brooks の定理とその証明に現れる彩色アルゴリズムの理解を目指す。 [事前学習] 教科書の99～105ページを読んでおくこと。 [事後学習] 演習プリントの39番を解くこと。
14	グラフの辺彩色を学ぶ。Vizing の定理とその証明に現れるアルゴリズムの理解を目指す。 [事前学習] 教科書の106～113ページを読んでおくこと。 [事後学習] 演習プリントの40番を解くこと。
15	これまで学んできたことの復習と補足を行う。 [事前学習] 前回配布した2018年度の試験問題を解いておくこと。 [事後学習] 配布する2017年度の試験問題を解いておくこと。

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