はじめに  
目次

第1章 グラフ表現のデータ構造  
1.1 グラフの基礎概念
1.2 有向グラフの完備データ構造
1.3 有向グラフの完備データ構造構成のプログラム
1.4 無向グラフの標準的データ構造
1.5 無向グラフの標準的データ構造構成のプログラム
1.6 行列によるグラフ表現
1.7 演習問題  

第2章 グラフ探索のアルゴリズム  
2.1 グラフ探索
2.2 深さ優先探索と幅優先探索
2.3 有向グラフの深さ優先探索
2.4 有向グラフの幅優先探索
2.5 無向グラフの深さ優先探索と幅優先探索
2.6 無向グラフの深さ優先探索と幅優先探索のプログラム
2.7 深さ優先探索と幅優先探索の応用例
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 演習問題  

第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.3 最大フロー問題の線形計画問題としての定式化
14.4 最小費用フロー問題の線形計画問題としての定式化
14.5 演習問題  

演習問題解答  
参考文献  
索引