| 第1章 グラフ 1 |
| 1-1 グラフとその表現 1 |
| (1) グラフ 1 |
| (2) 基本的な定義 6 |
| (3) グラフの行列表現 14 |
| (4) 次数と辺数 17 |
| 1-2 木と森 18 |
| (1) 木 18 |
| (2) 全域木 23 |
| (3) 根付き木と2分木 25 |
| 1-3 2部グラフとグラフの彩色 28 |
| (1) 2部グラフ 28 |
| (2) グラフの彩色 31 |
| 1-4 オイラーグラフとハミルトングラフ 32 |
| (1) オイラーグラフ 32 |
| (2) 完全グラフと完全2部グラフ 35 |
| (3) ハミルトングラフと巡回セールスマン問題 37 |
| 演習問題1 41 |
| 第2章 アルゴリズムの解析 44 |
| 2-1 関数の漸近的評価 44 |
| 2-2 アルゴリズムの解析 49 |
| (1) 問題 49 |
| (2) アルゴリズムの解析 54 |
| (3) 多項式時間アルゴリズム 56 |
| (4) グラフの大きさ 58 |
| (5) オイラーグラフ判定問題 61 |
| 2-3 整列アルゴリズム 64 |
| (1) 整列問題 64 |
| (2) 併合問題 67 |
| (3) 併合整列アルゴリズム 69 |
| 演習問題2 73 |
| 第3章 グラフのアルゴリズム 75 |
| 3-1 探索アルゴリズム 75 |
| (1) 深さ優先探索アルゴリズム 75 |
| (2) 幅優先探索アルゴリズム 85 |
| 3-2 最短路アルゴリズム 92 |
| (1) 最短路アルゴリズム 92 |
| (2) 最長路問題 97 |
| 3-3 最大全域木アルゴリズム 99 |
| (1) 最大全域木アルゴリズム 99 |
| (2) 合併発見手法 103 |
| (3) 最小全域木アルゴリズム 105 |
| 演習問題3 107 |
| 第4章 アルゴリズムの設計 108 |
| 4-1 アルゴリズムの設計技法 108 |
| (1) 様々なアルゴリズム 108 |
| (2) 設計技法 110 |
| 4-2 貪欲アルゴリズム 114 |
| (1) 独立系とマトロイド 114 |
| (2) マトロイドと貪欲アルゴリズム 122 |
| 4-3 問題の難しさ 129 |
| (1) NPとP 129 |
| (2) 多項式時間還元 134 |
| (3) NP完全 136 |
| (4) 充足可能性判定問題 137 |
| (5) NP完全問題 141 |
| 4-4 近似アルゴリズム 147 |
| (1) NP困難 147 |
| (2) 近似アルゴリズム 148 |
| (3) 三角巡回セールスマン問題 149 |
| (4) 独立系と貪欲アルゴリズム 152 |
| (5) 最大巡回セールスマン問題 155 |
| 演習問題4 158 |
| 演習問題解答 160 |
| 付録 174 |
| 1 集合 174 |
| 2 写像と関係 175 |
| 3 論理関数 176 |
| 4 その他 177 |
| 参考文献 178 |
| 索引 179 |
