| 授業の目標と概要 |
・ソフトウエア開発やプログラミングにおいて，ソフトウエア化の対象となる実モデルや関係をグ
ラフツールを用いて定式化，解析する能力や，その問題に最適なデータ構造とアルゴリズムの構築
を行える能力の習得を目的とする．
|
履修上の注意
(準備する用具・
前提とする知識等)
|
・本科低学年で履修する情報数学（離散数学）の基礎知識を必須とする．
・ソーティング，検索など基本的アルゴリズムの知識を必須とする．
・手続き型のプログラミング言語の知識を習得していると望ましい．
|
| 到達目標 |
・グラフ構造の名称や基本的な特性について理解できる．
・グラフ，ネットワークが数理問題のモデル化ツールとして応用されることが理解できる．
・パス問題，木構築問題，彩色問題に関する定理や解法を理解できる．
|
| 成績評価方法 |
定期試験2回の成績で行う．
前期中間(50%)，前期期末(50%)
合否判定：最終評価（または，再試験の素点）≧60％
|
| テキスト・参考書 |
教科書：データ構造とアルゴリズム 五十嵐健夫 数理工学社
参考書：グラフ理論入門 R.J.ウイルソン 近代科学社
|
| メッセージ |
・基本的な離散数学・数論アルゴリズムの知識が必要である．
・手続き型のプログラミング言語についての知識を習得していると望ましい．
・講義は基本的にプロジェクタを利用して行う．
|
| 授業の内容 |
授業項目 | 授業項目ごとの達成目標 |
1. グラフ理論概論 単純グラフ，一般グラフ(2)
2. 握手定理，同形，除去，縮約(2)
3. グラフの種類（完全，二部，星，連結）(2)
4. 歩道，小道，道，カットセット，橋(2)
5. オイラーグラフ，セミオイラーグラフ(2)
6. ハミルトングラフ，セミハミルトングラフ(2)
7. 最短経路問題，郵便配達員問題(2)
|
1. グラフ理論における用語や定義を学習する．
2. 同形の意味や除去，縮約等の操作を理解する．
3. グラフの種類やその特性について理解する．
4. 歩道，小道，道，カット，橋の定義を理解する．
5. オイラーグラフの必要十分条件を理解する.
6. ハミルトン問題の困難性を理解する.
7. 最短経路問題，郵便配達員問題の解を導出できる.
|
| 前期中間試験 |
実施する
|
8. 木，林の定義 木の性質，全域木，閉路階級(2)
9. 深さ優先探索木，幅優先探索木(2)
10. 最小全域木問題，電気回路解析の応用(2)
11. 最大流量問題(2)
12. 平面グラフ，交差数，オイラーの公式(2)
13. グラフの厚さ 平面グラフに関する定理(2)
14. グラフの彩色問題，彩色数，Brooksの定理(2)
15. 面彩色と辺彩色，Vizingの定理(2)
|
8. 基本的な木構造の特性を理解する．
9. 深さ優先探索木，幅優先探索木を構築できる．
10. 最小全域木問題の解法や電気回路解析ができる．
11. 最大流量問題の解法を理解できる．
12. 平面グラフの特性や，その応用例を理解する．
13. 平面グラフに関する様々な定理を理解する．
14. 彩色問題の困難性やBrookの定理を理解する．
15. 面辺彩色の特性やVizingの定理を理解する．
|
| 前期期末試験 |
実施する
|