グラフ理論入門
Discrete Mathematics and Graph Theory 2
目的
計算機科学の基礎であるグラフ理論を工学的立場から講義をおこないます．ただし，授業では演習·レポートを通じてグラフの考えを修得し,離散的手法の理解と応用力を育成します.
概要
グラフ理論入門では，計算機科学における基本的な概念であるグラフについて学んでいきます．ネットワーク，人工知能等様々な応用分野でこのグラフの考え方が出て来ます．また，グラフ理論入門では数学の問題として有名な四色問題も簡単に扱います．
キーワード
オイラーグラフ，ハミルトングラフ，平面的グラフ，4色定理，木
先行科目
関連科目
要件
特になし
目標
| 1. | 計算機の基礎として離散数学とグラフ の用語，概念，手法と応用力の習得を目標とする. |
計画
| 1. | グラフと多重グラフ |
| 2. | 次数，連結度 |
| 3. | ケーニヒスベルグの橋，周遊可能多重グラフ |
| 4. | 行列とグラフ |
| 5. | ラベル付グラフ |
| 6. | グラフの同形性 |
| 7. | 地図，領域，オイラーの公式 |
| 8. | 1.∼7.の演習問題と解法の説明 |
| 9. | 非平面的グラフ，クラトフスキーの定理 |
| 10. | 彩色グラフ，四色定理 |
| 11. | 木 |
| 12. | 順序根付き木 |
| 13. | 9.-12.の演習問題と解法の説明 |
| 14. | 演習問題の解法の説明，講義全体のまとめ |
| 15. | 定期試験 |
| 16. | 返却と解説 |
評価
レポートの提出状況と内容，講義中の質問の回答も評点の対象となる. 試験では以下の「持ち込み用紙」一枚を認める. 1)自筆で，コピーは不可 2)B5サイズ，表裏記入可 3)表裏に学年·出席番号·氏名を明記すること．「持ち込み用紙」は，講義及び教科書の内容を自分でまとめたものである．作成に際しては何色を使ってもよい．
対象学生
開講コース学生のみ履修可能
教科書
リブシュッツ 著·成嶋 弘 監訳「離散数学-コンピュータサイエンスの基礎数学-」オーム社
参考資料
C.L.リコー 著·成嶋 弘 他訳「-コンピュータサイエンスのための-離散数学入門」マグロウヒル社
連絡先
金西(大学開放実践センター2階, 088-656-7610, marukin@cue.tokushima-u.ac(no-spam).jp)
備考
平常点と試験の点＝30:70 学習進度の状況によっては中間試験を行うことがある．