離散数学

グラフ理論 ― 連結性・木・マッチング・フロー・平面性・彩色

概要

目次

1. 第1章 連結性

   グラフの同型・部分グラフ・補グラフから始め、最短路による距離・直径・中心、切断点・橋・ブロックという「壊れやすい接続」の分解を扱い、最後に互いに内部頂点を共有しない道の最大本数と最小の頂点切断が等しいというMengerの定理を述べる章である。Mengerの定理の証明は最大流最小切断定理（第4章）に帰着させる経路を示す。グラフの形を頂点名に依らない構造として捉える視点がこの章の出発点になる。

   $$\newcommand{abs}[1]{\left\lvert #1 \right\rvert} \newcommand{cG}[0]{\mathcal{G}} \newcommand{diam}[0]{\operatorname{Diam}} \newcommand{la}[0]{\leftarrow} \newcommand{lt}[0]{\left} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{mR}[0]{\mathbb{R}} \newcommand{p}[0]{\prime} \newcommand{ra}[0]{\rightarrow} \newcommand{rad}[0]{\operatorname{rad}} \newcommand{rt}[0]{\right} $$
   1. 1-0 章の見取り図
   2. 1-1 同型・部分グラフ・補グラフ
   3. 1-2 距離・直径・中心
   4. 1-3 切断点・橋・ブロック
   5. 1-4 Mengerの定理

2. 第2章 木

   閉路のない連結グラフである木を、根付き木と探索木、全域木と切断・閉路の性質、最小全域木の順に扱う章である。辺を一本足し一本引く交換の法則から、切断を渡る最小重みの辺を含む最小全域木が存在することを示し、Kruskal算法とPrim算法の正しさの根拠を与える。木が再帰構造をもつこと（根を選ぶと部分木が再び木になる）がこの章を通じて使われる。

   $$\newcommand{abs}[1]{\left\lvert #1 \right\rvert} \newcommand{cG}[0]{\mathcal{G}} \newcommand{diam}[0]{\operatorname{Diam}} \newcommand{la}[0]{\leftarrow} \newcommand{lt}[0]{\left} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{mR}[0]{\mathbb{R}} \newcommand{p}[0]{\prime} \newcommand{ra}[0]{\rightarrow} \newcommand{rad}[0]{\operatorname{rad}} \newcommand{rt}[0]{\right} $$
   1. 2-0 章の見取り図
   2. 2-1 根付き木と探索木
   3. 2-2 全域木と切断・閉路の性質
   4. 2-3 最小全域木

3. 第3章 マッチング

   二部グラフで「全員に異なる相手を割り当てる」問題を、増加路による割当の組み替え、Hallの結婚定理、Kőnigの定理の順に扱う章である。マッチングの最大化を交互道で改善できるかという局所的な操作が、最大マッチングと最小点被覆の一致という大域的な定理を生む。割当の最大数と障害を覆う最小数が一致するという形は、第4章のフローでも現れる。

   $$\newcommand{abs}[1]{\left\lvert #1 \right\rvert} \newcommand{cG}[0]{\mathcal{G}} \newcommand{diam}[0]{\operatorname{Diam}} \newcommand{la}[0]{\leftarrow} \newcommand{lt}[0]{\left} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{mR}[0]{\mathbb{R}} \newcommand{p}[0]{\prime} \newcommand{ra}[0]{\rightarrow} \newcommand{rad}[0]{\operatorname{rad}} \newcommand{rt}[0]{\right} $$
   1. 3-0 章の見取り図
   2. 3-1 二部グラフとマッチング
   3. 3-2 増加路
   4. 3-3 HallとKőnig

4. 第4章 フロー

   ネットワークの各辺に容量を与えたとき、始点から終点へ送れる最大の量を求める章である。残余ネットワークによる増加路の組み替えを導入し、最大流最小切断定理（整数容量）を証明する。流量の上界を与える切断が、最大流のときちょうど等しくなることが定理の内容であり、第1章のMengerの定理と第3章のKőnigの定理はいずれもこの定理の特殊な場合として再解釈できる。

   $$\newcommand{abs}[1]{\left\lvert #1 \right\rvert} \newcommand{cG}[0]{\mathcal{G}} \newcommand{diam}[0]{\operatorname{Diam}} \newcommand{la}[0]{\leftarrow} \newcommand{lt}[0]{\left} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{mR}[0]{\mathbb{R}} \newcommand{p}[0]{\prime} \newcommand{ra}[0]{\rightarrow} \newcommand{rad}[0]{\operatorname{rad}} \newcommand{rt}[0]{\right} $$
   1. 4-0 章の見取り図
   2. 4-1 ネットワーク流
   3. 4-2 最大流最小切断定理

5. 第5章 平面性

   グラフを平面に交わりなく描けるかという問いを、Euler公式、辺数の評価、平面双対、Kuratowskiの定理の順に扱う章である。頂点・辺・面の数の関係から $K_5$ と $K_{3,3}$ が平面的でないことを示し、面を頂点に変える双対で閉路と切断が入れ替わることを見る。後半では平面性判定の構造を分析し、Kuratowskiの定理の証明に進む。

   $$\newcommand{abs}[1]{\left\lvert #1 \right\rvert} \newcommand{cG}[0]{\mathcal{G}} \newcommand{diam}[0]{\operatorname{Diam}} \newcommand{la}[0]{\leftarrow} \newcommand{lt}[0]{\left} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{mR}[0]{\mathbb{R}} \newcommand{p}[0]{\prime} \newcommand{ra}[0]{\rightarrow} \newcommand{rad}[0]{\operatorname{rad}} \newcommand{rt}[0]{\right} $$
   1. 5-0 章の見取り図
   2. 5-1 平面グラフ
   3. 5-2 Euler公式の限界とKuratowskiの定理
   4. 5-3 平面双対
   5. 5-4 平面性判定の構造
   6. 5-5 Euler公式と非平面性の判定

6. 第6章 彩色

   隣接する頂点に異なる色を割り当てる頂点彩色を扱う章である。彩色数の定義と基本的な評価、貪欲彩色と退化度による上界、そして平面グラフが5色で塗れるという五色定理（Kempe鎖による証明）を順に示す。衝突する対象に異なる割当をするというモデル化の例を通して、グラフの構造（退化度、平面性）が色数の上界に直接結びつくことを見る。

   $$\newcommand{abs}[1]{\left\lvert #1 \right\rvert} \newcommand{cG}[0]{\mathcal{G}} \newcommand{diam}[0]{\operatorname{Diam}} \newcommand{la}[0]{\leftarrow} \newcommand{lt}[0]{\left} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{mR}[0]{\mathbb{R}} \newcommand{p}[0]{\prime} \newcommand{ra}[0]{\rightarrow} \newcommand{rad}[0]{\operatorname{rad}} \newcommand{rt}[0]{\right} $$
   1. 6-0 章の見取り図
   2. 6-1 グラフ彩色
   3. 6-2 貪欲彩色と退化度
   4. 6-3 平面グラフの五色定理

7. 第7章 Euler・Hamilton性

   すべての辺を一度ずつ通る閉路（Euler閉路）と、すべての頂点を一度ずつ訪れる閉路（Hamilton閉路）を、名前の似た別の問題として区別する章である。Euler閉路は次数の偶奇で完全に特徴づけられ、de Bruijn列の構成に応用される。Hamilton閉路は同様の簡明な必要十分条件がなく、十分条件（次数条件）と、存在しないことを示す方法を調べる。

   $$\newcommand{abs}[1]{\left\lvert #1 \right\rvert} \newcommand{cG}[0]{\mathcal{G}} \newcommand{diam}[0]{\operatorname{Diam}} \newcommand{la}[0]{\leftarrow} \newcommand{lt}[0]{\left} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{mR}[0]{\mathbb{R}} \newcommand{p}[0]{\prime} \newcommand{ra}[0]{\rightarrow} \newcommand{rad}[0]{\operatorname{rad}} \newcommand{rt}[0]{\right} $$
   1. 7-0 章の見取り図
   2. 7-1 Eulerグラフとde Bruijn列
   3. 7-2 Hamiltonグラフ

8. 第8章 極値グラフ

   禁止した部分グラフを含まないグラフの辺数の最大値を求める極値問題への入口の章である。三角形を含まないグラフの辺数が $\lfloor n^2/4\rfloor$ 以下であるというMantelの定理を証明し、完全二部グラフで等号が達成されることを見る。これはTuránの定理など一般の極値グラフ理論につながる最初の結果である。

   $$\newcommand{abs}[1]{\left\lvert #1 \right\rvert} \newcommand{cG}[0]{\mathcal{G}} \newcommand{diam}[0]{\operatorname{Diam}} \newcommand{la}[0]{\leftarrow} \newcommand{lt}[0]{\left} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{mR}[0]{\mathbb{R}} \newcommand{p}[0]{\prime} \newcommand{ra}[0]{\rightarrow} \newcommand{rad}[0]{\operatorname{rad}} \newcommand{rt}[0]{\right} $$
   1. 8-0 章の見取り図
   2. 8-1 Mantelの定理

9. 第9章 アルゴリズム

   グラフを系統的に調べる手続きである幅優先探索（BFS）と深さ優先探索（DFS）を扱う章である。BFSが最短距離を与えること、DFSが切断点・橋・閉路の構造を明らかにすることを、探索木を通して示す。この章は、距離や連結成分といった第1章・第2章の概念を、算法として実際に計算する視点から見直す。

   $$\newcommand{abs}[1]{\left\lvert #1 \right\rvert} \newcommand{cG}[0]{\mathcal{G}} \newcommand{diam}[0]{\operatorname{Diam}} \newcommand{la}[0]{\leftarrow} \newcommand{lt}[0]{\left} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{mR}[0]{\mathbb{R}} \newcommand{p}[0]{\prime} \newcommand{ra}[0]{\rightarrow} \newcommand{rad}[0]{\operatorname{rad}} \newcommand{rt}[0]{\right} $$
   1. 9-0 章の見取り図
   2. 9-1 幅優先探索と深さ優先探索

Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する