| 情報 | 離散数学Ⅱ | 4年・通年・選択・学修2単位 | |
| 担当教員 | 蓬莱 尚幸 | 連絡先 | |
|---|---|---|---|
| 講義の概要 | 3年次で学んだ離散数学を基礎にグラフ理論について学び、グラフ理論がコンピュータとどのように結びついているのかを様々なアルゴリズムを通じて理解する。 | ||
| 到達目標 | 1. グラフ理論特有の表現や考え方に慣れ、理論的な証明ができるようになること。 2. アルゴリズムを理解し、そのアルゴリズムを適用できるようになること。 | ||
| 日程 | 授業項目 | 理解すべき内容 | 理解度 (1～4) | |
|---|---|---|---|---|
| 前期 | 第1週 | グラフの基礎(1) | グラフとパズル | |
| 第2週 | グラフの基礎(2) | グラフの定義 | ||
| 第3週 | グラフの基礎(3) | 次数と握手定理 | ||
| 第4週 | グラフの基礎(4) | 完全グラフ、完全2部グラフ | ||
| 第5週 | グラフの基礎(5) | グラフの和、結び、積、誘導部分グラフ | ||
| 第6週 | グラフの基礎(6) | 隣接行列 | ||
| 第7週 | （中間試験） | |||
| 第8週 | 最短経路と周遊問題(1) | 小道、道、回路、閉路、連結成分 | ||
| 第9週 | 最短経路と周遊問題(2) | グラフの連結度と辺連結度 | ||
| 第10週 | 最短経路と周遊問題(3) | ダイキストラ法による最短経路問題の解法 | ||
| 第11週 | 最短経路と周遊問題(4) | オイラー回路と郵便配達人問題 | ||
| 第12週 | 最短経路と周遊問題(5) | ハミルトン閉路と巡回セールスマン問題 | ||
| 第13週 | 木と全域木(1) | 木の定義と基本的な性質 | ||
| 第14週 | 木と全域木(2) | 木の中心と重心 | ||
| 第15週 | （期末試験） | |||
| 第16週 | 総復習 | |||
| 後期 | 第1週 | 木と全域木(3) | ラベルづけされた木の個数（ケーリーの定理） | |
| 第2週 | 木と全域木(4) | 根付き木と木の同形判定 | ||
| 第3週 | 木と全域木(5) | 全域木 | ||
| 第4週 | 木と全域木(6) | 最小重みの全域木を求める欲張りアルゴリズム | ||
| 第5週 | 平面グラフ(1) | オイラーの公式とその利用法 | ||
| 第6週 | 平面グラフ(2) | クラトウスキーの平面的グラフ判定定理 | ||
| 第7週 | （中間試験） | |||
| 第8週 | グラフの彩色(1) | グラフの点彩色と点染色数 | ||
| 第9週 | グラフの彩色(2) | グラフの辺彩色と辺染色数 | ||
| 第10週 | ネットワークと流れ(1) | 入口、出口、容量、流量 | ||
| 第11週 | ネットワークと流れ(2) | 最大流を求めるアルゴリズム | ||
| 第12週 | ネットワークと流れ(3) | 最大流・最小カット定理 | ||
| 第13週 | ネットワークと流れ(4) | グラフの辺素な道 | ||
| 第14週 | ネットワークと流れ(5) | グラフの内点素な道 | ||
| 第15週 | （期末試験） | |||
| 第16週 | 総復習 | |||
| 学習教育目標 | Ａに対応 | 達成項目 | 本科イ）に対応 | JABEE 認定基準 |
(A-1)，(c)に対応 |
|---|---|---|---|---|---|
| 教科書・参考書 | 教科書：加納幹雄「情報科学のためのグラフ理論」（朝倉書店） | ||||
| 評価方法及び合格基準 | 成績の評価は、定期試験の成績で行い、平均の成績が60点以上の者を合格とする。 | ||||
| 学生への メッセージ |
離散数学Ⅱでは情報科学の基礎理論の一つであるグラフ理論を学んでいきます。 予習：教科書当該部分の内容に目を通しておきましょう。 復習：教科書、講義資料(ppt)を見直し、理解不十分なところがあれば教員に聞くなどして解決しておきましょう。また、教科書の演習問題や課題にチャレンジしてみましょう。 | ||||