1 グラフとネットワーク 1 |
1.1 基礎概念と用語 1 |
1.2 グラフの連結性 10 |
1.3 アルゴリズムと計算量 17 |
1.4 グラフの探索 22 |
1.5 オイラーの一筆書き 27 |
1.6 最小木問題 29 |
1.7 最短路問題 32 |
演習問題 35 |
2 ネットワークフロー 37 |
2.1 フローの定義と性質 37 |
2.2 最大フロー問題 41 |
2.3 最大マッチング問題 45 |
2.4 最大フローのアルゴリズム 49 |
2.5 層ネットワークによる最大フローアルゴリズム 50 |
2.6 前フローを用いた最大フローアルゴリズム 56 |
演習問題 63 |
3 最小カットと連結度 67 |
3.1 メンガーの定理 67 |
3.2 最小カットと連結度の計算 69 |
3.3 辺連結度と点連結度の統合 72 |
演習問題 73 |
4 グラフのカット構造 76 |
4.1 ゴモリ・フー木 76 |
4.2 極点集合 83 |
4.3 カクタス表現 86 |
演習問題 89 |
5 最大隣接順序と森分解 91 |
5.1 連結度を保存する全域部分グラフ 91 |
5.2 最大隣接順序 95 |
5.3 最大隣接順序による森分解 99 |
5.4 疎構造化 102 |
5.5 疎構造化による連結度アルゴリズムの改良 107 |
演習問題 108 |
6 無向グラフの最小カット 110 |
6.1 ペンダント対 110 |
6.2 最大隣接順序による最小カットアルゴリズム 113 |
6.3 最小カットの諸アルゴリズムと実用上の工夫 116 |
6.4 ペンダント対間の最大フロー 121 |
演習問題 127 |
7 最小カットの力クタス表現 130 |
7.1 カクタス表現の標準形 130 |
7.2 カクタス表現の結合 136 |
7.3 (s,t)-カクタス表現を構成するアルゴリズム 139 |
7.4 全最小カットのカクタス表現を構成するアルゴリズム 147 |
演習問題 156 |
8 極点集合とその応用 158 |
8.1 フラット対と最小次数順序 158 |
8.2 極点集合の計算 161 |
8.3 最小κ-部分分割問題 164 |
8.4 最小κ-カット問題に対する近似アルゴリズム 170 |
演習問題 172 |
9 辺分離とその応用 173 |
9.1 準備 173 |
9.2 重み付き無向グラフにおける辺分離 176 |
9.3 多重グラフにおける辺分離 183 |
9.4 その他の辺分離 190 |
9.5 辺分離の応用 195 |
演習問題 200 |
10 デタッチメント 201 |
10.1 デタッチメントの存在条件 201 |
10.2 自己ループをもたない連結デタッチメント 207 |
10.3 化学構造グラフの推定問題 214 |
演習問題 224 |
11 辺連結度増加問題 225 |
11.1 辺連結度を1増加するアルゴリズム 225 |
11.2 辺連結度を目標値に増加するアルゴリズム 229 |
演習問題 236 |
12 供給点配置問題 238 |
12.1 無向グラフにおける辺連結度要求 239 |
12.2 木ハイパーグラフとその性質 244 |
12.3 有向グラフにおける辺連結度要求 250 |
12.4 点連結度要求をもつ供給点配置問題 257 |
12.5 有向グラフにおける単一被覆供給点配置問題 266 |
演習問題 269 |
演習問題:ヒントと略解 271 |
文献 296 |
記号リスト 301 |
索引 305 |