グラフ理論特論

駅にある路線図やコンピュータネットワークのように，いくつかの点とそれらを結ぶ辺からなる図形をグラフという。グラフは自然科学の様々な局面で現れる重要な概念であり，現代の社会を数学的に解析する手段のひとつとして，極めて有効である。また，グラフ理論はグラフの構造を解析する数理科学の一分野である。グラフ理論は自然科学のみならず，工学あるいは社会科学上の問題における要素間の関係を点と辺で表すことにより，直面している問題の見通しを立てやすくし，与えられえた問題の難しさを解析・評価する道具にもなり得る。システム理工学専攻の学生諸氏にとって，こうした概念を獲得するのは有益と考える。取り扱う主な内容は，下記のとおりである。

グラフ理論の基礎とその応用について理解を深める。

1．	マッチングと因子について理解する。
2．	連結度について理解する。
3．	平面的グラフについて理解する。
4．	ハミルトン閉路について理解する。

日本語（英語対応も可）

	【授業計画】	【授業時間外課題（予習および復習を含む）】
1．	グラフの基本用語の確認（グラフ，次数，道と閉路）	グラフの次数，道と閉路の定義を確認しておくこと。また，授業中に出した問題を解く。
2．	グラフの基本用語の確認（連結度，木と林，二部グラフ，縮約とマイナー）	グラフの連結度，木，林の定義を確認しておくこと。また，授業中に出した問題を解く。
3．	二部グラフにおけるマッチング	グラフのマッチングの定義を調べておくこと。また，授業中に出した問題を解く。
4．	一般のグラフにおけるマッチング	二部グラフに完全マッチングが存在するための必要十分条件を復習しておく。
5．	グラフの木構造	グラフの木の定義を確認しておくこと。
6．	平面的グラフの基本的概念	平面的グラフと平面グラフの定義を調べ，それらの違いを理解しておくこと。
7．	平面的グラフにおける諸定理	授業中に出した問題を解く。
8．	グラフ彩色	グラフにおける彩色の定義を調べておくこと。また，授業中に出した問題を解く。
9．	四色問題の歴史的考察とケンペの誤った証明	四色問題とは何かを調べておくこと。
10．	四色定理とグラフマイナー	授業中に出した問題を解く。
11．	オイラーグラフとその構造	オイラーグラフの定義を確認しておくこと。また，授業中に出した問題を解く。
12．	ハミルトン閉路	ハミルトン閉路の定義を確認しておくこと。
13．	ハミルトングラフの工学的応用，特に，巡回セールスマン問題を中心として	巡回セールスマン問題とは何かを調べておくこと。
14．	グラフの工学的応用の考察	巡回セールスマン問題を復習しておくこと。
15．	期末試験とその解説	これまでの内容を総復習。

レポートが50パーセント，期末試験が50パーセントとして，総合得点の60パーセント以上を合格とする。

教科書は指定せず，毎回配布する資料を基づいて，授業を進める。
参考書は次のとおりである。
グラフ理論，R.ディーステル著，根上生也/太田克弘訳

グラフ理論の基礎知識は前提としないが，数学的帰納法や背理法といった証明手法は自然に使えることが望ましい。

・	水曜日18:00-19:00 その他，研究室在室中は基本的に受け付ける。

環境に関連しない科目

地域志向ではない科目

・	知識活用力を育成する科目
・	対課題基礎力を育成する科目

能動的な学修への参加による授業が概ね半数

最終更新 : Thu Jun 09 09:22:03 JST 2016

開講部	大学院理工学研究科　修士課程
開講学科	システム理工学専攻
開講学年	1年次
開講時期	後期
単位数	2
単位区分	特修
系列区分	特論
講義区分	講義

6M008200

授業の概要

授業の目的

達成目標

授業で使用する言語

授業計画

評価方法と基準

教科書・参考書

履修登録前の準備

オフィスアワー、質問・相談の方法

環境との関連

地域志向

社会的・職業的自立力の育成

アクティブ・ラーニング科目