書記の読書記録#677『グラフ理論 (Springer‐Verlag GTMシリーズ)』

R. ディーステル（訳：根上 生也，太田克弘）『グラフ理論 (Springer‐Verlag GTMシリーズ)』のレビュー

グラフ理論 (Springer‐Verlag GTMシリーズ)

レビュー

根気さえあれば要求される前知識は少ないが，R.J. ウィルソン『グラフ理論入門』が基礎理論に終始していたのに対し，本書の第6章以降は応用に特化した印象。

もくじ

第１章　基本用語
　１．１　グラフ
　１．２　頂点の次数
　１．３　道と閉路
　１．４　連結度
　１．５　木と林
　１．６　二部グラフ
　１．７　縮約とマイナー
　１．８　オイラー周遊
　１．９　線形代数から
　１．10　その他
第２章　マッチング
　２．１　二部グラフのマッチング
　２．２　一般のグラフにおけるマッチング
　２．３　道被覆
第３章　連結度
　３．１　２―連結グラフと部分グラフ
　３．２　３―連結グラフの構造
　３．３　Mengerの定理
　３．４　Maderの定理
　３．５　辺素な全域木
　３．６　与えられた頂点対を結ぶ道
第４章　平面的グラフ
　４．１　位相幾何学からの準備
　４．２　平面グラフ
　４．３　描画
　４．４　平面的グラフ：Kuratowskiの定理
　４．５　平面性の代数的判定基準
　４．６　平面双対性
第５章　彩色 　　　
　５．１　地図の色分けと平面グラフ
　５．２　頂点彩色
　５．３　辺の彩色
　５．４　リスト彩色
　５．５　理想グラフ
第６章　流れ
　６．１　循環流
　６．２　ネットワークの流れ
　６．３　群に値を持つ流れ
　６．４　小さいｋに対するｋ―流
　６．５　流れと彩色の双対性
　６．６　Tutteの流れ予想
第７章　密なグラフの部分構造
　７．１　部分グラフ
　７．２　Szemerediの一様化補題
　７．３　一様化補題の応用）
第８章　疎なグラフの部分構造
　８．１　位相的マイナー
　８．２　マイナー
　８．３　Hadwigers予想
第９章　ラムゼー理論
　９．１　ラムゼーの定理
　９．２　ラムゼー数
　９．３　誘導ラムゼー定理
　９．４　ラムゼー的性質と連結度
第10章　ハミルトン閉路
　10．１　簡単な十分条件
　10．２　ハミルトン閉路と次数列
　10．３　グラフの平方におけるハミルトン閉路
第11章　ランダム・グラフ
　11．１　ランダム・グラフの概念
　11．２　確率論的手法
　11．３　ほとんどすべてのグラフに関する性質
　11．４　閾値関数と２次モーメント
第12章　樹状分解とマイナー
　12．１　よい擬順序
　12．２　木に関するグラフ・マイナー定理
　12．３　樹状分解
　12．４　樹状幅と禁止マイナー
　12．５　グラフ・マイナー定理

本記事のもくじはこちら：

書記の読書記録まとめ｜Writer_Rinka｜note