文理学部シラバスTOP > 文理学部 > 情報科学科（情報システム解析学科） > グラフ理論
日本大学ロゴ

グラフ理論

このページを印刷する

令和元年度以前入学者 グラフ理論
教員名 斎藤明
単位数    2 学年    2 開講区分 文理学部
（他学部生相互履修可）
科目群 情報科学科
学期 前期 履修区分 選択必修
授業の形態 オンデマンド型の遠隔授業（15回）
授業概要 駅にある路線図やコンピュータネットワークのように、点が線で結ばれたものをグラフとよぶ。グラフは情報科学の様々な局面で現れる重要な概念である。この講義では、グラフに関する様々な話題を取り上げ解説する。あまり理論に深入りせず、工学的な応用に重点を置く。
授業のねらい・到達目標 ・グラフ理論の基礎的な諸概念と代表的なアルゴリズムを理解し、運用することができる。
・連結性の概念を理解し、応用することができる。
・連結度の概念を把握できる。
・最短路問題、ネットワークフローの問題を解くことができる。


この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している。
授業の方法 講義と演習により進める。
演習ではプリントを配布する。プリントは授業内演習および宿題と事後学習に使用する。
宿題として課した問題は回収、添削し、返却する。
授業計画
1 グラフ理論への興味を持ってもらうため、パズルを２題ほど出題し、グラフを用いてそれらを解いてみる。
【事前学習】インターネットなどで「グラフ」という言葉の使われ方を調べる。 （1時間）
【事後学習】演習問題プリントの1番（握手問題の発展）を解く。 （3時間）
2 グラフの定義と基本的な用語を学ぶ。頂点、辺、同形といった概念を学習する。
【事前学習】教科書８～12ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの5番（グラフの位数）を解く、 （3時間）
3 近傍と次数の概念を学ぶ。また握手定理とその証明を学ぶ。
【事前学習】教科書 13～19 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの14番（次数列判定の計算問題）を解く。 （3時間）
4 次数列の概念と、その判定方法である Havel-Hakimi の定理を学ぶ。
【事前学習】教科書 19～26 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの15番（次数列の応用問題）を解く。 （3時間）
5 道、閉路といった概念を学ぶ。またグラフの連結性の概念を学習し、連結グラフの性質を調べる。
【事前学習】教科書 33～35 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの19番（連結性の概念）を解く。 （3時間）
6 グラフの連結度、辺連結度の概念を学ぶ。特に連結度、辺連結度、最小次数に関する不等式を学習する。
【事前学習】教科書 35～40 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの27番（連結度に関する問題）を解く。 （3時間）
7 グラフの最短路問題と、その解法であるダイクストラ法を学ぶ。
【事前学習】教科書 40～44 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの31番（ダイクストラ法の計算問題）を解く。 （3時間）
8 木の定義を学び、その性質を調べる。またグラフの直径、半径、中心等の概念を学ぶ。
【事前学習】教科書 58～64 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの34番（木とグラフの直径、半径に関する問題）を解く。 （3時間）
9 探索木の概念を学び、深さ優先探索のアルゴリズムを学ぶ。
【事前学習】教科書 71～81 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの34番（全域木を求める問題）を解く。 （3時間）
10 ネットワークフローを学ぶ。特にネットワークの最大流と最小カットの定義を学習する。
【事前学習】教科書 116～121 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの34番（最大流を求める問題）を解く。 （3時間）
11 最大流、最小カットを求めるアルゴリズムを学ぶ。
【事前学習】教科書 122～125 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの35番（最大流を求める問題）を解く。 （3時間）
12 グラフの平面性の概念を学び、オイラーの公式を学習する。
【事前学習】教科書 85～95 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの35番（オイラーの公式）を解く。 （3時間）
13 グラフの彩色を学ぶ。Brooks の定理とその証明に現れる彩色アルゴリズムの理解を目指す。
【事前学習】教科書 99～105 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの37番（Brooksの定理）を解く。 （3時間）
14 グラフの辺彩色を学ぶ。Vizing の定理とその証明に現れるアルゴリズムの理解を目指す。
【事前学習】教科書 106～113 ページを読み、理解できなかった部分をチェックする。 （1時間）
【事後学習】演習プリントの39番（Vizingの定理）を解く。 （3時間）
15 これまで学んできたことの復習と補足を行う。
【事前学習】配布する2019年度試験過去問を解いておく。 （2時間）
【事後学習】配布する2018年度試験過去問を解いておく。 （2時間）
その他
教科書 加納幹雄 『情報科学のためのグラフ理論』 朝倉書店 2001年 第1版
参考書 なし
成績評価の方法及び基準 試験(70%)、授業参画度:毎回課す宿題の提出状況と内容(30%)
試験は15回の講義が全て終了した後に、オンラインで試験を行う。その結果と宿題の提出状況・内容を元に評価する。
オフィスアワー 毎週火曜日の 12:10～13:00 をオンライン上でのオフィスアワーとする。具体的な方法は BlackBoard にて指示する。可能であれば電子メールにてアポイントを取ること。アポイントを取らずに来室することも可能だが、アポイントを取ってきた人がいる場合には、そちらを優先する。
備考 演習プリントは毎年バージョンアップしている。授業計画の[事後学習]に挙げている演習プリントの番号は2019年度版に基づいているが、バージョンアップにより番号が変わることがある。その場合適宜およびBlackBoardにて周知する。

↑このページのトップ