| １． |
授業の概要（ねらい）・ディプロマポリシーとの関連 |
|
本科目では、情報科学の基礎としてのグラフ理論を学習します。グラフ理論は、点や線を使った図形で問題を分析する数学です。主に、以下の項目について学習します。（1）グラフの種類（オイラーグラフ、ハミルトングラフ、木、平面的グラフ、有向グラフ、2部グラフ、等）。（2）グラフの性質（巡回性、全域性、平面性、彩色可能性、向き付け可能性、連結性、等）。（3）グラフ理論における代表的な定理（オイラーの一筆書き定理、Kratowskiの定理、4色定理、最大フロー・最小カット定理、Hallの定理、Mengerの定理、等）。
本科目は、情報科学科（通信教育課程）のディプロマポリシー「2．現代の情報工学、情報システムの理論から応用までを修得し、現代の高度情報化社会に有効に活用できる」に関連する科目です。
|
| ２． |
授業の到達目標 |
|
本科目では、グラフ理論における以下の項目を理解することを目標とします。（1）グラフの種類。（2）グラフの性質。（3）代表的な定理。
|
| ３． |
成績評価の方法および基準・フィードバック方法 |
|
期末試験、中間試験（LMSで実施）、小テスト（LMSで実施）により成績を評価します。期末試験30パーセント、中間試験20パーセント、小テスト50パーセントで評価します。希望者には試験の結果に関するコメントをメールでフィードバックします。疑問点や意見がある場合は私にメールで知らせて下さい。
|
| ４． |
教科書・参考書 |
|
講義資料をLMSに提示します。ビデオコンテンツおよびそれに対応するスライド資料をLMSに提示します。その他、補足資料もLMSに提示します。
参考資料を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)。
|
| ５． |
準備学修の内容・必要な時間 |
|
講義資料はLMSから各自ダウンロードして下さい。各回で小テストを（LMSで）実施します。中間試験を（LMSで）実施します。自分の興味のあるところを中心に準備学習して下さい。いくつかの回のフォルダには、補足資料を添付してあります。それらの中で興味のあるものがあれば予習として読むことを勧めます（1時間程度）。復習としては、LMS上の小テストを受験してください（30分程度）。また、中間試験・期末試験・小テストの各範囲をLMSの資料やビデオコンテンツで繰り返し学習して下さい（1時間30分程度）。
|
| ６． |
その他履修上の注意事項 |
|
ビデオコンテンツおよびそれに対応するスライド資料をLMSに提示します。その他、補足資料もLMSに提示します。
|
| ７． |
授業内容 |
|
| 【第１回】 | | 導入： グラフ理論とは・グラフ理論の概要 | | 【第２回】 | | グラフの基礎概念： グラフの定義・グラフの種類 | | 【第３回】 | | 連結グラフ（1）： オイラーグラフ・オイラーの一筆書き定理 | | 【第４回】 | | 連結グラフ（2）： ハミルトングラフ・Oreの定理・Diracの定理 | | 【第５回】 | | 木： 全域木・木の応用 | | 【第６回】 | | 平面的グラフ（1）： オイラーの公式・Kratowskiの定理 | | 【第７回】 | | 平面的グラフ（2）： 双対グラフ・曲面上のグラフ | | 【第８回】 | | 無限グラフ・中間試験 | | 【第９回】 | | 彩色問題（1）： 点彩色・地図彩色・4色定理 | | 【第10回】 | | 彩色問題（2）： 辺彩色・彩色多項式 | | 【第11回】 | | 有向グラフ（1）： 向き付け可能性・オイラー有向グラフ・ハミルトン有向グラフ | | 【第12回】 | | 有向グラフ（2）： ネットワーク・フロー・最大フロー最小カット定理 | | 【第13回】 | | Hallの定理： 2部グラフによる形式化・横断理論による形式化・Hallの定理の応用 | | 【第14回】 | | Mengerの定理： 点形のMengerの定理・辺形のMengerの定理・Mengerの定理の応用 | | 【第15回】 | | 複雑ネットワーク： スモールワールドモデル・バラバシ=アルバートモデル |
|
