グラフ理論
担当者上出 哲広教員紹介
学年・開講期2年次 後期  [理工学部 情報電子工学科]
科目の種類専門
区分・単位選択 2単位
科目ナンバー3C222

授業の概要(ねらい)

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

授業の到達目標

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

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

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

教科書・参考文献

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

準備学修の内容

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

その他履修上の注意事項

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

授業内容

授業内容
第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回発展的話題・まとめ・期末試験