グラフ理論

数学学部無料 7 章有料 0 章

有限グラフの構造を、道と閉路、マッチング、連結度とフロー、平面性、彩色、極値問題と Ramsey 理論の順に扱う。

想定読者: 大学生（理系）、離散数学・アルゴリズム・組合せ最適化に進む人

前提テーマ:組合せ論

このテーマの 100 本ノック（50 問）

目次

1. 第 1 章道・閉路・木：Euler 回路と Hamilton 閉路無料有限グラフの基本語彙を整え、握手補題、二部グラフと奇閉路、木の 6 つの特徴づけ、Euler の定理、Dirac・Ore・Bondy–Chvátal の Hamilton 閉路の十分条件、Havel–Hakimi の定理を、最長の道を取る論法を軸に証明する。
2. 第 2 章マッチング：Hall の結婚定理・König の定理・Tutte の定理無料増加道による Berge の定理から出発し、二部グラフの Hall の結婚定理と König–Egerváry の定理、Gallai の恒等式、Birkhoff–von Neumann の定理、一般のグラフの Tutte の 1-因子定理と Tutte–Berge の公式、安定マッチングの Gale–Shapley の定理を証明する。
3. 第 3 章連結度とネットワークフロー：Menger の定理・最大フロー最小カット定理無料頂点連結度と辺連結度、Whitney の不等式、2-連結グラフの耳分解とブロック木を扱い、最大フロー最小カット定理を Ford–Fulkerson の増加道で証明する。そこから Menger の定理、扇の補題、Chvátal–Erdős の定理、Hall・König の定理を導く。
4. 第 4 章平面グラフ：Euler の公式・双対・五色定理無料辺を折れ線で描いた平面グラフについて、位相の入力を Jordan の曲線定理 1 つにまとめ、Euler の公式 n − m + f = 2、辺数の上界と K_5・K_{3,3} の非平面性、面の境界と双対グラフ、正多面体の分類、Kempe 鎖による五色定理を証明する。
5. 第 5 章Kuratowski の定理：マイナーと平面性の判定無料グラフが平面的であることと K_5・K_{3,3} の細分を含まないことの同値性を、3-連結グラフの縮約できる辺と凸な描画の構成（Thomassen の方法）で証明し、Wagner の定理、Fáry の定理、Whitney の一意性定理、外平面的グラフの特徴づけを導く。
6. 第 6 章彩色：Brooks の定理・Vizing の定理・彩色多項式無料Brooks・Mycielski・König・Vizing の定理、彩色多項式と Whitney の展開、平面的グラフの 5-リスト彩色可能性（Thomassen）、弦グラフと弱パーフェクトグラフ定理（Lovász）を、証明を省かずに示す。
7. 第 7 章極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法無料禁止された部分グラフをもたないグラフの辺数の最大値（Mantel・Turán・Kővári–Sós–Turán）、彩色に必ず現れる単色の構造（Ramsey・Schur）、数え上げによる存在証明（Erdős の下界、内周も彩色数も大きいグラフ）を証明する。