内容紹介
この20年、グラフ理論は大きく変貌した。数学や情報科学の根幹を揺るがすような定理が次々と証明され、深遠な理論が生まれている。もはや、旧来のトピックに分けて、その進展を捉えることは不可能である。本書は、そのような近年の動向を踏まえて、先端的なグラフ理論の全体像を把握するために書かれた教科書である。どの章も、その分野で何が問題になっているのかがわかる導入になっており、その精神が丁寧に書かれている。また、形式的な証明を与える前に、その直感的なアイデアが示されており、理解を助けてくれる。 特に、最終章には、近年のグラフ理論の１つの指導原理となっているRobertsonとSeymonによるグラフ・マイナーの理論がまとめられている。膨大な論文を読むことなしに、その全貌を知ることができる。グラフ理論に興味のあるすべての人におすすめの一冊である。
目次
第１章 基本用語
１．１ グラフ
１．２ 頂点の次数
１．３ 道と閉路
１．４ 連結度
１．５ 木と林
１．６ 二部グラフ
１．７ 縮約とマイナー
１．８ オイラー周遊
１．９ 線形代数から
１．10 その他
第２章 マッチング
２．１ 二部グラフのマッチング
２．２ 一般のグラフにおけるマッチング
２．３ 道被覆
第３章 連結度
３．１ ２―連結グラフと部分グラフ
３．２ ３―連結グラフの構造
３．３ Mengerの定理
３．４ Maderの定理
３．５ 辺素な全域木
３．６ 与えられた頂点対を結ぶ道
第４章 平面的グラフ
４．１ 位相幾何学からの準備
４．２ 平面グラフ
４．３ 描画
４．４ 平面的グラフ：Kuratowskiの定理
４．５ 平面性の代数的判定基準
４．６ 平面双対性
第５章 彩色
５．１ 地図の色分けと平面グラフ
５．２ 頂点彩色
５．３ 辺の彩色
５．４ リスト彩色
５．５ 理想グラフ
第６章 流れ
６．１ 循環流
６．２ ネットワークの流れ
６．３ 群に値を持つ流れ
６．４ 小さいｋに対するｋ―流
６．５ 流れと彩色の双対性
６．６ Tutteの流れ予想
第７章 密なグラフの部分構造
７．１ 部分グラフ
７．２ Szemerediの一様化補題
７．３ 一様化補題の応用）
第８章 疎なグラフの部分構造
８．１ 位相的マイナー
８．２ マイナー
８．３ Hadwigers予想
第９章 ラムゼー理論
９．１ ラムゼーの定理
９．２ ラムゼー数
９．３ 誘導ラムゼー定理
９．４ ラムゼー的性質と連結度
第10章 ハミルトン閉路
10．１ 簡単な十分条件
10．２ ハミルトン閉路と次数列
10．３ グラフの平方におけるハミルトン閉路
第11章 ランダム・グラフ
11．１ ランダム・グラフの概念
11．２ 確率論的手法
11．３ ほとんどすべてのグラフに関する性質
11．４ 閾値関数と２次モーメント
第12章 樹状分解とマイナー
12．１ よい擬順序
12．２ 木に関するグラフ・マイナー定理
12．３ 樹状分解
12．４ 樹状幅と禁止マイナー
12．５ グラフ・マイナー定理
出版社からのメッセージ
本書は、2000年10月にシュプリンガー・ジャパン株式会社より出版された同名書籍を再出版したものです。
