科目分野	理工学部
選必区分	選択
担当教員 ［ローマ字表記］	伊藤　桃代　[Momoyo Itoh]
授業形態	講義

授業の目的

計算機科学の基礎である離散数学とグラフ理論を工学的立場から講義し，演習・レポートを通して理論と情報処理手法を修得させ，離散的手法の理解と応用力を育成する．

授業概要

グラフ理論は，離散数学を前提とし，エッジ（頂点）とノード（辺）の集合からなるグラフの性質を学ぶ学問である．従来と違った手法・方法論を学ぶためには，演習及び例題の解法が重要である．そこで講義と合わせて演習を行う．

到達目標

計算機の基礎としてグラフ の用語（次数，オイラーグラフ，木，ポーランド記法など），概念，手法などを説明できる．

授業計画

1. グラフと多重グラフ
2. 次数，連結度
3. ケーニヒスベルグの橋，周遊可能多重グラフ
4. 行列とグラフ
5. ラベル付グラフ
6. グラフの同形性
7. 1.～6.の演習問題と解法の説明
8. 地図，領域，オイラーの公式
9. 非平面的グラフ，クラトフスキーの定理
10. 彩色グラフ，四色定理
11. 木
12. 順序根付き木
13. ポーランド記法
14. 8.～13.の演習問題
15. 演習問題の解法の説明
16. 定期試験

教科書

離散数学―コンピュータサイエンスの基礎数学 (マグロウヒル大学演習)／Seymour Lipschutz (著), 成嶋 弘 (翻訳)：オーム社，Mar-95, ISBN:9784274130052

キーワード

グラフ, 木, ポーランド記法