内容

目次

第1章　グラフ 　　1.1　グラフとその表現 　　1.2　同型写像と自己同型写像 　　1.3　他の構造から発生するグラフ 　　1.4　他のグラフからグラフの構成 　　1.5　有向グラフ 　　1.6　無限グラフ 　　1.7　関連する読み物 第2章　部分グラフ 　　2.1　部分グラフと拡大グラフ 　　2.2　全域部分グラフと誘導部分グラフ 　　2.3　グラフの変形 　　2.4　分解と被覆 　　2.5　辺切断とボンド 　　2.6　偶部分グラフ 　　2.7　グラフの再構成 　　2.8　関連する読み物 第3章　連結グラフ 　　3.1　歩道と連結 　　3.2　切断辺 　　3.3　オイラー周遊 　　3.4　有向グラフの連結 　　3.5　閉路2重被覆 　　3.6　関連する読み物 第4章　木 　　4.1　林と木 　　4.2　全域木 　　4.3　基本閉路と基本ボンド 　　4.4　関連する読み物 第5章　分離不可能グラフ 　　5.1　切断点 　　5.2　分離とブロック 　　5.3　耳分解 　　5.4　有向耳分解 　　5.5　関連する読み物 第6章　探索木アルゴリズム 　　6.1　探索木 　　6.2　最小重み全域木 　　6.3　分枝探索 　　6.4　関連する読み物 第7章　ネットワークのフロー 　　7.1　輸送ネットワーク 　　7.2　最大フロー最小カット定理 　　7.3　弧素な有向道 　　7.4　関連する読み物 第8章　アルゴリズムの複雑性 　　8.1　計算複雑性 　　8.2　多項式時間帰着 　　8.3　NP-完全問題 　　8.4　近似アルゴリズム 　　8.5　貪欲ヒューリスティック 　　8.6　線形計画問題と整数計画問題 　　8.7　関連する読み物 第9章　連結度 　　9.1　頂点連結度 　　9.2　扇補題 　　9.3　辺連結度 　　9.4　3-連結グラフ 　　9.5　劣モジュラ性 　　9.6　Gomory–Hu木 　　9.7　弦グラフ 　　9.8　関連する読み物 第10章　平面的グラフ 　　10.1　平面グラフと平面的グラフ 　　10.2　双対性 　　10.3　Eulerの公式 　　10.4　橋 　　10.5　Kuratowskiの定理 　　10.6　グラフの曲面埋め込み 　　10.7　関連する読み物 第11章　四色定理 　　11.1　地図の彩色 　　11.2　五色定理 　　11.3　関連する読み物 第12章　独立集合とクリーク 　　12.1　独立集合 　　12.2　Turánの定理 　　12.3　Ramseyの定理 　　12.4　正則化補題 　　12.5　関連する読み物 第13章　確率的手法 　　13.1　ランダムグラフ 　　13.2　期待値 　　13.3　分散 　　13.4　ランダムグラフの発展 　　13.5　局所補題 　　13.6　関連する読み物 第14章　頂点彩色 　　14.1　染色数 　　14.2　臨界的グラフ 　　14.3　内周と染色数 　　14.4　理想グラフ 　　14.5　リスト彩色 　　14.6　隣接多項式 　　14.7　彩色多項式 　　14.8　関連する読み物 第15章　地図の彩色 　　15.1　曲面の染色数 　　15.2　四色定理 　　15.3　平面的グラフのリスト彩色 　　15.4　Hadwigerの予想 　　15.5　関連する読み物 第16章　マッチング 　　16.1　最大マッチング 　　16.2　2部グラフのマッチング 　　16.3　任意のグラフのマッチグ 　　16.4　完全マッチングと因子 　　16.5　マッチングアルゴリズム 　　16.6　関連する読み物 第17章　辺彩色 　　17.1　辺染色数 　　17.2　Vizingの定理 　　17.3　スナーク 　　17.4　完全マッチングによる被覆 　　17.5　リスト辺彩色 　　17.6　関連する読み物 第18章　ハミルトン閉路 　　18.1　ハミルトングラフと非ハミルトングラフ 　　18.2　平面的非ハミルトングラフ 　　18.3　道交換と閉路交換 　　18.4　道交換と偶奇性 　　18.5　ランダムグラフのハミルトン閉路 　　18.6　関連する読み物 第19章　有向グラフにおける被覆と詰め込み 　　19.1　ハイパーグラフの被覆と詰め込み 　　19.2　有向閉路による被覆 　　19.3　分枝の詰め込み 　　19.4　有向閉路と有向ボンドの詰め込み 　　19.5　関連する読み物 第20章　電気回路 　　20.1　循環と電圧 　　20.2　基底行列 　　20.3　実行可能な循環と電圧 　　20.4　行列木定理 　　20.5　抵抗電気回路 　　20.6　完全正方形分割 　　20.7　グラフ上のランダムウォーク 　　20.8　関連する読み物 第21章　整数フローと被覆 　　21.1　循環と彩色 　　21.2　整数フロー 　　21.3　Tutteのフロー予想 　　21.4　辺素な全域木 　　21.5　4-フロー定理と8-フロー定理 　　21.6　6-フロー定理 　　21.7　Tutte 多項式 　　21.8　関連する読み物 未解決問題 参考文献 用語集 索引