グラフ理論のサイトと書籍のご紹介

はじめに

[更新: 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)

Graph Theory (Graduate Texts in Mathematics)

日本語の書籍も『グラフ理論』([amazon], http://www.amazon.co.jp/dp/4431708766)) というタイトルで出ています。

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)

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件) を見る

連結度

連結度に興味を持たれた方は、こちらをご参照ください。

グラフ理論―連結構造とその応用 (基礎数理講座)

グラフ理論―連結構造とその応用 (基礎数理講座)


Algorithmic Aspects of Graph Connectivity (Encyclopedia of Mathematics and its Applications)

Algorithmic Aspects of Graph Connectivity (Encyclopedia of Mathematics and its Applications)

フロー、カット、連結度の主にアルゴリズム的な側面から書かれた書籍です。

  • 目次
    • 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


Connections in Combinatorial Optimization (Oxford Lecture Series in Mathematics and Its Applications)

Connections in Combinatorial Optimization (Oxford Lecture Series in Mathematics and Its Applications)

  • 目次
    • 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)

Planar Graphs: Theory and Algorithms (Dover Books on Mathematics)

  • 目次
    • 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: 平面グラフにおけるフローについて。