Web Syllabus(講義概要)

2019年度

ひとつ前のページへ戻る 教授名で検索

 
グラフ理論(Graph Theory) 上出 哲広
2年 後期 専門科目選択 2単位
【情電・後期】 19-1-1222-3816

1.
授業の概要(ねらい)・ディプロマポリシーとの関連

 本科目では、情報科学の基礎としてのグラフ理論を学習します。グラフ理論は、点や線を使った図形(グラフ)で問題を分析する数学です。主に、以下の項目について学習します。(1)グラフの種類(オイラーグラフ、ハミルトングラフ、木、平面的グラフ、有向グラフ、ネットワーク、2部グラフ、等)。(2)グラフの性質(連結性、巡回性、全域性、平面性、彩色可能性、向き付け可能性、マッチング、等)。(3)グラフ理論における代表的な定理(オイラーの一筆書き定理、Kratowskiの定理、4色定理、最大フロー・最小カット定理、Hallの定理、Mengerの定理、等)。
 本科目は、情報電子工学科のディプロマポリシー「自然科学の基礎的な知識を持ち、それを課題解決に活用することができる」に関連する科目です。

2.
授業の到達目標

 本科目では、グラフ理論における以下の項目について理解することを目標とします。(1)グラフの種類。(2)グラフの性質。(3)代表的な定理。学生自身が、上記項目について説明できるようになることを目標とします。

3.
成績評価の方法および基準・フィードバック方法

 期末試験(30パーセント)、中間試験(20パーセント)、小テスト(50パーセント、LMSで実施)により成績を評価します。100点満点で60点以上を合格とします。試験終了後、解答の一部を解説したビデオコンテンツを配信します。また、希望者には、試験終了後にオフィスアワーなどを利用して試験結果に関連する個別指導を実施します。

4.
教科書・参考書

教科書:
なし。LMS上に教材(ビデオコンテンツ、オンラインテスト、講義スライド、その他学習資料)を提示します。
参考書:
[1] R.J.ウィルソン(著)、西関隆夫、西関裕子(共訳)『グラフ理論入門(原書第4版)』(近代科学社)(ISBN: 4-7649-0296-6)。
[2] R.J Wilson『Introduction to graph theory (5th edition)』(Pearson education limited)(ISBN: 978-0273728894)。

5.
準備学修の内容・必要な時間

 本科目では、集合、行列および組み合わせ論の基礎知識を仮定します。これら内容について復習しておいてください。本科目では、毎回の授業で演習問題を多数出題します。それら問題を解くことによって、予習・復習に努めてください。また、各回において、LMS上で小テスト(オンラインテスト)を実施します。各回の授業後にこの小テストを受験して下さい。各回の授業のビデオコンテンツがLMS上で配信されます。授業で分からなかった内容についてはこれらビデオコンテンツで復習して下さい。また、授業の発展的内容に関するビデオコンテンツもLMS上で配信されます。さらに知識を深めたい場合は、それらビデオコンテンツを視聴して下さい。毎回の授業の教材(ビデオコンテンツ、オンラインテスト、講義スライドおよび補足資料)は、だいたい1週間前にLMSに提示されます。
 各回の予習と復習の目安は以下の通りです。予習として、次回の講義スライドおよびその他講義資料に目を通して疑問点をまとめて下さい(30分程度)。また、それら疑問点については授業前にオフィスアワーなどを利用して講師に質問することを勧めます。復習として、各回の小テストの受験、各回の演習問題への解答、および各回において授業で分からなかった部分に関するビデオコンテンツ視聴による復習を実施して下さい(2時間30分程度)。

6.
その他履修上の注意事項

 授業ではLMSを使用します。各回の学習資料がLMS上に提示されます。授業には必ずこれら学習資料をプリントアウトして持ち込んで下さい。また、授業期間中にLMSでアンケートを実施します。
 本科目はJABEE対応プログラムの必修科目で、学習・教育到達目標中項目4-1「コンピュータ科学に必要な離散構造、計算理論と情報の表現の理解」に対応しています。

7.
授業内容

【第1回】
導入: グラフ理論の概要・グラフ理論の応用
【第2回】
グラフの基礎概念: グラフの定義・グラフの種類
【第3回】
連結グラフ(1): オイラーグラフ・オイラーの一筆書き定理
【第4回】
連結グラフ(2): ハミルトングラフ・Oreの定理・Diracの定理
【第5回】
木: 全域木・木の応用・Cayleyの定理
【第6回】
平面的グラフ(1): オイラーの公式・Kratowskiの定理
【第7回】
平面的グラフ(2): 双対グラフ・曲面上のグラフ
【第8回】
無限グラフ: ケーニッヒの補題・中間試験
【第9回】
彩色問題(1): 点彩色・地図彩色・4色定理
【第10回】
彩色問題(2): 辺彩色・彩色多項式
【第11回】
有向グラフ(1): 向き付け可能性・オイラー有向グラフ・ハミルトン有向グラフ
【第12回】
有向グラフ(2): ネットワークとフロー・最大フロー最小カット定理
【第13回】
Hallの定理: 結婚問題・2部グラフ・横断理論・Hallの定理の応用
【第14回】
Mengerの定理: 連結性・非連結化集合・分離集合・Mengerの定理の応用
【第15回】
発展的話題・まとめ・期末試験