グラフ理論のサイトと書籍のご紹介
はじめに
[更新: 2013/4/22]いくつか更新しました。 [/更新]
§1では、グラフ理論のWWW上の資料で「これは良かった。役に立った。」と思えるものをご紹介します。
どちらかというと、グラフアルゴリズムより数学としてのグラフ理論を意識した資料を選びました。
§2では、グラフアルゴリズム等を含むより専門的な書籍をご紹介します。
1. グラフ理論のサイト
Reinhard Diestel, Graph Theory Electronic Edition
http://diestel-graph-theory.com/basic.html
ディーステル先生のグラフ理論のテキストのpdf版です。基礎から応用まで丁寧に書いてあります。
応用についてはほとんど書かれておりませんが、その分数学的な色彩が強い本です。
- 目次
- 1. The Basics: グラフの基礎です。次数やパス等の基本的な定義について。
- 2. Matching: Covering and Packing: マッチングや頂点被覆、パッキング等。グラフアルゴリズム的にも重要な概念について。
- 3. Connectivity: グラフのある種の「強度」である点連結度と辺連結度の性質について。
- 4. Planer Graphs: 平面に辺が交差することなく描画できるグラフについて。
- 5. Colouring: 頂点彩色や辺彩色について。
- 6. Flows: フローについて。
- 7. Extremal Graph Theory: 極値グラフ理論について。
- 8. Infinite Graphs: 無現グラフについて。
- 9. Ramsey Theory for Graphs: グラフのラムゼー定理について。
- 10. Hamilton Cycles: ハミルトン閉路について。
- 11. Random Graphs: ランダムグラフについて。
- 12. Minors, Trees and WQO: グラフマイナー理論について。
Graph Theory (Graduate Texts in Mathematics)
- 作者: Reinhard Diestel
- 出版社/メーカー: Springer
- 発売日: 2010/07/19
- メディア: ペーパーバック
- この商品を含むブログを見る
Satoru Iwata, http://www.kurims.kyoto-u.ac.jp/~iwata/
岩田覚先生のサイトの Lecture Notes が勉強になります。
マトロイドと劣モジュラ関数についてグラフ理論と関連付けて理解を深めることができます。
- 目次
- Lecture 1: 辺彩色, 特に 2 部グラフの辺彩色についての解説。 (辺彩色: グラフの各辺に色をつけること)
- Lecture 2: 辺彩色2, 2 部グラフより一般的なグラフの辺彩色についての解説。
- Lecture 3: 安定マッチング, 安定マッチングと、そのリスト彩色の関係についての解説。
- Lecture 4: マトロイド, マトロイド: 線形代数における線形独立の抽象化
- Lecture 6: 同時交換性
- Lecture 7: マトロイドの共通独立集合族
- Lecture 8: Nash-Williams の定理
- Lecture 10: 劣モジュラ関数
- Lecture 11: 劣モジュラ関数2
- Lecture 12: 劣モジュラ関数3
システム情報数理学IIb (ファイル形式: pdf),
http://www.math.is.tohoku.ac.jp/~obata/lecture/2007-graduate/2007-in-Abs-1-12.pdf
尾畑伸明先生のサイトにある、グラフのスペクトル分解の資料です。
読みこなすのに、線形代数の知識が必要になります。
2. より専門的な資料
グラフアルゴリズム
グラフアルゴリズムに興味を持たれているみなさんは、
以下のアルゴリズムの本の該当箇所をご参照ください。
近年、和書含め良書が増えていると思いますため、
見つけ次第こちらでご紹介いたします。
Introduction to Algorithms (MIT Press)
- 作者: Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein
- 出版社/メーカー: The MIT Press
- 発売日: 2009/07/31
- メディア: ペーパーバック
- 購入: 5人 クリック: 90回
- この商品を含むブログ (19件) を見る
連結度
連結度に興味を持たれた方は、こちらをご参照ください。
- 作者: 茨木俊秀,石井利昌,永持仁
- 出版社/メーカー: 朝倉書店
- 発売日: 2010/04/01
- メディア: 単行本
- 購入: 1人 クリック: 90回
- この商品を含むブログ (1件) を見る
Algorithmic Aspects of Graph Connectivity (Encyclopedia of Mathematics and its Applications)
- 作者: Hiroshi Nagamochi,Toshihide Ibaraki
- 出版社/メーカー: Cambridge University Press
- 発売日: 2008/09/08
- メディア: ハードカバー
- クリック: 1回
- この商品を含むブログを見る
フロー、カット、連結度の主にアルゴリズム的な側面から書かれた書籍です。
- 目次
- 1. Introduction: フロー、カット、連結度に関する基本的な定義について。
- 2. Maximum Adjacency Ordering and Forest Decompositions: 最小カット算出の基礎となるグラフの順序付けのひとつである最大隣接順序と、森分解について。
- 3. Minimum Cuts: 最小カットについて。
- 4. Cut Enumerations: カットの列挙について。
- 5. Cactus Representations: 最小カットのカクタス表現について。
- 6. Extreme Vertex Sets: 極値集合族とよばれるカットの値にかんする頂点集合のラミナ族について。
- 7. Edge Splitting: 辺分離操作について。
- 8. Connectivity Augmentation: 連結度増大問題について。
- 9. Source Location Problems: 供給点配置問題について。
- 10. Submodular and Posimodular Set Functions: カット関数の一般化である劣モジュラ、かつ、正モジュラ関数について。
石井先生の以下の資料を準備として読むとより分かりやすいです。
§1〜§5について
石井利昌, 連結度と関連問題, http://barrel.ih.otaru-uc.ac.jp/handle/10252/4290
§6〜§9について
石井利昌, 連結度要求を持つネットワーク構成問題, http://barrel.ih.otaru-uc.ac.jp/handle/10252/4292
- 作者: Andras Frank
- 出版社/メーカー: Oxford Univ Pr
- 発売日: 2011/06/01
- メディア: ハードカバー
- この商品を含むブログを見る
- 目次
- 1. Elements of graphs and hypergraphs: グラフとハイパーグラフの諸定義について。
- 2. Connectivity, paths, and matchings: 連結度、パス、およびマッチングについて。
- 3. Elements of network optimization: ネットワーク最適化の基礎について。
- 4. Elements of polyhedral combinatorics: 多面体的組合せ論の基礎について。
- 5. Elements of matroid theory: マトロイド理論の基礎について。
- 6. Efficient algorithms for flows and cuts: フローとカットに対する効率的なアルゴリズムについて。
- 7. Structure and representations of cuts: カットの構造と表現について。
- 8. The splitting off operation and constructive characterizations: 辺分離操作と構成的特徴づけについて。
- 9. Orientations of graphs and hypergraphs: グラフとハイパーグラフの向き付けについて。
- 10. Trees and arborescences: packing and coveing
- 11. Preserving and improving connections:
- 12. Setting the stage: aspects and approaches:
- 13. Matroid optimization:
- 14. Generalized polymatroids:
- 15. Relaxing semimodularity:
- 16. Submodular flows: 劣モジュラフローについて。
- 17. Covering supermodular functions by digraphs: 有向グラフによる優モジュラ関数の被覆について。
平面グラフ
平面グラフの性質、アルゴリズムについて興味を持たれた方は、こちらをご参照ください。
Planar Graphs: Theory and Algorithms (Dover Books on Mathematics)
- 作者: T. Nishizeki,N. Chiba,Mathematics
- 出版社/メーカー: Dover Publications
- 発売日: 2008/06/11
- メディア: ペーパーバック
- この商品を含むブログを見る
- 目次
- 1. Graph Theoretic Foundations: グラフの諸定義について。
- 2. Algorithmic Foundations: アルゴリズムの基礎について。
- 3. Planarity Testing and Embedding: 平面性判定と埋め込みについて。
- 4. Drawing Planar Graphs: 描画について。
- 5. Vertex Coloring: 頂点彩色について。
- 6. Edge Coloring: 辺彩色について。
- 7. Independent Vertex Sets: 独立集合について。
- 8. Listing Subgraphs:
- 9. Planar Separator Theorem:
- 10. Hamiltonian Cycles: ハミルトン閉路について。
- 11. Flows in Planar Graphs: 平面グラフにおけるフローについて。