授業の概要（ねらい）

　本科目では、情報科学の基礎としてのグラフ理論を学習します。グラフ理論は、点や線を使った図形（グラフ）で問題を分析する数学です。主に、以下の項目について学習します。（1）グラフの種類（オイラーグラフ、ハミルトングラフ、木、平面的グラフ、有向グラフ、ネットワーク、2部グラフ、等）。（2）グラフの性質（連結性、巡回性、全域性、平面性、彩色可能性、向き付け可能性、マッチング、等）。（3）グラフ理論における代表的な定理（オイラーの一筆書き定理、Kratowskiの定理、4色定理、最大フロー・最小カット定理、Hallの定理、Mengerの定理、等）。
　本科目は、情報電子工学科の以下のディプロマポリシーに関連する科目です。「自然科学の基礎的な知識を持ち、それを課題解決に活用することができる」。「ソフトウェアとしての情報システムを構築し運用することができる」。「幅広いメディア表現技術を応用し機能的で使い易いマルチメディアコンテンツを制作することができる」。本科目は、JABEE対応プログラムの必修科目で、学習・教育到達目標中項目「4-1. コンピュータ科学に必要な離散構造、計算理論と情報の表現の理解」に対応しています。

授業の到達目標

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

成績評価の方法および基準

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

教科書・参考文献

準備学修の内容

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

その他履修上の注意事項

　授業ではLMSを使用します。各回の学習資料がLMS上に提示されます。授業には必ずこれら学習資料をプリントアウトして持ち込んで下さい。また、授業期間中にLMSでアンケートを実施します。

授業内容