授業科目名 : グラフ理論

科目コード 90301
配当学年 (数)2年
開講年度・開講期 平成30年度・前期
曜時限 木曜・2時限
講義室 総合研究8号館講義室2
単位数 2
履修者制限
授業形態 講義
使用言語 日本語
担当教員    所属・職名・氏名 情報学研究科・教授・永持仁

授業の概要・目的

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

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

講義では原則,毎回,3~5分程度で解答するミニ演習を課し,解答はその講義終了時に提出してもらう.このミニ演習の提出全回分の評価(30点満点)と定期試験の点数(70点満点)の合計(100点満点)で評価する.

到達目標

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

授業計画と内容

項目 回数 内容説明
グラフとネットワーク 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/

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

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