【授業の目的】
離散数学分野の中から、現代情報科学を学ぶ上で必要不可欠なグラフ理論の基礎をわかりやすく解説する。
【授業の到達目標】
現代の情報科学・計算機科学の根幹を支える、有限的・離散的な構造を扱う数学のことを離散数学という。
この講義では離散数学の広い分野の中から、現代情報科学を学ぶ上で必要不可欠なテーマである、グラフ理論に焦点を当て、わかりやすく解説する。
【授業概要（キーワード）】
木、グラフ、マッチング、ネットワークフロー、連結度、彩色問題
【科目の位置付け】
システム情報学コース・カリキュラムにおける専門科目に属する。数学系の必修科目と、離散数学Aについて、予め取得しておくことが望ましい。
【授業計画】
・授業の方法
主として講義形式で行うが、一部に、演習形式を採り入れる。
・日程
第１回：用語の定義
第２回：オイラーグラフ
第３回：木と２部グラフの性質
第４回：縮約とマイナー
第５回：グラフの線形代数的取扱い
第６回：２部グラフのマッチング
第７回：一般のグラフのマッチング
第８回：ネットワークフロー（最大流最小カットの定理）
第９回：連結度その１（２連結グラフ・３連結グラフ）
第１０回：連結度その２（メンガーの定理）
第１１回：平面的グラフその１（オイラーの公式）
第１２回：平面的グラフその２（クラトウスキの定理）
第１３回：地図の塗り分け
第１４回：ブルックスの定理・ビジングの定理
第１５回：理想グラフ定理
【学習の方法】
・受講のあり方
講義は定理の証明が中心である。初出の概念や証明の難しい箇所を把握するためには、しっかりと板書をノートに取り、分からないことは、授業中に（授業の進行を妨げない程度に）質問するなどして、講義の時間内に解決しておくことが望ましい。
・授業時間外学習へのアドバイス
授業中に提示する参考書などで予習するとよい。
【成績の評価】
・基準
期末試験と授業中に実施する演習の得点を合算して評価得点を算出し，それをもとに評価を決定します．
・方法
期末試験 60％
授業中に実施する演習 40%
【テキスト・参考書】
参考書：R. ディーステル 著「グラフ理論」シュプリンガー・フェアラーク東京
参考書：R.J.ウィルソン 著「グラフ理論入門」近代数学社
参考書：松原・大島・藤田 他著「IT Text 離散数学」オーム社
参考書：榎本彦衛 著 「情報数学入門」新曜社
参考書：斎藤伸自・西関隆夫・千葉則茂 著 「離散数学」朝倉書店
【その他】
・オフィス・アワー
前期 木曜日 14時40分以降
後期 水曜日 16時20分以降
|