担当者 | 上出 哲広 | |
---|---|---|
学年・開講期 | 2年次 Ⅰ・Ⅲ [理工学部 情報科学科(通信課程)] | |
科目の種類 | 専門基礎 | |
クラス | メディア授業 | |
区分・単位 | 選択 2単位 | |
科目ナンバー | 2B203 |
本科目では、情報科学の基礎としてのグラフ理論を学習します。グラフ理論は、点や線を使った図形で問題を分析する数学です。主に、以下の項目について学習します。(1)グラフの種類(オイラーグラフ、ハミルトングラフ、木、平面的グラフ、有向グラフ、2部グラフ、等)。(2)グラフの性質(巡回性、全域性、平面性、彩色可能性、向き付け可能性、連結性、等)。(3)グラフ理論における代表的な定理(オイラーの一筆書き定理、Kratowskiの定理、4色定理、最大フロー・最小カット定理、Hallの定理、Mengerの定理、等)。
本科目は、情報科学科(通信教育課程)のディプロマポリシー「2.現代の情報工学、情報システムの理論から応用までを修得し、現代の高度情報化社会に有効に活用できる」に関連する科目です。
本科目では、グラフ理論における以下の項目を理解することを目標とします。(1)グラフの種類。(2)グラフの性質。(3)代表的な定理。
科目習得試験、中間試験(LMSで実施)、小テスト(LMSで実施)により成績を評価します。科目習得試験30パーセント、中間試験20パーセント、小テスト50パーセントで評価します。希望者には試験の結果に関するコメントをメールでフィードバックします。疑問点や意見がある場合は私にメールで知らせて下さい。
種別 | 書名 | 著者・編者 | 発行所 |
---|---|---|---|
教科書 | なし。講義資料をLMSに提示します。ビデオコンテンツおよびそれに対応するスライド資料をLMSに提示します。その他、補足資料もLMSに提示します。 | ||
参考文献 | グラフ理論入門(原書第4版) | R.J. ウィルソン(著)、西関隆夫・西関裕子(共訳) | 近代科学社 (ISBN: 4-7649-0296-6) |
参考文献 | Introduction to graph theory (5th edition) | R.J Wilson | Pearson education limited(ISBN: 978-0273728894) |
講義資料はLMSから各自ダウンロードして下さい。各回で小テストを(LMSで)実施します。中間試験を(LMSで)実施します。自分の興味のあるところを中心に準備学習して下さい。いくつかの回のフォルダには、補足資料を添付してあります。それらの中で興味のあるものがあれば予習として読むことを勧めます(1時間程度)。復習としては、LMS上の小テストを受験してください(30分程度)。また、中間試験・科目習得試験・小テストの各範囲をLMSの資料やビデオコンテンツで繰り返し学習して下さい(1時間30分程度)。
ビデオコンテンツおよびそれに対応するスライド資料をLMSに提示します。その他、補足資料もLMSに提示します。
回 | 授業内容 |
---|---|
第1回 | 導入: グラフ理論とは・グラフ理論の概要 |
第2回 | グラフの基礎概念: グラフの定義・グラフの種類 |
第3回 | 連結グラフ(1): オイラーグラフ・オイラーの一筆書き定理 |
第4回 | 連結グラフ(2): ハミルトングラフ・Oreの定理・Diracの定理 |
第5回 | 木: 全域木・木の応用 |
第6回 | 平面的グラフ(1): オイラーの公式・Kratowskiの定理 |
第7回 | 平面的グラフ(2): 双対グラフ・曲面上のグラフ |
第8回 | 無限グラフ・中間試験 |
第9回 | 彩色問題(1): 点彩色・地図彩色・4色定理 |
第10回 | 彩色問題(2): 辺彩色・彩色多項式 |
第11回 | 有向グラフ(1): 向き付け可能性・オイラー有向グラフ・ハミルトン有向グラフ |
第12回 | 有向グラフ(2): ネットワーク・フロー・最大フロー最小カット定理 |
第13回 | Hallの定理: 2部グラフによる形式化・横断理論による形式化・Hallの定理の応用 |
第14回 | Mengerの定理: 点形のMengerの定理・辺形のMengerの定理・Mengerの定理の応用 |
第15回 | 複雑ネットワーク: スモールワールドモデル・バラバシ=アルバートモデル |