科目名 : グラフ理論

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

講義概要

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

評価方法

演習の回答の評価と定期試験の点数の合計で評価する.

最終目標

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

講義計画

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

教科書

指定なし

参考書

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

予備知識

集合に関する基本的な用語,アルゴリズムの計算時間に対するオーダー表記

授業URL

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

その他

講義中に演習を行う。また,演習やテストの内容に関する解答や到達度を確認(講評)する。