科目名 : グラフ理論

科目コード 90300
配当学年 (計)2年
開講期 後期
曜時限 木曜・4時限
講義室 総合研究8号館NSホール
単位数 2
履修者制限 無し
講義形態 講義
言語
担当教員 宮崎修一

講義概要

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

評価方法

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

最終目標

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

講義計画

項目 回数 内容説明
グラフ、アルゴリズム 3 グラフとは何かを説明するとともに、グラフの基本的性質について説明する。また、アルゴリズムとは何か、アルゴリズムの評価尺度などについて説明する。
最小全域木 2 クラスカルのアルゴリズム、プリムのアルゴリズム。スタイナー木問題。
最短経路問題 1 ダイクストラのアルゴリズム。
ハミルトン閉路問題 2 ディラックの定理。
彩色問題 2 頂点彩色問題、辺彩色問題。
最大流問題 2 フォード-ファルカーソンの増大路法。
マッチング 2 Hallの定理。ハンガリアン法。
学習到達度の確認 1

教科書

指定しない。

参考書

授業中に紹介する。

予備知識

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

授業URL

その他