検索したい科目/教員名/キーワードを入力し「検索開始」ボタンをクリックしてください。
※教員名では姓と名の間に1文字スペースを入れずに、検索してください。
令和元年度以前入学者 | グラフ理論 | ||||
---|---|---|---|---|---|
教員名 | 齋藤明 | ||||
単位数 | 2 | 学年 | 2 | 開講区分 | 文理学部 |
科目群 | 情報科学科 | ||||
学期 | 後期 | 履修区分 | 選択必修 |
授業の形態 | 対面授業 BlackBoard コースID: 20224403 |
---|---|
授業概要 | 駅にある路線図やコンピュータネットワークのように、点が線で結ばれたものをグラフとよぶ。グラフは情報科学の様々な局面で現れる重要な概念である。この講義では、グラフに関する様々な話題を取り上げ解説する。あまり理論に深入りせず、工学的な応用に重点を置く。 |
授業のねらい・到達目標 | ・グラフ理論の基礎的な諸概念と代表的なアルゴリズムを理解し、運用することができる。 ・連結性の概念を理解し、応用することができる ・連結度の概念を把握できる。 ・最短路問題、ネットワークフローの問題を解くことができる。 この科目は文理学部(学士(理学))のディプロマポリシーDP3及びカリキュラムポリシーCP3に対応している。 |
授業の方法 | (1) 授業の形式:【 講義 】 板書とスライドにより基本事項を説明する。また適宜授業内課題を与える。与えた課題については、講義時間内に解説を行う。 (2) 対面授業に参加できない学生への代替方法、要件 対面授業に参加できない場合、以下の要件を満たす学生は、別途実施するオンライン授業(Zoom)への参加を認める。 オンライン授業への参加を認める要件:学部の方針に従う。 オンライン授業の方法:予め授業資料を渡し、対面授業とは別の時間枠で反転授業を行う。授業時間は受講者との協議の上で決めていく。 |
授業計画 | |
---|---|
1 |
グラフ理論への興味を持ってもらうため、パズルを2題ほど出題し、グラフを用いてそれらを解いてみる。
【事前学習】インターネットなどで「グラフ」という言葉の使われ方を調べる。 (1時間) 【事後学習】演習問題プリントの1番(握手問題の発展)を解く。 (3時間) |
2 |
グラフの定義と基本的な用語を学ぶ。頂点、辺、同形といった概念を学習する。
【事前学習】教科書8~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 |
第1回~第7回の内容に関する総合演習を行う。初めにテスト形式で演習を解いた後に、問題に対する解説を行う。
【事前学習】これまでに配布した演習の中で間違えたもの、理解不足を感じたものを解き直す。 (3時間) 【事後学習】講義の解説に従って、演習問題で間違えたもの、理解不足を感じたものを解き直す。 (1時間) |
9 |
木の定義を学び、その性質を調べる。またグラフの直径、半径、中心等の概念を学ぶ。
【事前学習】教科書 58~64 ページを読み、理解できなかった部分をノートに書き出しておく。 (1時間) 【事後学習】演習プリントの34番(木とグラフの直径、半径に関する問題)を解く。 (3時間) |
10 |
探索木の概念を学び、深さ優先探索のアルゴリズムを学ぶ。【対面】(A-5-2)
【事前学習】教科書 71~81 ページを読み、理解できなかった部分をチェックする。 (1時間) 【事後学習】演習プリントの34番(全域木を求める問題)を解く。 (3時間) |
11 |
ネットワークフローを学ぶ。特にネットワークの最大流と最小カットの定義を学習する。
【事前学習】教科書 116~121 ページを読み、理解できなかった部分をノートに書き出しておく。 (1時間) 【事後学習】演習プリントの34番(最大流を求める問題)を解く。 (3時間) |
12 |
最大流、最小カットを求めるアルゴリズムを学ぶ。
【事前学習】教科書 122~125 ページを読み、理解できなかった部分をノートに書き出しておく。 (1時間) 【事後学習】演習プリントの35番(最大流を求める問題)を解く。 (3時間) |
13 |
グラフの平面性の概念を学び、オイラーの公式を学習する。
【事前学習】教科書 85~95 ページを読み、理解できなかった部分をノートに書き出しておく。 (1時間) 【事後学習】演習プリントの35番(オイラーの公式)を解く。 (3時間) |
14 |
グラフの彩色を学ぶ。Brooks の定理とその証明に現れる彩色アルゴリズムの理解を目指す。
【事前学習】教科書 99~105 ページを読み、理解できなかった部分をノートに書き出しておく。 (1時間) 【事後学習】演習プリントの37番(Brooksの定理)を解く。 (3時間) |
15 |
グラフの辺彩色を学ぶ。Vizing の定理とその証明に現れるアルゴリズムの理解を目指す。
【事前学習】教科書 106~113 ページを読み、理解できなかった部分をノートに書き出しておく。 (2時間) 【事後学習】演習プリントの39番(Vizingの定理)を解く。 (2時間) |
その他 | |
---|---|
教科書 | なし |
参考書 | 加納幹雄 『情報科学のためのグラフ理論』 朝倉書店 2001年 第1版 |
成績評価の方法及び基準 | 試験(50%)、授業内テスト:第8回で実施する総合演習(20%)、毎回課す授業外演習の提出状況と内容(30%) 試験は15回の講義が全て終了した後に、独自に日時を設けて対面で試験を行う。その結果と第8回総合演習、授業外演習の提出状況・内容を元に評価する。 対面の試験を受験できない学生については、別途オンライン試験を実施する。オンライン試験の内容は対面で行う試験の内容と異なる。 |
オフィスアワー | 毎週火曜日 12:20~13:00 に研究室で行う。またメール([email protected])での質疑応答も受け付ける。 |
備考 | 演習プリントは毎年バージョンアップしている。授業計画の[事後学習]に挙げている演習プリントの番号は2021年度版に基づいているが、バージョンアップにより番号が変わることがある。その場合適宜およびBlackBoardにて周知する。 |