| 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 |
