有向グラフの教科書
Jørgen Bang-Jensen(http://www.imada.sdu.dk/~jbj/)と
Gregory Gutin(http://www.cs.rhul.ac.uk/~gutin/)の書いた有向グラフの教科書、
『Digraphs: Theory, Algorithms and Applications』の第一版が
Springer-Verlagの好意により、無料で読めるようです。
ファイル形式はpdfです。下記リンク先の「 the first edition of the book 」から読めます。
Digraphs: Theory, Algorithms and Applications, 2nd Edition, http://www.cs.rhul.ac.uk/books/dbook/
ざっと読んだんですが、
有向グラフのクラス、分解の方法を紹介していたり知らないことがたくさん載ってたんで勉強になりそうです。
以前紹介した(http://d.hatena.ne.jp/salmonsnare/20090313/1236942950)、
Reinhard Diestelの『Graph Theory』は無向グラフを中心に書かれているんで、
併せて読めばグラフ理論に関して広範な基礎知識を得ることができるように思います。
[追記] 目次を追記しました。 [/追記]
目次
- Basic Terminology, Notation and Results（基本用語、記法等）
- Distances（頂点間の距離を算出するアルゴリズム等)
- Flows in Networks（ネットワークフロー）
- Classes of Digraphs（有向グラフのクラス）
- Hamiltonicity and Related Problems（ハミルトン性と関連問題）
- Hamiltonian Refinements
- Global Connectivity（有向グラフの点連結度、辺連結度について）
- Orientations of Graphs（グラフの向き付け（無向グラフの辺に向きをつけて有向グラフにすること）について）
- Disjoint Paths and Trees（互いに素なパスと木）
- Cycle Structure of Digraphs（サイクル構造と有向グラフ）
- Generalizations of Digraphs（有向グラフの一般化）
- Additional Topics（追加トピック）
