グラフ理論
Graph Theory
准教授・緒方 広明
2単位
目的
計算機科学の基礎である離散数学とグラフ理論を工学的立場から講義し，演習·レポートを通して理論と情報処理手法を修得させ,離散的手法の理解と応用力を育成する.
概要
離散数学は，微分·積分の数学と違い，離散系を扱う数学であり，素朴集合論より導入する. 前提とする数学知識は，中学·高校で修得したもので充分である. しかし，従来と違った手法·方法論を学ぶためには，演習及び例題の解法が重要である.そこで講義と合わせて演習を行う．
キーワード
グラフ，木，ポーランド記法
先行科目
関連科目
要件
特になし
目標
| 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.リコー 著·成嶋 弘 他訳「-コンピュータサイエンスのための-離散数学入門」マグロウヒル社
連絡先
緒方(C507, 088-656-7498, ogata@is.tokushima-u.ac(no-spam).jp)
- オフィスアワー: 月曜日∼金曜日:午後5時∼6時
備考
| 1. | 平常点と試験の点=30:70 |
| 2. | 授業を受ける際には，2時間の授業時間毎に2時間の予習と2時間の復習をしたうえで授業を受けることが，授業の理解と単位取得のために必要である． |
| 3. | 授業計画1∼7は，中間テスト及びレポートにより達成度評価を行なう．授業計画9∼14は，最終試験およびレポートにより達成度評価を行なう． |