授業科目名 : グラフ理論

科目コード 90300
配当学年 (計)2年
開講年度・開講期 平成30年度・後期
曜時限 木曜・4時限
講義室 総合研究8号館NSホール
単位数 2
履修者制限 無し
授業形態 講義
使用言語 日本語
担当教員    所属・職名・氏名 学術情報メディアセンター・准教授・宮崎修一

授業の概要・目的

グラフ・ネットワーク理論の基礎と応用、それに関する基礎的なアルゴリズムについて学ぶ。

成績評価の方法・観点及び達成度

主に期末試験によって評価するが、出席、レポート、講義中の発言なども考慮する場合がある。

到達目標

グラフ・ネットワーク理論の基礎と応用、それに関する基礎的なアルゴリズムについて学ぶことを目標とする。

授業計画と内容

項目 回数 内容説明
グラフの基礎 4 グラフとは何かを説明するとともに、グラフの基本的性質について説明する。
最小全域木 1 最小全域木を求めるクラスカルのアルゴリズムおよびプリムのアルゴリズムを説明する。また、類似問題としてスタイナー木問題を紹介する。
最短経路問題 1 最短経路問題を解くダイクストラのアルゴリズムを説明する。
オイラー回路とハミルトン閉路 2 オイラー回路とハミルトン閉路について説明する。オイラー回路が存在するための必要十分条件について考える。また、ハミルトン閉路を持つための十分条件であるディラックの定理、オーレの定理を説明する。
グラフの彩色 2 グラフの頂点彩色および辺彩色について考える。頂点彩色数や辺彩色数に関する定理を紹介する(ブルックスの定理、ビジングの定理、ケーニッヒの定理等)。関連して、地図の彩色問題についても紹介する。
最大流問題 2 最大フローを見つけるフォード-ファルカーソンのアルゴリズムを紹介する。
マッチング 2 グラフのマッチング、主に二部グラフのマッチングについて考える。完全マッチングを持つための必要十分条件であるホールの定理や、最大サイズマッチングを求めるハンガリアン法を紹介する。
学習到達度の確認 1

教科書

グラフ理論入門 ~基本とアルゴリズム~, 宮崎修一,森北出版株式会社

参考書等

授業中に紹介する。

履修要件

アルゴリズムやデータ構造、集合論などの基本的知識

授業外学習(予習・復習)等

授業URL

その他(オフィスアワー等)