離散数学２

「離散数学１」に続き，情報工学で必要となる数学的な概念，記法，論法を身につける．特に本科目では情報工学の様々な分野で用いられるグラフという概念について詳しく学ぶ．グラフ理論の基本的概念，性質を理解するとともに，簡単な証明を自分自身で組み立てられるようになることを目指す．

授業の目的

情報工学は情報という抽象的なものを対象とする学問であり、様々な科目の中で抽象的な記法や論理的な思考が必要となる。「離散数学１」に続いて本科目を履修することにより、本学科の専門科目を学んでいくための基礎知識を身につけることができる。

達成目標

1.	グラフに関する基本的概念を理解し，例を挙げて説明できるようになる．
2.	グラフの基本的な性質の証明を理解し，具体例に即して説明できるようになる．
3.	グラフの簡単な性質の証明（特に背理法，数学的帰納法を用いるもの）を自分で組み立てることができるようになる．

授業で使用する言語

授業計画

	【授業計画】	【授業時間外課題（予習および復習を含む）】
1.	グラフ理論の概要：　グラフとは，グラフの例	シラバスを確認する
2.	基本的概念（１）：　頂点と辺，同型，次数	教科書4.1節（事前に目を通しておく．また授業後に節末問題を解き理解を確認する．以下も同様）
3.	基本的概念（２）：　正則グラフ，完全グラフ，部分グラフ	教科書4.1節
4.	道と閉路（１）：　道，閉路，単純道，基本道	教科書4.2.1節
5.	道と閉路（２）：　隣接行列，距離，離心数，直径	教科書4.2.1節
6.	グラフの演習（１）：　ここまでの学習内容の問題演習	第1回〜第5回の復習（問題）
7.	中間試験と解説	第1回〜第6回の復習
8.	連結グラフ（１）：　連結，連結成分，連結グラフの性質	教科書4.2.2節
9.	連結グラフ（２）：　切断点，切断辺，2重連結	教科書4.2.3節
10.	木（１）：　森，木，木の性質	教科書4.3.6節
11.	木（２）：　根付き木，部分木，n分木	教科書4.3.6節
12.	グラフの演習（２）：　ここまでの学習内容の問題演習	第8回〜第11回の復習（問題）
13.	有向グラフ：　有向グラフの定義，次数，道と閉路，連結性	教科書3.4節
14.	発展的な話題：　いろいろなグラフ，データ構造とアルゴリズム	教科書4.3節，4.5節
15.	期末試験と解説	第8回〜第14回の復習