グラフ・ネットワークアルゴリズムの基礎 数理とCプログラム
グラフ・ネットワークアルゴリズムの基礎: 数理とCプログラム
近代科学社
著者：浅野孝夫
はじめに
第1章 グラフ表現のデータ構造
1.1 グラフの基礎概念
1.2 有向グラフの完備データ構造
1.3 有向グラフの完備データ構造構成のプログラム
1.4 無向グラフの標準的データ構造
1.5 無向グラフの標準的データ構造構成のプログラム
1.6 行列によるグラフの表現
1.7 演習問題
第2章 グラフ探索のアルゴリズム
2.1 グラフ探索
2.2 深さ優先探索と幅優先探索
2.3 有向グラフの深さ優先探索
2.3.1 有向グラフの深さ優先探索のプログラム
2.4 有向グラフの幅優先探索
2.4.1 有向グラフの幅優先探索のプログラム
2.5 無向グラフの深さ優先探索と幅優先探索
2.5.1 無向グラフの深さ優先探索木と幅優先探索木
2.6 無向グラフの深さ優先探索と幅優先探索のプログラム
2.7 深さ優先探索と幅優先探索の応用例
2.7.1 グラフが閉路をもつかどうかの判定
2.7.2 グラフが指定された2点を結ぶパスをもつかどうかの判定
2.7.3 無向グラフの連結成分分解
2.7.4 グラフの指定された2点を結ぶ辺数最小のパス
2.7.5 無向グラフが二部グラフであるかどうかの判定
2.8 演習問題
第3章 有向グラフの強連結成分分解
3.1 強連結成分分解
3.2 強連結成分分解のプログラム
3.3 凝縮グラフ
3.4 演習問題
第4章 トポロジカルソートと最長パス
4.1 有向無閉路グラフのトポロジカルソート
4.2 有向無閉路ネットワークでの最長パス
4.3 有向無閉路ネットワークの最長パス木を求めるプログラム
4.4 演習問題
第5章 オイラーグラフと一筆書き
5.1 オイラーグラフ
5.2 一筆書きを求めるアルゴリズム
5.3 有向グラフに対するアルゴリズムの実行例
5.4 有向オイラーグラフの一筆書きを求めるプログラム
5.5 無向グラフに対するアルゴリズムの実行例
5.6 無向オイラーグラフの一筆書きを求めるプログラム
5.7 演習問題
第6章 二部グラフの最大マッチング
6.1 最大マッチング
6.2 二部グラフの最大マッチングを求めるアルゴリズム
6.3 ホップクロフト－カープの高速アルゴリズム
6.4 ホップクロフト－カープのアルゴリズムのプログラム
6.5 演習問題
第7章 最短パス
7.1 最短パス問題
7.2 最短パスを求めるダイクストラのアルゴリズム
7.3 ダイクストラのアルゴリズムの正当性
7.4 ダイクストラの最短パスアルゴリズムのプログラム
7.5 演習問題
第8章 全点間の最短パス問題
8.1 全点間の最短パスを求めるワーシャル－フロイド法
8.2 ワーシャル－フロイド法のプログラム
8.3 演習問題
第9章 最小全点木
9.1 最小全点木を求めるクラスカルのアルゴリズム
9.2 クラスカルのアルゴリズムの正当性
9.3 クラスカルのアルゴリズムの計算時間
9.4 クラスカルのアルゴリズムののプログラム
9.5 演習問題
第10章 最大フローと最小カット
10.1 最大フローと最小カットの定義
10.2 最大フロー最小カット定理
10.3 残容量ネットワークと増加パス
10.4 フォード－ファルカーソンの最大フローアルゴリズム
10.5 二部グラフの最大マッチングと最大フローの関係
10.6 フォード－ファルカーソンの最大フローアルゴリズムのプログラム
10.7 演習問題
第11章 ディニッツの最大フローアルゴリズム
11.1 レベルネットワークと極大フロー
11.2 ディニッツの最大フローアルゴリズム
11.3 ディニッツの最大フローアルゴリズムの実行例
11.4 ディニッツの最大フローアルゴリズムの計算時間解析
11.5 ディニッツの最大フローアルゴリズムのプログラム
11.6 演習問題
第12章 需要付きフローと下界付きフロー
12.1 需要付きフロー
12.2 下界付きフロー
12.3 演習問題
第13章 最小費用フロー問題
13.1 最小費用フロー問題の定義
13.2 負の長さの閉路除去による最小費用フローアルゴリズム
13.3 最短パス計算による最小費用フローアルゴリズム
13.4 ダイクストラのアルゴリズムの適用
13.5 最小費用フローアルゴリズムのプログラム
13.6 演習問題
第14章 フロー問題の線形計画問題定式化
14.1 線形計画問題：主問題と双対問題
14.2 双対定理と相補性条件
14.2.1 相補性条件の成立することの確認
14.3 最大フロー問題の線形計画問題としての定式化
14.4 最小費用フロー問題の線形計画問題としての定式化
14.5 演習問題
演習問題回答
参考文献
索引