離散数学（Discrete Mathematics）[1T01]

＜授業のねらい＞

本講義では、離散数学の中でも重要な学問であるグラフ理論を学ぶ。理論だけではなく、アルゴリズムや応用についての理解も深める。グラフに関する基本的な知識を習得する。

＜受講にあたっての前提条件＞

特に必要となる前提条件はない。

＜具体的な到達目標＞

ネットワークに関する数々の問題を数理モデル化し、グラフ理論の知識を用いて解決できる。例えば電車の乗り換え案内やカーナビの経路探索のといった問題について、その裏側ではどのような理論が働いているのかを知り、それを関連する問題に応用することができる。

＜授業計画及び準備学習＞

以下の内容について解説する。いずれの内容についても、現実の問題への応用例を挙げて、常に応用を意識するようにする。ほぼ毎回宿題を課し、授業の復習ができるようにする。宿題は回収後に添削採点し、返却する。

1. グラフとは
2. グラフ理論における基本的な用語
3. 次数と近傍
4. 次数列
5. グラフの道と閉路
6. グラフの連結性
7. 連結度と辺連結度
8. 最短経路問題
9. 木
10. グラフの全域木
11. ネットワークフロー (1)
12. ネットワークフロー (2)
13. グラフの平面性
14. 補足事項の解説
15. 学習成果の確認

＜成績評価方法＞

毎回宿題を課す。宿題の提出状況を最大20点、提出された宿題の内容を最大10点、期末試験の成績を最大70点として計算する。この合計値が60点以上であった者を合格とする。

＜教科書＞

「情報科学のためのグラフ理論」 加納幹雄著（朝倉書店）

＜参考書＞

「離散構造」 根上生也著（共立出版）

＜オフィスアワー＞

質問は講義時間中に受け付ける。またメールによる質問も随時受け付ける。メールアドレスは授業初回に公開する。質問用のアドレスは以下である。
asaito@chs.nihon-u.ac.jp

＜学生へのメッセージ＞

宿題は60分以内で解ける程度の分量と難易度を目安とする。また期末試験では宿題の発展問題を出題する。すなわち毎回の宿題を解いていけば、それが自然に試験勉強につながるように配慮する。宿題をおろそかにせず、頑張って解いて欲しい。
また授業の最後に、次回の内容について教科書の対応ページを伝えるので、授業に出る前に 10 分程度でかまわないので、見ておいて欲しい。理解しようと精読する必要はない。目を通しておくだけで、授業の理解度が格段と高まるはずである。