授業科目名 グラフ・ネットワーク理論
履修期 秋 2単位 履修基準年度 2年
授業目的
グラフ理論とネットワーク理論から，基礎的かつ重要な話題を選んで，数学的な基本事項を理解し，代表的なアルゴリズムを学ぶ．これらは情報科学のあらゆる分野で必要とされる基礎知識であるので，本講義を通じて理解を深めておくことが求められる．
到達目標
グラフやネットワークを用いた問題の定式化ができるようになる．基本的なグラフやネットワークの用語を理解する．グラフに関する基本的な最適化問題とその解法を理解する．
授業計画
第1回グラフと関連する概念
第2回グラフを歩く
第3回木とグラフの探索
第4回迷路を解こう
第5回グラフ上の最適化問題
第6回グラフ彩色と4色問題
第7回平面グラフと幾何学
第8回中間試験もしくは中間レポートの作成
第9回最小全域木とそのアルゴリズム
第10回動的計画法と最短路
第11回ダイクストラアルゴリズムとデータ構造
第12回グラフのカットとフロー
第13回フローとマッチング
第14回グラフ問題と線形代数・線形計画法
第15回定期試験もしくは期末レポート