グラフ理論 -連結構造とその応用- 茨木俊秀、永持仁、石井利昌　著 朝倉書店、2010年4月

1. グラフとネットワーク　
   　　基礎概念と用語、グラフの連結性、アルゴリズムと計算量、 グラフの探索、
   　　オイラーの一筆書き、最小木問題、最短路問題　
   　　演習問題
2. ネットワークフロー　
   　　フローの定義と性質、最大フロー問題、最大マッチング問題、 最大フローのアルゴリズム、
   　　層ネットワークによる最大フローアルゴリズム、 前フローを用いた最大フローアルゴリズム
   　　演習問題
3. 最小カットと連結度　
   　　メンガーの定理、最小カットと連結度の計算、 辺連結度と点連結度の統合
   　　演習問題
4. グラフのカット構造　
   　　ゴモリ・フー木、極点集合、カクタス表現
   　　演習問題
5. 最大隣接順序と森分解　
   　　連結度を保存する全域部分グラフ、最大隣接順序、 最大隣接順序による森分解、
   　　疎構造化、疎構造化による連結度アルゴリズムの改良
   　　演習問題
6. 無向グラフの最小カット　
   　　ペンダント対、最大隣接順序による最小カットアルゴリズム、
   　　最小カットの諸アルゴリズムと実用上の工夫、 ペンダント対間の最大フロー
   　　演習問題
7. 最小カットのカクタス表現　
   　　カクタス表現の標準形、カクタス表現の結合、 (s,t)-カクタス表現を構成するアルゴリズム、
   　　全最小カットのカクタス表現を構成するアルゴリズム　
   　　演習問題
8. 極点集合とその応用　
   　　フラット対と最小次数順序、極点集合の計算、最小k-部分分割問題、
   　　最小k-カット問題に対する近似アルゴリズム
   　　演習問題
9. 辺分離とその応用　
   　　準備、重み付き無向グラフにおける辺分離、多重グラフにおける辺分離、 その他の辺分離、
   　　辺分離の応用
   　　演習問題
10. デタッチメント　
    　　デタッチメントの存在条件、自己ループを持たない連結デタッチメント、
    　　化学構造グラフの推定問題
    　　演習問題
11. 辺連結度増加問題　
    　　辺連結度を1増加するアルゴリズム、辺連結度を目標値に増加するアルゴリズム
    　　演習問題
12. 供給点配置問題　
    　　無向グラフにおける辺連結度要求、木ハイパーグラフとその性質、
    　　有向グラフにおける辺連結度要求、点連結度要求をもつ供給点配置問題、
    　　有向グラフにおける単一被覆供給点配置問題
    　　演習問題
    
    演習問題：ヒントと略解　
    文献　
    記号リスト　
    索引　
    

茨木研究室ホームページへ