科目名 : グラフ理論

科目コード 90301
配当学年 (数)2年
開講期 前期
曜時限 木曜・2時限
講義室 総合研究8号館講義室2
単位数 2
履修者制限
講義形態 講義
言語
担当教員 永持,趙

講義概要

グラフとネットワークについて、その基本用語と性質、さらに最小木問題、最短路問題、最大フロー問題など、代表的な問題のアルゴリズムについて講述する。また、これらの応用例や、離散数学への展開についても言及する。

評価方法

レポートの評価と定期試験の点数の合計で評価する.

最終目標

グラフ構造に関する概念を知識として習得するだけでなく,離散構造に対する数学的性質の証明,計算法の仕組みなどの論理的メカニズムを理解する.

講義計画

項目 回数 内容説明
グラフとネットワーク 1 グラフとネットワークの基本用語の定義、さらにオイラーの一筆書き、ハミルトン閉路問題、グラフの同形性など代表的な問題を紹介する。
連結性 1 無向グラフのk-連結性、有向グラフの強連結性など、連結性の定義とその性質を考察する。
グラフの表現 1 グラフを入力するためのデータ表現として、隣接リストや行列による方法などを紹介する。
木とカットセット 1 全域木とカットセットの重要な性質、とくに基本閉路と基本カットセットの役割について述べる。
最小木 2 最小木を求める代表的なアルゴリズムとしてPrim法,Kruskal法を紹介し、そのデータ構造と計算量についても触れる。
グラフの探索 2 深さ優先探索と幅優先探索を導入し、応用例として、グラフの2連結成分を求めるアルゴリズムについて述べる。
最短路 1 最短路の性質と、代表的なアルゴリズムである Dijkstra 法を紹介する。
最大フロー 2 ネットワークにおける最大フローと最小カットの定理、さらに最大フローを求めるアルゴリズムについて述べる。
平面グラフと双対グラフ 1〜2 平面グラフを特徴づける Kratowski の定理、双対性と4色問題など、グラフの組合せ論的な話題に触れる。

教科書

指定なし

参考書

茨木:Cによるアルゴリズムとデータ構造(昭晃堂)

予備知識

集合に関する基本的な用語,アルゴリズムの計算量の考え方

授業URL

資料等をアップする際は次のURLを使う.URL: http://www-or.amp.i.kyoto-u.ac.jp/members/nag/

その他

授業期間を通して2~3回課題を出し、その解答をレポートとして提出させる。