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

第1章 連結性

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

第2章 木

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

第3章 マッチング

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

第4章 フロー

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

第5章 平面性

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

第6章 彩色

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

第7章 Euler・Hamilton性

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

第8章 極値グラフ

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

第9章 アルゴリズム

## この章の問い
連結を保つ最小限の辺は何か。辺に重みがあるとき、最も軽い全域木はどう作るか。
## 道筋
- **根付き木と探索木**：根を選ぶと木が再帰になる。
- **全域木と切断・閉路の性質**：一本を足し一本を引く交換の法則。
- **最小全域木**：局所的に軽い辺を選んで大域的最適解を作る。
## 読み方
交換の法則を2〜3個のグラフで手を動かして確かめてから、最小全域木の証明を読む。
## 章末で言えること
連結な $n$ 頂点グラフの全域木は $n-1$ 辺をもち、切断を渡る最小重みの辺を含む最小全域木が存在する。
## 前の章から持ち込むもの
連結性、閉路、橋。


2-0 章の見取り図

## この章の問い
グラフの「つながり方」をどう測るか。どこを切ればつながりが失われるか、その最小の切り方は、つながっている道の本数と何が対応するか。
## 道筋
- **同型・部分グラフ・補グラフ**：頂点名を忘れて構造を見る。同型の保存量、自己補グラフ、隣接行列。
- **距離・直径・中心**：最短路でグラフの大きさを測る。
- **切断点・橋・ブロック**：一本で壊れる接続とその分解。
- **Mengerの定理**：道の最大本数と頂点切断の最小数の一致。証明は第4章の最大流最小切断定理を使う。
## 読み方
最初の3頁は順に必須。Mengerの定理の証明は第4章を読んだあとで戻るとよい。
## 章末で言えること
非隣接な2頂点の間の内部頂点素な道の最大本数は、それらを分離する頂点切断の最小サイズに等しい。
## 前の章から持ち込むもの
集合と写像、数学的帰納法。


1-0 章の見取り図

## この章の問い
隣り合う頂点が同じ色にならないように塗るには最低何色必要か。グラフの構造は色数をどこまで抑えるか。
## 道筋
- **グラフ彩色**：彩色数の定義、二部グラフ、奇閉路、完全グラフ。
- **貪欲彩色と退化度**：良い順序を作れば色数が下がる。
- **平面グラフの五色定理**：Kempe鎖で塞がれた色を空ける。
## 読み方
貪欲彩色の順序依存性を小さな例で確認する。五色定理は第5章の辺数評価（次数5以下の頂点の存在）を使う。
## 章末で言えること
退化度 $d$ のグラフは $d+1$ 色で塗れ、平面グラフは5色で塗れる。
## 前の章から持ち込むもの
平面グラフの辺数評価（第5章）、二部グラフ（第3章）。


6-0 章の見取り図

## この章の問い
ある部分グラフを禁じたとき、辺はいくつまで持てるか。
## 道筋
- **Mantelの定理**：三角形を含まないグラフの辺数の上界と、それを達成するグラフ。
## 読み方
1頁だけなので、$n=4,5,6$ で完全二部グラフの辺数を数えてから証明を読む。
## 章末で言えること
頂点数 $n$ の三角形なしグラフの辺数は高々 $\lfloor n^2/4\rfloor$ で、完全二部グラフ $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ が等号を達成する。
## 前の章から持ち込むもの
次数、二部グラフ。


8-0 章の見取り図

## この章の問い
二つの集合の間に割当を作るとき、全員に相手を割り当てられる条件は何か。できないときの障害は何か。
## 道筋
- **二部グラフとマッチング**：割当をグラフの辺の集合として表す。
- **増加路**：交互道で割当を組み替えて増やす。
- **HallとKőnig**：完全マッチングの存在条件と、最大マッチング＝最小点被覆。
## 読み方
増加路の一般論を先に読み、その特別な場合としてHallの定理を読む。小さい二部グラフで自分で増加路を探してみる。
## 章末で言えること
二部グラフの最大マッチングの大きさは最小点被覆の大きさに等しく、左側を飽和するマッチングが存在するための必要十分条件はHallの条件である。
## 前の章から持ち込むもの
木と二部グラフ、閉路の偶奇。


3-0 章の見取り図

## この章の問い
グラフが大きくなっても、距離や連結成分を機械的に求めるにはどうすればよいか。
## 道筋
- **幅優先探索と深さ優先探索**：探索木が距離と分離構造を明かす。
## 読み方
小さなグラフで手でBFSとDFSを実行し、探索木を描いて比較する。
## 章末で言えること
BFSは始点からの最短距離を与え、DFSの探索木は切断点と橋を見つけるのに使える。
## 前の章から持ち込むもの
距離、連結性、木。


9-0 章の見取り図

## この章の問い
すべての辺を通る道と、すべての頂点を通る道は、なぜまったく違う難しさをもつのか。
## 道筋
- **Eulerグラフとde Bruijn列**：次数の偶奇による特徴づけと、すべての語を並べる列。
- **Hamiltonグラフ**：十分条件と、存在しないことの証明。
## 読み方
2頁は独立して読める。Euler閉路の頁は、de Bruijn列を自分で小さい場合に作ってみると理解が進む。
## 章末で言えること
連結グラフがEuler閉路をもつための必要十分条件はすべての次数が偶数であること。Hamilton閉路については簡明な必要十分条件は知られていない。
## 前の章から持ち込むもの
連結性、次数、閉路。


7-0 章の見取り図

## この章の問い
どれだけの量をネットワークに流せるか。その上限を決めているのはネットワークのどの部分か。
## 道筋
- **ネットワーク流**：容量、流れの保存、残余ネットワーク。
- **最大流最小切断定理**：増加路算法の停止と最小切断との一致。
## 読み方
容量付きの小さなネットワークを自分で用意して、増加路を一本ずつ流しながら残余ネットワークを描くと、定理の証明の意味がはっきりする。
## 章末で言えること
整数容量のネットワークの最大流量は最小切断容量に等しく、最大流は整数値をとるものが存在する。
## 前の章から持ち込むもの
増加路（第3章）、切断（第1章）。


4-0 章の見取り図

## この章の問い
グラフを平面に交わりなく描けるのはいつか。描けないときの障害は何か。
## 道筋
- **平面グラフ**：頂点・辺・面を結ぶEuler公式。
- **Euler公式の限界とKuratowskiの定理**：Euler公式だけでは判定できない場合と、非平面性の障害。
- **平面双対**：面を頂点へ変えると閉路と切断が入れ替わる。
- **平面性判定の構造**：Kuratowskiの定理の証明。
- **Euler公式と非平面性の判定**：橋を含む面境界の数え方、辺数評価による非平面性、交互端点の道。
## 読み方
最初の2頁でEuler公式と非平面性の例を押さえ、そのあとの頁では定義を先に確認する。Kuratowskiの定理の証明は長いので、途中で何を示しているかを見失わないように節ごとに目標を書き出しながら読む。
## 章末で言えること
有限グラフが平面的であるための必要十分条件は、$K_5$ または $K_{3,3}$ の細分を部分グラフとして含まないことである。
## 前の章から持ち込むもの
木、閉路と切断、連結性。


5-0 章の見取り図

2-1 根付き木と探索木

## 三角形を禁じると辺はいくつか
**Mantelの定理。** 三角形を持たない頂点数 $n$ の有限単純グラフの辺数 $E$ は $E\le\lfloor n^2/4\rfloor$。
**証明。** 辺 $uv$ の両端の近傍は三角形がないため交わらない。従って $d(u)+d(v)\le n$。全辺で足すと $\sum_vd(v)^2\le nE$。一方Cauchy–Schwarzで $(\sum_vd(v))^2=(2E)^2\le n\sum_vd(v)^2$。$E>0$ なら $4E^2\le n^2E$ より $E\le n^2/4$。$E=0$ も明らか。辺数は整数なので床を取る。□
二部完全グラフ $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ は三角形がなく辺数が $\lfloor n^2/4\rfloor$ で、境界は達成される。これは三角形禁止の場合であり、長い閉路や任意の部分グラフを禁じる一般極値問題まで解いたものではない。
**演習。** $n=5$ のとき最大辺数と達成例を挙げよ。
**解答。** $\lfloor25/4\rfloor=6$。$K_{2,3}$ が6辺を持つ。


8-1 Mantelの定理

9-1 幅優先探索と深さ優先探索

## 配属はいつ可能か
三人の学生 $a,b,c$ を三つの研究室 $1,2,3$ へ一人ずつ配属します。希望は
$$
N(a)=\{1,2\},\qquad
N(b)=\{1\},\qquad
N(c)=\{2,3\}
$$
だとします。$b$ を1、$a$ を2、$c$ を3へ送れば全員の希望を満たせます。
しかし $a,b,c$ が全員 $\{1,2\}$ だけを希望すれば不可能です。三人の候補先を合わせても二室しかないからです。
問題は、個々人の候補数では決まりません。任意の学生集団 $S$ について、その集団が使える研究室全体 $N(S)$ が少なくとも $|S|$ 個必要です。驚くべきことに、この明らかな必要条件は十分でもあります。
## 二部グラフ
&&&def 二部グラフ [05-def-bipartite-graph]
グラフ $G$ が[[二部グラフ]]であるとは、頂点集合を互いに交わらない二集合 $X,Y$ に分け
$$
V(G)=X\sqcup Y
$$
とし、すべての辺が $X$ の頂点と $Y$ の頂点を結ぶようにできることをいう。$(X,Y)$ を二部表示という。
$X$ の全頂点と $Y$ の全頂点の間にすべての辺がある二部グラフを[[完全二部グラフ]]といい、$K_{|X|,|Y|}$ と書く。
&&&
学生と研究室、労働者と仕事、数とその素因数のように対象が二種類に分かれる関係は、自然に二部グラフになります。
木は二部グラフです。一つの根からの距離が偶数か奇数かにより頂点を二分できます。一般のグラフについても、二部性はodd cycleがないことと一致します。
&&&thm 二部グラフのodd cycle判定 [05-thm-bipartite-odd-cycle]
グラフ $G$ が二部グラフであるための必要十分条件は、$G$ が奇数長のcycleを含まないことである。
&&&
&&&prf [05-prf-bipartite-odd-cycle]
$G$ が二部表示 $(X,Y)$ をもつとします。walkは一辺進むごとに $X$ と $Y$ の間を移ります。出発点へ戻るには偶数回移る必要があるため、すべてのcycleの長さは偶数です。
逆に $G$ がodd cycleをもたないとします。各連結成分で根 $r$ を一つ選び、$r$ からの最短pathの長さを $d(r,v)$ と書きます。距離が偶数の頂点を $X$、奇数の頂点を $Y$ に入れます。
辺 $uv$ の両端の距離が同じ偶奇だと仮定します。$r$ から $u,v$ への最短pathを取り、二つが最後に共有する頂点を $w$ とします。$w$ から $u$ への部分と $w$ から $v$ への部分は内部で交わりません。二つの長さの和は $d(r,u)+d(r,v)-2d(r,w)$ で偶数です。これに辺 $uv$ を加えると奇数長のcycleができ、仮定に反します。従って各辺は異なる偶奇の頂点を結び、$(X,Y)$ は二部表示です。非連結の場合も成分ごとに同じ操作をすればよいです。□
&&&
## matching
&&&def matchingと飽和 [05-def-matching-saturation]
グラフ $G$ の辺集合 $M\subseteq E(G)$ で、どの二辺も端点を共有しないものを[[マッチング (グラフ理論)|matching]]という。
matching $M$ のある辺の端点になっている頂点を $M$ により[[飽和頂点|飽和]]されるという。すべての頂点を飽和するmatchingを[[完全マッチング|perfect matching]]という。
二部グラフ $(X,Y)$ で $X$ の全頂点を飽和するmatchingを、$X$ を飽和するmatchingという。
&&&
matchingの各辺は、互いに重ならない「割当」を一つずつ表します。$X$ を学生、$Y$ を研究室とすれば、$X$ を飽和するmatchingが全学生への異なる研究室の割当です。
## 集団の候補先
&&&def 集合の近傍 [05-def-set-neighborhood]
二部グラフ $(X,Y)$ と部分集合 $S\subseteq X$ に対して
$$
N(S)=\{y\in Y\mid \text{ある }x\in S\text{ と }xy\in E(G)\}
$$
を $S$ の[[集合の近傍 (グラフ理論)|近傍]]という。
&&&
$N(S)$ は個々の $N(x)$ の和集合です。学生集団 $S$ が選べる研究室全体に対応します。
&&&prop Hall条件の必要性 [05-prop-hall-necessary]
二部グラフ $(X,Y)$ に $X$ を飽和するmatchingがあれば、すべての $S\subseteq X$ に対して
$$
|N(S)|\ge|S|
$$
が成り立つ。
&&&
&&&prf [05-prf-hall-necessary]
matchingで $S$ の各頂点に割り当てられた相手は、すべて $N(S)$ に属します。matchingの辺は端点を共有しないので、$S$ の異なる頂点は異なる相手へ割り当てられます。従って $N(S)$ には少なくとも $|S|$ 個の頂点があります。□
&&&
## Hallの結婚定理
&&&thm Hallの結婚定理 [05-thm-hall-marriage]
有限二部グラフ $(X,Y)$ が $X$ を飽和するmatchingをもつための必要十分条件は、すべての部分集合 $S\subseteq X$ に対して
$$
|N(S)|\ge|S|
$$
が成り立つことである。
&&&
&&&prf [05-prf-hall-marriage]
必要性は前の命題で示しました。十分性を $|X|$ に関する帰納法で証明します。
$|X|=0$ なら空matchingが $X$ を飽和します。$|X|=1$ なら、唯一の頂点 $x$ に対して $|N(\{x\})|\ge1$ なので隣接辺を一本選べます。
$|X|\ge2$ とし、より小さい左側頂点集合をもつ二部グラフで定理が成り立つと仮定します。二つの場合に分けます。
### 場合1：等号になる非自明な部分集合がある
ある空でない真部分集合 $S\subsetneq X$ が
$$
|N(S)|=|S|
$$
を満たすとします。$S$ と $N(S)$ が誘導する二部グラフでは、任意の $A\subseteq S$ の近傍は元のグラフでの $N(A)$ と同じです。従ってHall条件を満たし、帰納法の仮定から $S$ を飽和するmatching $M_1$ があります。
残りの二部グラフ
$$
(X\setminus S, Y\setminus N(S))
$$
もHall条件を満たすことを示します。$T\subseteq X\setminus S$ を取ります。この残りのグラフでの近傍は
$$
N(T)\setminus N(S)
$$
です。元のグラフで $S\cup T$ にHall条件を使うと
$$
|N(S\cup T)|\ge|S|+|T|.
$$
一方
$$
N(S\cup T)=N(S)\cup N(T)
$$
なので
$$
|N(S\cup T)|
=|N(S)|+|N(T)\setminus N(S)|.
$$
$|N(S)|=|S|$ を代入して
$$
|N(T)\setminus N(S)|\ge|T|.
$$
従って残りにも帰納法を適用でき、$X\setminus S$ を飽和するmatching $M_2$ があります。$M_1$ の右端点は $N(S)$、$M_2$ の右端点はその外側なので、$M_1\cup M_2$ はmatchingで $X$ を飽和します。
### 場合2：すべての非自明な部分集合で不等号が厳しい
すべての空でない真部分集合 $S\subsetneq X$ に対して
$$
|N(S)|\ge|S|+1
$$
とします。任意の頂点 $x\in X$ を選びます。Hall条件から $x$ には隣接頂点 $y\in Y$ があります。$x,y$ とそれらに接続する辺を削除した二部グラフを考えます。
任意の $T\subseteq X\setminus\{x\}$ について、元の近傍から削除される可能性があるのは $y$ 一つだけです。$T$ は $X$ の真部分集合なので
$$
|N(T)|\ge|T|+1.
$$
従って削除後も近傍の大きさは少なくとも $|T|$ です。帰納法の仮定から、削除後のグラフには $X\setminus\{x\}$ を飽和するmatching $M'$ があります。これに辺 $xy$ を加えると $X$ を飽和するmatchingになります。
二つの場合がすべてを尽くすため、十分性が証明されました。□
&&&
この証明で等号 $|N(S)|=|S|$ となる集合は、先にその内部で完全に割り当てるべき「余裕のない塊」です。厳しい不等号しかなければ、一組を任意に確定しても残りに十分な余裕があります。
## 計算例――配属を判定する
$$
X=\{a,b,c,d\},\qquad Y=\{1,2,3,4\}
$$
とし
$$
N(a)=\{1,2\},\quad
N(b)=\{1,2\},\quad
N(c)=\{2,3\},\quad
N(d)=\{3,4\}
$$
とします。
単集合の近傍はすべて1個以上。二要素集合では $\{a,b\}$ の近傍がちょうど2個で、他は少なくとも2個。三要素なら少なくとも $\{1,2,3\}$ の3個、全体なら4個です。Hall条件を満たします。
実際
$$
M=\{a1,b2,c3,d4\}
$$
は $X$ を飽和するmatchingです。ここで $\{a,b\}$ は余裕のない集合なので、研究室1,2を二人で使い切ります。
## 完全matchingとperfect matching
&&&cor balanced二部グラフのperfect matching [05-cor-balanced-perfect-matching]
有限二部グラフ $(X,Y)$ で $|X|=|Y|$ とする。すべての $S\subseteq X$ に対して $|N(S)|\ge|S|$ ならperfect matchingが存在する。
&&&
&&&prf [05-prf-balanced-perfect-matching]
Hallの定理により $X$ を飽和するmatchingがあります。matchingは $|X|$ 本の辺をもち、右側で相異なる $|X|=|Y|$ 頂点を使います。従って $Y$ の全頂点も飽和し、perfect matchingです。□
&&&
## 正則二部グラフにはperfect matchingがある
&&&thm 正則二部グラフのperfect matching [05-thm-regular-bipartite-perfect-matching]
$r\ge1$ とし、有限 $r$-正則二部グラフ $(X,Y)$ はperfect matchingをもつ。
&&&
&&&prf [05-prf-regular-bipartite-perfect-matching]
まず辺数を左右から数えると
$$
r|X|=|E(G)|=r|Y|.
$$
$r\ge1$ なので $|X|=|Y|$。
$S\subseteq X$ を取ります。$S$ の頂点から出る辺は各頂点 $r$ 本なので合計 $r|S|$ 本です。それらはすべて $N(S)$ の頂点へ入ります。$N(S)$ の各頂点へ入る辺はグラフ全体で $r$ 本しかないため
$$
r|S|\le r|N(S)|.
$$
従って $|S|\le|N(S)|$。Hall条件が成立し、$X$ を飽和するmatchingがあります。$|X|=|Y|$ なのでperfect matchingです。□
&&&
この定理を繰り返すと、$r$-正則二部グラフの辺集合を $r$ 個のperfect matchingへ分解できます。一つのperfect matchingを除くと各頂点の次数は $r-1$ になり、再び定理を適用できるからです。
## matchingを実際に見つける
Hallの帰納証明は存在を保証しますが、大きなグラフで全ての部分集合を調べるのは非効率です。実際の算法では、現在のmatchingに対し
- matchingに入っていない辺
- matchingに入っている辺
を交互に通るpathを探します。未飽和頂点から別の未飽和頂点へ到達したら、path上で「不使用」と「使用」を反転するとmatchingの大きさが1増えます。このaugmenting pathの存在と最大性の同値がBergeの補題で、「増加路」に置きます。
## 失敗の証明もHall集合が与える
割当が不可能なときは、単に探索に失敗しただけでは証明になりません。$|N(S)|<|S|$ となる具体的な集合 $S$ を示せば、「この $|S|$ 人は候補を合わせても $|N(S)|$ 枠しかない」という不可能性証明になります。
最大matching算法は、成功時にはmatchingを、失敗時にはこのような障害集合を返せます。これはmax-flow min-cut定理における「解」と「不可能性証明」の双対性へつながります。
## 演習
&&&exc cycleの二部性 [05-exc-bipartite-cycle]
cycle graph $C_n$ が二部グラフであるための必要十分条件が、$n$ が偶数であることだと示せ。
&&&
&&&prf 解答 [05-prf-bipartite-cycle-answer]
$n$ が奇数なら $C_n$ 自身がodd cycleなので、odd cycle判定により二部グラフではありません。
$n$ が偶数なら、cycle上の頂点を順に $v_1,\ldots,v_n$ とし
$$
X=\{v_1,v_3,\ldots,v_{n-1}\},\qquad
Y=\{v_2,v_4,\ldots,v_n\}
$$
と分けます。連続する頂点は異なる集合に入り、最後の辺 $v_nv_1$ も偶数番と奇数番を結ぶので二部表示です。□
&&&
&&&exc Hall条件の失敗 [05-exc-hall-obstruction]
$$
N(a)=\{1,2\},\quad N(b)=\{1,2\},\quad
N(c)=\{1,2\},\quad N(d)=\{3,4\}
$$
であるとき、左側全員を飽和するmatchingが存在しないことを、障害集合を示して証明せよ。
&&&
&&&prf 解答 [05-prf-hall-obstruction-answer]
$S=\{a,b,c\}$ と取ると
$$
N(S)=\{1,2\},\qquad |N(S)|=2<3=|S|.
$$
三人 $a,b,c$ を相異なる二つの相手1,2へ割り当てることはできません。Hall条件の必要性に反するため、全員を飽和するmatchingは存在しません。□
&&&
&&&exc matchingを構成する [05-exc-hall-construct]
$$
N(a)=\{1,3\},\quad N(b)=\{1,2\},\quad
N(c)=\{2,3,4\},\quad N(d)=\{3,4\}
$$
に対し、左側全員を飽和するmatchingを一つ構成せよ。また $\{a,b\}$ と $\{c,d\}$ の候補を比較せよ。
&&&
&&&prf 解答 [05-prf-hall-construct-answer]
例えば
$$
M=\{a3,b1,c2,d4\}
$$
は端点を共有せず、四人をすべて飽和します。
$$
N(\{a,b\})=\{1,2,3\},\qquad
N(\{c,d\})=\{2,3,4\}
$$
で、どちらも2人に対して3候補あり一つ余裕があります。特定の二人組が候補を使い切る状況ではありません。□
&&&
&&&exc 正則二部グラフの分解 [05-exc-regular-bipartite-decomposition]
有限2-正則二部グラフの各連結成分が偶cycleであり、その辺集合が二つのperfect matchingへ分かれることを示せ。
&&&
&&&prf 解答 [05-prf-regular-bipartite-decomposition-answer]
有限連結2-正則グラフはcycleです。実際、任意の頂点から辺をたどると次数2なので行き止まらず、有限性から頂点を再訪してcycleを得ます。連結で、cycle外へ出る辺をもつ頂点は次数が3以上になるため、成分全体がそのcycleです。
二部グラフにodd cycleはないので各cycleの長さは偶数です。偶cycleの辺を一周しながら一つおきに赤・青へ塗ると、各頂点には赤辺と青辺が一本ずつ接続します。全成分で赤辺を集めたものと青辺を集めたものが、それぞれperfect matchingです。□
&&&
&&&exc 集合族の代表元 [05-exc-hall-distinct-representatives]
有限集合族 $A_1,\ldots,A_n$ から、各 $i$ について $a_i\in A_i$ を選び、$a_1,\ldots,a_n$ を相異なるようにできるための必要十分条件を書き、Hallの定理から証明せよ。
&&&
&&&prf 解答 [05-prf-hall-distinct-representatives-answer]
必要十分条件は、すべての添字集合 $I\subseteq[n]$ に対して
$$
\left|\bigcup_{i\in I}A_i\right|\ge|I|
$$
となることです。
左側頂点を添字 $1,\ldots,n$、右側頂点を和集合 $A_1\cup\cdots\cup A_n$ の要素とし、$a\in A_i$ のとき辺 $ia$ を結びます。添字集合 $I$ の近傍はちょうど $\bigcup_{i\in I}A_i$ です。相異なる代表元の選択は左側を飽和するmatchingと同じなので、主張はHallの定理そのものです。□
&&&
&&&exc domino敷き詰めの必要条件 [05-exc-matching-domino-necessary]
格子状の盤面をcheckerboardのように白黒に塗る。隣接二マスを覆うdominoだけで盤面を敷き詰められるなら、白マスと黒マスの個数が等しいことを示せ。この条件が十分ではない例も与えよ。
&&&
&&&prf 解答 [05-prf-matching-domino-necessary-answer]
格子で隣接する二マスは必ず異なる色です。従って各dominoは白マス一つと黒マス一つを覆います。盤面全体を敷き詰めれば、使った白黒の個数はdomino数に等しく、白マス数と黒マス数は等しいです。
しかし同数だけでは十分でありません。座標
$$
(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(-1,1),(1,4)
$$
にある8マスだけを残した連結な盤面を考えます。座標和の偶奇で塗ると白黒は4マスずつです。しかし白マス $(0,0)$ と $(-1,1)$ は、盤面内ではどちらも黒マス $(0,1)$ だけに隣接します。この白二マスの集合 $S$ に対して
$$
|N(S)|=1<2=|S|.
$$
Hall条件が破れるため敷き詰められません。十分性には全体の個数だけでなく、任意の白マス部分集合の隣接黒マス数を調べる必要があります。□
&&&

3-1 二部グラフとマッチング

> **前提知識**：二部グラフ、平面グラフ
> 
## 時間割を色で表す
複数の試験を時間帯へ割り当てます。同じ学生が受ける二試験は同時に実施できません。試験を頂点、同じ学生を共有する二試験を辺で結ぶと、一つの時間帯を一つの色として、隣接頂点へ異なる色を割り当てる問題になります。
必要な最少時間帯はグラフの彩色数です。彩色は地図だけの問題ではなく、時間割、周波数割当、register allocation、互いに両立しない仕事の分類を同じ形へ翻訳します。
## proper coloringと彩色数
&&&def 頂点彩色と彩色数 [05-def-vertex-coloring-chromatic-number]
グラフ $G$ の $k$-[[頂点彩色|coloring]]とは、写像
$$
c:V(G)\longrightarrow\{1,2,\ldots,k\}
$$
で、すべての辺 $uv\in E(G)$ に対して
$$
c(u)\ne c(v)
$$
を満たすものをいう。この条件を満たす彩色を[[正則彩色|proper coloring]]という。
$G$ をproperに彩色するために必要な最少色数を[[彩色数]]といい、$\chi(G)$ と書く。頂点をもたないグラフでは $\chi(G)=0$ と約束する。
&&&
色の名前には意味がありません。色1と色2を全体で交換しても同じ制約を満たします。本質は頂点集合を、各内部に辺をもたない独立集合へ何個に分割できるかです。
&&&prop 彩色と独立集合への分割 [05-prop-coloring-independent-partition]
$G$ が $k$-colorableであるための必要十分条件は、$V(G)$ を高々 $k$ 個の独立集合へ分割できることである。
&&&
&&&prf [05-prf-coloring-independent-partition]
proper coloring $c$ があれば、各色 $i$ の色類
$$
V_i=\{v\in V(G)\mid c(v)=i\}
$$
を取ります。同じ色の二頂点が隣接するとproperでないため、各 $V_i$ は独立集合です。色類は互いに交わらず全頂点を尽くします。
逆に独立集合への分割 $V(G)=V_1\sqcup\cdots\sqcup V_k$ があれば、$V_i$ の頂点へ色 $i$ を割り当てます。同じ色の頂点間には辺がないのでproper coloringです。□
&&&
## 下界――cliqueはすべて異なる色を要求する
&&&def cliqueとclique数 [05-def-clique-number]
頂点部分集合 $S\subseteq V(G)$ で、$S$ の任意の相異なる二頂点が隣接するとき、$S$ を[[クリーク (グラフ理論)|clique]]という。最大cliqueの頂点数を[[クリーク数|clique数]]といい、$\omega(G)$ と書く。
&&&
&&&prop clique lower bound [05-prop-clique-lower-bound]
$$
\chi(G)\ge\omega(G).
$$
&&&
&&&prf [05-prf-clique-lower-bound]
clique内の任意の二頂点は隣接するので、proper coloringでは全頂点が相異なる色をもたなければなりません。最大cliqueに $\omega(G)$ 頂点あるため、少なくともその数の色が必要です。□
&&&
逆向きの等号は一般には成り立ちません。長さ5のcycle $C_5$ は三頂点cliqueを含まないので $\omega(C_5)=2$ ですが、2色では塗れず $\chi(C_5)=3$ です。
## greedy coloring
頂点を一つずつ処理し、既に彩色された隣接頂点が使っていない最小番号の色を割り当てます。
&&&thm greedy coloringの上界 [05-thm-greedy-coloring]
頂点順序
$$
v_1,v_2,\ldots,v_n
$$
を固定する。$v_i$ より前に現れる隣接頂点の個数が常に高々 $d$ なら、greedy coloringは高々 $d+1$ 色で $G$ をproperに彩色する。
&&&
&&&prf [05-prf-greedy-coloring]
$v_i$ を彩色する時点で色が決まっているのは前に現れた頂点だけです。そのうち $v_i$ と隣接するものは高々 $d$ 個なので、禁止される色も高々 $d$ 色です。
$1,2,\ldots,d+1$ の $d+1$ 色のうち少なくとも一色は使われていません。その色を $v_i$ へ割り当てられます。こうして全頂点を処理できます。
各辺 $v_iv_j$ で $i<j$ とすると、$v_j$ を塗る際に $v_i$ の色を避けるため、最終的に両端の色は異なります。従ってproper coloringです。□
&&&
&&&cor 最大次数上界 [05-cor-chromatic-max-degree]
最大次数を $\Delta(G)$ とすると
$$
\chi(G)\le\Delta(G)+1.
$$
&&&
&&&prf [05-prf-chromatic-max-degree]
任意の頂点順序で、各頂点より前に現れる隣接頂点数はその次数以下、従って $\Delta(G)$ 以下です。greedy定理で $\Delta(G)+1$ 色あれば足ります。□
&&&
この上界は $K_n$ で等号です。しかし多くのグラフでは頂点順序を工夫すると大幅に少ない色で塗れます。「貪欲彩色と退化度」では、各部分グラフに低次数頂点があるという退化度を使い、良い順序を後ろから作ります。
## 2-coloringと二部グラフ
&&&thm 二部グラフと2-coloring [05-thm-bipartite-two-color]
辺をもつグラフ $G$ について、次は同値である。
1. $G$ は二部グラフである。
2. $G$ は2-colorableである。
3. $G$ はodd cycleを含まない。
従って、辺をもつ二部グラフでは $\chi(G)=2$ である。
&&&
&&&prf [05-prf-bipartite-two-color]
$(1)\Rightarrow(2)$。二部表示 $(X,Y)$ に対し、$X$ を色1、$Y$ を色2で塗ります。すべての辺は二部の間を結ぶのでproperです。
$(2)\Rightarrow(1)$。色1の頂点集合を $X$、色2を $Y$ とすれば、proper性により同色頂点間に辺はなく、すべての辺が二部の間を結びます。
$(1)\Leftrightarrow(3)$ は「二部グラフとマッチング」のodd cycle判定で完全に証明しました。
辺が一つ以上あれば隣接二頂点は異なる色を必要とするため $\chi(G)\ge2$。二部性から $\chi(G)\le2$ なので等号です。□
&&&
## 基本グラフの彩色数
&&&prop 完全グラフ・path・cycle [05-prop-basic-chromatic-numbers]
次が成り立つ。
1. $\chi(K_n)=n$。
2. $n\ge2$ に対して $\chi(P_n)=2$。
3. $n\ge3$ に対して
   $$
   \chi(C_n)=
   \begin{cases}
   2&n\text{ が偶数},\\
   3&n\text{ が奇数}.
   \end{cases}
   $$
&&&
&&&prf [05-prf-basic-chromatic-numbers]
$K_n$ は全頂点がcliqueなので少なくとも $n$ 色必要で、各頂点へ別の色を与えれば $n$ 色で足ります。
$P_n$ は辺をもち、木なので二部グラフです。従って彩色数は2です。
$C_n$ は $n$ が偶数なら二部グラフなので2色です。$n$ が奇数ならodd cycleそのものなので2-colorableでなく、少なくとも3色必要です。一方、path $v_1,\ldots,v_{n-1}$ を色1,2で交互に塗り、最後の頂点 $v_n$ だけ色3にすればproperなので3色で足ります。□
&&&
## 色数の上界と下界を挟む
彩色数を決める標準手順は、同じ整数へ達する下界と上界を作ることです。
- 下界：clique、odd cycle、部分グラフ、独立集合の最大サイズ。
- 上界：具体的な彩色、greedy順序、構造に基づく帰納法。
例えばwheel graph $W_6$ を、$C_5$ の全頂点へ中心頂点を接続したグラフとします。外周 $C_5$ に3色必要で、中心は外周の全頂点と隣接します。外周の3色をすべて避ける第四色が必要なので $\chi(W_6)\ge4$。外周を3色、中心を第四色で塗れるので $\chi(W_6)=4$ です。
## 平面グラフは6色で塗れる
「平面グラフ」で、頂点数3以上のsimple planar graphには次数5以下の頂点が存在することを証明しました。この局所情報だけで帰納法が動きます。
&&&thm 平面六色定理 [05-thm-planar-six-color]
すべての有限simple planar graph $G$ は6-colorableである。
&&&
&&&prf [05-prf-planar-six-color]
頂点数 $n=|V(G)|$ に関する帰納法で示します。$n\le6$ なら各頂点へ異なる色を与えればよいです。
$n\ge7$ とし、より少ない頂点をもつすべてのsimple planar graphが6-colorableだと仮定します。「平面グラフ」の低次数頂点の定理から、$G$ には次数5以下の頂点 $v$ があります。
$G-v$ は頂点を一つ削ったplanar graphなので、帰納法の仮定により6色でproperに塗れます。$v$ の隣接頂点は高々5個であり、それらが使う色は高々5色です。六色のうち少なくとも一色は隣接頂点に使われていません。その色を $v$ へ割り当てれば、$G$ 全体のproper 6-coloringになります。□
&&&
実際には平面グラフは4色で塗れますが、四色定理の既知の証明は大規模な場合分けと計算機検証を含み、本テキストの手計算中心のCoreには置きません。一方、Kempe chainを用いると5色までは比較的短い完全証明で到達できます。
&&&thm 平面五色定理 [05-thm-planar-five-color]
すべての有限simple planar graphは5-colorableである。
&&&
この定理は「平面グラフの五色定理」の中心定理です。そこで、次数5の頂点の五つの隣接頂点がすべて異なる色を使う唯一の難しい場合に、二色で塗られた連結成分を入れ替えるKempe chainを導入し、完全に証明します。本章では六色定理までを証明済み範囲とし、五色定理を未証明の推論には使いません。
## greedy coloringは順序に依存する
path $P_4$ の頂点を辺 $x_1x_2,x_2x_3,x_3x_4$ とします。順序
$$
x_1,x_2,x_3,x_4
$$
ならgreedyは色1,2,1,2の二色です。
しかし順序
$$
x_1,x_4,x_2,x_3
$$
では、$x_1,x_4$ が色1、$x_2$ が色2となり、最後の $x_3$ は隣接頂点 $x_4$ の色1と $x_2$ の色2をともに避けて色3を使います。同じgraphでも順序だけで使用色数が変わりました。greedy算法が返す色数は上界であり、常に彩色数そのものとは限りません。
## 応用――試験時間割
試験A,B,C,D,Eについて、同じ学生を共有する組が
$$
AB,AC,BC,CD,DE
$$
だとします。A,B,Cは三角形を作るので少なくとも3時間帯必要です。
具体的に
$$
c(A)=1,\quad c(B)=2,\quad c(C)=3,\quad
c(D)=1,\quad c(E)=2
$$
とすれば、すべての衝突辺の両端が異なる色です。従って必要最少時間帯は3です。下界を三角形、上界を具体的彩色が与えました。
## 演習
&&&exc complementと彩色 [05-exc-coloring-complement-partition]
$G$ のproper $k$-coloringが、補グラフ $\overline G$ の頂点集合を $k$ 個のcliqueへ分割することと同値であることを示せ。
&&&
&&&prf 解答 [05-prf-coloring-complement-partition-answer]
$G$ の各色類は独立集合です。同じ色類の相異なる二頂点は $G$ で隣接しないため、$\overline G$ では隣接します。従って各色類は $\overline G$ のcliqueです。
逆に $V(G)$ が $\overline G$ の $k$ 個のcliqueへ分割されていれば、各clique内の二頂点は $G$ では隣接しません。各部分へ一色を割り当てると $G$ のproper coloringになります。□
&&&
&&&exc wheel graph [05-exc-coloring-wheel]
$n\ge4$ とし、cycle $C_{n-1}$ の全頂点へ一つの中心頂点を接続したwheel graph $W_n$ の彩色数を求めよ。
&&&
&&&prf 解答 [05-prf-coloring-wheel-answer]
外周長 $n-1$ が偶数、すなわち $n$ が奇数なら、外周は2色で塗れます。中心は外周の両色を避ける第四色ではなく第三色を使えばよいので $\chi(W_n)\le3$。中心と外周の隣接二頂点は三角形を作るため $\chi(W_n)\ge3$。従って3です。
外周長 $n-1$ が奇数、すなわち $n$ が偶数なら、外周には3色必要です。中心は外周の全頂点に隣接し、properなodd cycle彩色では三色すべてが外周に現れるため第四色が必要です。第四色を中心へ使えば足りるので $\chi(W_n)=4$。従って
$$
\chi(W_n)=
\begin{cases}
3&n\text{ が奇数},\\
4&n\text{ が偶数}.
\end{cases}
$$
□
&&&
&&&exc greedy順序を比較する [05-exc-coloring-bad-greedy-order]
path $P_4=x_1x_2x_3x_4$ にgreedy coloringを適用する。順序
$$
x_1,x_2,x_3,x_4
$$
と順序
$$
x_1,x_4,x_2,x_3
$$
で使用色数を比較し、真の彩色数を求めよ。
&&&
&&&prf 解答 [05-prf-coloring-bad-greedy-order-answer]
最初の順序では
$$
c(x_1),c(x_2),c(x_3),c(x_4)=1,2,1,2
$$
となり二色です。
第二の順序では $x_1,x_4$ は色1、$x_2$ は $x_1$ を避け色2です。最後の $x_3$ は $x_4$ の色1と $x_2$ の色2を避け、色3になります。
$P_4$ は辺をもつ木、従って二部グラフなので真の彩色数は2です。第二のgreedy結果3は最適ではありません。□
&&&
&&&exc 独立集合からの下界 [05-exc-coloring-independence-bound]
最大独立集合の大きさを $\alpha(G)$ とする。$n$ 頂点グラフについて
$$
\chi(G)\ge\left\lceil\frac{n}{\alpha(G)}\right\rceil
$$
を示せ。
&&&
&&&prf 解答 [05-prf-coloring-independence-bound-answer]
proper coloringの各色類は独立集合なので、一色類に含まれる頂点は高々 $\alpha(G)$ 個です。$k$ 色で全 $n$ 頂点を塗れたなら
$$
n\le k\alpha(G).
$$
従って
$$
k\ge\frac{n}{\alpha(G)}.
$$
$k$ は整数なので $k\ge\lceil n/\alpha(G)\rceil$。最小の $k=\chi(G)$ にも同じ下界が成り立ちます。□
&&&
&&&exc planar graphの平均次数 [05-exc-coloring-planar-average]
$v\ge3$ のsimple planar graphの平均次数が6未満であることを示し、次数5以下の頂点の存在をもう一度導け。
&&&
&&&prf 解答 [05-prf-coloring-planar-average-answer]
planar辺数上界 $e\le3v-6$ と握手補題から
$$
\frac1v\sum_{x\in V}\deg(x)
=\frac{2e}{v}
\le\frac{2(3v-6)}v
=6-\frac{12}{v}<6.
$$
すべての頂点の次数が6以上なら平均も6以上になるため矛盾です。従って次数5以下の頂点があります。□
&&&
&&&exc 時間割を彩色する [05-exc-coloring-schedule]
科目 $A,B,C,D,E,F$ の衝突辺が
$$
AB,AC,BC,CD,DE,EF,FD
$$
である。彩色数を求め、最少時間帯の割当を一つ与えよ。
&&&
&&&prf 解答 [05-prf-coloring-schedule-answer]
$A,B,C$ が三角形を作るので少なくとも3色必要です。また $D,E,F$ も三角形です。
次の3-coloringを取れます。
$$
c(A)=1,\quad c(B)=2,\quad c(C)=3,
$$
辺 $CD$ があるので $D$ を1とし、
$$
c(D)=1,\quad c(E)=2,\quad c(F)=3
$$
とします。列挙された各辺の両端は異なる色です。従って $\chi=3$ で、色1,2,3を三つの時間帯とすればよいです。□
&&&

6-1 グラフ彩色

> **前提知識**：HallとKőnig
> 
## 一本のpathだけでは容量を使い切れない
sourceからsinkへ物資や情報を送りたいとします。各有向arcには一度に通せる容量があります。一つのpathへ可能な限り流すだけでは、早い選択が後の経路を塞ぐことがあります。
matchingで既存の割当をalternating pathに沿って反転したように、flowでも過去の送り方を部分的に取り消す必要があります。その「まだ増やせる向き」と「取り消せる逆向き」を同時に記録するのがresidual networkです。
## networkとflow
&&&def capacitated network [34-def-capacitated-network]
[[容量付きネットワーク|capacitated network]]とは、有限有向multigraph $D=(V,A)$、相異なるsource $s$ とsink $t$、各arc $a\in A$ の容量
$$
c(a)\in\mathbb R_{\ge0}
$$
からなる。sourceへ入るarcとsinkから出るarcはないものとする。
&&&
平行arcと互いに逆向きのarcを許し、arcには固有の名前を付けて区別します。
&&&def feasible flowとflow value [34-def-feasible-flow]
network上のflowとは、各arcに実数 $f(a)$ を割り当て、次を満たすものである。
1. 容量制約：
$$
0\le f(a)\le c(a)\qquad(a\in A).
$$
2. 保存則：$v\ne s,t$ に対して
$$
\sum_{\substack{a\in A\\a\text{ enters }v}}f(a)
=
\sum_{\substack{a\in A\\a\text{ leaves }v}}f(a).
$$
この二条件を満たすflowを[[実行可能フロー|feasible flow]]という。[[フロー値|flowの値]]を
$$
|f|=
\sum_{a\text{ leaves }s}f(a)
-
\sum_{a\text{ enters }s}f(a)
$$
と定める。
&&&
全頂点で「流出－流入」を足すと各arcが一度ずつ正負に現れて相殺するため、保存則から
$$
|f|=
\sum_{a\text{ enters }t}f(a)
-
\sum_{a\text{ leaves }t}f(a)
$$
も成り立ちます。sourceから正味に出た量とsinkへ正味に入った量は等しいのです。
&&&prop flow valueの基本上界 [34-prop-flow-value-bound]
任意のfeasible flowに対して
$$
|f|\le\sum_{a\text{ leaves }s}c(a).
$$
&&&
&&&prf [34-prf-flow-value-bound]
sourceへ入るflowは非負なので
$$
|f|
=\sum_{a\text{ leaves }s}f(a)-\sum_{a\text{ enters }s}f(a)
\le\sum_{a\text{ leaves }s}f(a)
\le\sum_{a\text{ leaves }s}c(a).
$$
□
&&&
従って最大化問題には有限の上界があります。
## residual network
各original arc $a:u\to v$ について、現在のflow $f(a)$ からできる二種類の操作を考えます。
- forward residual arc $a^+:u\to v$：さらに $c(a)-f(a)$ だけ増やせる。
- backward residual arc $a^-:v\to u$：既存flowを $f(a)$ だけ取り消せる。
&&&def residual network [34-def-residual-network]
flow $f$ に対する[[残余ネットワーク|residual network]] $D_f$ は、各original arc $a:u\to v$ について
$$
c_f(a^+)=c(a)-f(a)>0
$$
ならforward residual arc $a^+$ を置き、
$$
c_f(a^-)=f(a)>0
$$
ならbackward residual arc $a^-$ を置く有向multigraphである。
&&&
original networkに $v\to u$ という別arcがある場合、そのforward residual arcと、$u\to v$ のbackward residual arcは同じ向きでも異なる操作です。arc名を区別する理由です。
&&&def augmenting pathとbottleneck [34-def-flow-augmenting-path]
$D_f$ における $s$ から $t$ への有向path $P$ を $f$-[[増加路 (フロー)|augmenting path]]という。その[[ボトルネック容量|bottleneck]] residual capacityを
$$
\Delta(P)=\min_{b\in E(P)}c_f(b)
$$
と定める。
&&&
$P$ に沿って $\Delta=\Delta(P)$ だけaugmentするとは、forward residual arc $a^+$ を通るたび $f(a)$ を $\Delta$ 増やし、backward residual arc $a^-$ を通るたび $f(a)$ を $\Delta$ 減らすことです。
## augmentationがflowを保つこと
&&&lemma augmentation lemma [34-lem-augmentation]
feasible flow $f$ とaugmenting path $P$ に対し、$0<\delta\le\Delta(P)$ だけaugmentして得る $f'$ はfeasible flowであり
$$
|f'|=|f|+\delta
$$
を満たす。
&&&
&&&prf [34-prf-augmentation]
forward arc $a^+$ では
$$
f'(a)=f(a)+\delta\le f(a)+c(a)-f(a)=c(a)
$$
で、非負性も保たれます。backward arc $a^-$ では
$$
f'(a)=f(a)-\delta\ge f(a)-f(a)=0
$$
で、上限も保たれます。従って容量制約が成り立ちます。
pathの内部頂点 $v$ ではresidual pathが一本で入り一本で出ます。forwardかbackwardかにかかわらず、入る操作は $v$ への正味流入を $\delta$ 増やし、出る操作は正味流出を $\delta$ 増やすと解釈できます。両者が相殺するため保存則は保たれます。arcごとに確認しても、original flowの増減が $v$ の流入側と流出側で同量です。
sourceではpathが一本出て戻らず、正味流出が $\delta$ 増えます。sinkでは正味流入が $\delta$ 増えます。従って $|f'|=|f|+\delta$ です。□
&&&
backward arcは「物を逆向きに送る」のではなく、以前の選択を取り消す操作です。これによりgreedyな初期選択を後から修正できます。
## Ford--Fulkerson算法
&&&alg Ford--Fulkerson算法 [34-alg-ford-fulkerson]
1. zero flow $f(a)=0$ から始める。
2. residual network $D_f$ で $s$--$t$ path $P$ を探す。
3. 見つかれば $\Delta(P)$ だけaugmentし、2へ戻る。
4. pathがなければ停止して $f$ を出力する。
&&&
各反復でflow値は真に増えます。ただし実数容量では、増分が無限に小さくなり停止しない経路選択もあり得ます。整数容量では有限停止を完全に保証できます。
&&&thm 整数容量での有限停止とintegrality [34-thm-integral-termination]
全容量が非負整数なら、Ford--Fulkerson算法はどのaugmenting pathを選んでも有限回で停止し、途中および出力の全arc flowは整数である。反復回数は
$$
\sum_{a\text{ leaves }s}c(a)
$$
以下である。
&&&
&&&prf [34-prf-integral-termination]
初期flowは整数です。flowが整数なら各residual capacity
$$
c(a)-f(a)\quad\text{または}\quad f(a)
$$
も整数であり、path上の最小値 $\Delta(P)$ は正整数です。augmentationは各flowへ整数を加減するためintegralityが保たれます。
各反復でflow値は $\Delta(P)\ge1$ 増えます。一方、基本上界によりflow値はsourceから出る容量和を超えません。従って反復回数はその整数上界以下で、有限停止します。□
&&&
容量が全て有理数なら共通分母を掛けて整数容量へ変換できるので、やはり有限停止します。無理数容量では有限停止の保証にpath選択規則が必要です。BFSで最短arc数のaugmenting pathを選ぶEdmonds--Karp算法は、実容量でも有限回で停止します。その $O(|V||A|^2)$ 証明は「最大流最小切断定理」の定理後の発展へ置きます。
## 具体計算――backward arcで選択を直す
頂点 $s,a,b,t$ とarc
$$
s\to a,\quad s\to b,\quad a\to b,\quad a\to t,\quad b\to t
$$
を考え、容量を順に
$$
1,\ 1,\ 1,\ 1,\ 1
$$
とします。
最初にpath $s\to a\to b\to t$ へ1流すと、この三arcが飽和します。このままoriginal arcだけを見ると、残る $s\to b$ から先の $b\to t$ は飽和し、増やせません。
しかしresidual networkには $a\to b$ のbackward arc $b\to a$ があります。path
$$
s\to b\to a\to t
$$
をresidualにたどり1 augmentすると、
- $s\to b$ と $a\to t$ を1増やす。
- $a\to b$ を1減らす。
結果は
$$
s\to a\to t,\qquad s\to b\to t
$$
へ各1流す値2のflowです。過去の一本を取り消すことで二本へ組み替えました。
## flow decomposition
flowはarcごとの数値表ですが、その正の部分をsource--sink pathとdirected cycleの流れに分解できます。
&&&thm flow decomposition [34-thm-flow-decomposition]
有限network上のfeasible flow $f$ は、有限個の $s$--$t$ 有向path flowと有向cycle flowの和に分解できる。path flowの係数の総和は $|f|$ である。
&&&
&&&prf [34-prf-flow-decomposition]
正のflowをもつarcだけからなる有向部分グラフを考えます。$|f|>0$ ならsourceから正のflow arcをたどり始められます。内部頂点へ正のflowで入ったなら保存則により正のflowで出るarcもあります。
有限性から、たどり続けるとsinkへ到達するか、既出頂点を再訪します。sinkへ到達した場合は $s$--$t$ walkを得ます。途中のdirected cycleを削れば $s$--$t$ pathになります。再訪した場合はdirected cycleを得ます。
得たpathまたはcycle上のflow最小値 $\delta>0$ を全arcから引きます。容量制約と保存則を保ち、少なくとも一本の正flow arcが0になります。pathを引いた場合はflow値が $\delta$ 減り、cycleを引いた場合はflow値が変わりません。
path成分を引き終えてflow値が0になった後にも正flow arcが残る場合、そのarcから向きに沿ってたどります。sinkへの正味流入はflow値0に等しく、sinkから出るarcはないので、sinkへ入る正flow arcは残っていません。sourceへ入るarcもありません。従って有限性により内部頂点を再訪し、directed cycleを得ます。これを同じ方法で引きます。
正flow arc数が毎回少なくとも一つ減るので有限回でzero flowになります。引いたpath・cycleと係数を逆に足せば元の $f$ です。pathを引いたときだけ値がその係数だけ減り、最後は0なのでpath係数総和は元の $|f|$ です。□
&&&
cycle flowはsourceからsinkへ運ぶ正味量へ寄与しません。最大値だけが目的ならcycle成分を除いたflowを選べます。
## matchingをflowとして表す
二部グラフ $G=(X\sqcup Y,E)$ からnetworkを作ります。
1. source $s$ から各 $x\in X$ へ容量1のarc。
2. 各辺 $xy\in E$ を $x\to y$ の容量1 arc。
3. 各 $y\in Y$ からsink $t$ へ容量1のarc。
&&&thm 二部matchingとintegral flowの対応 [34-thm-matching-flow-correspondence]
上のnetworkで、整数値 $k$ のintegral flowが存在することと、$G$ に大きさ $k$ のmatchingが存在することは同値である。
&&&
&&&prf [34-prf-matching-flow-correspondence]
matching $M$ があれば、各 $xy\in M$ に対するpath
$$
s\to x\to y\to t
$$
へ1ずつ流します。matching辺は端点を共有しないため、$s\to x$ と $y\to t$ の容量1を超えず、内部保存則も成り立ちます。flow値は $|M|=k$ です。
逆に値 $k$ のintegral flowを取ります。容量は全て1なので各arc flowは0または1です。正のcycle flowを除いても値を変えずintegralです。残るflowをpathへ分解すると、各正flow pathは
$$
s\to x\to y\to t
$$
の形です。容量1により同じ $x$ または $y$ を二pathが共有できません。従ってflow 1の中間arc $x\to y$ を集めるとmatchingになり、その本数はflow値 $k$ です。□
&&&
この対応で、matchingのalternating pathはflow networkのresidual augmenting pathになります。「増加路」の反転はFord--Fulkersonの容量1版です。
## 演習
&&&exc feasible flowを判定する [34-exc-check-feasible-flow]
arc $s\to a,s\to b,a\to b,a\to t,b\to t$ の容量をそれぞれ $3,2,1,2,3$ とする。flow値を順に $2,1,1,1,2$ と割り当てたものがfeasibleか判定し、値を求めよ。
&&&
&&&prf 解答 [34-prf-check-feasible-flow-answer]
全arcでflowは0以上かつ容量以下です。頂点 $a$ には2入り、$a\to b$ と $a\to t$ へ1ずつ、合計2出るので保存されます。頂点 $b$ には $s$ から1、$a$ から1の合計2が入り、$t$ へ2出るので保存されます。
sourceからの正味流出は $2+1=3$、sinkへの流入も $1+2=3$ なのでfeasibleで値3です。□
&&&
&&&exc residual capacityを書く [34-exc-write-residual]
前問のflowについて、各original arcのforward・backward residual capacityを書け。
&&&
&&&prf 解答 [34-prf-write-residual-answer]
順に
$$
\begin{array}{c|ccccc}
a&s a&s b&a b&a t&b t\\ \hline
c(a)-f(a)&1&1&0&1&1\\
f(a)&2&1&1&1&2
\end{array}
$$
です。forward capacity 0の $a\to b$ はresidual networkに現れません。他のforward arcは表の第一行の正値をもち、各backward arcは第二行の値をもちます。□
&&&
&&&exc augmentationを実行する [34-exc-perform-augmentation]
前問のresidual networkでpath
$$
s\to b\to a\to t
$$
を考える。中央はoriginal arc $a\to b$ のbackward arcである。bottleneckを求め、最大量augmentした新flowを書け。
&&&
&&&prf 解答 [34-prf-perform-augmentation-answer]
residual capacitiesは $s\to b$ が1、$b\to a$ が $f(a\to b)=1$、$a\to t$ が1なのでbottleneckは1です。
augment後は $s\to b$ と $a\to t$ が1ずつ増え、$a\to b$ が1減ります。arc順の新flowは
$$
(2,2,0,2,2).
$$
値は3から4へ増え、$a$ では流入2・流出2、$b$ では流入2・流出2です。□
&&&
&&&exc 上界から最大性を判定する [34-exc-source-bound]
sourceから出るarc容量が4,3,2であるnetworkに値9のfeasible flowが見つかった。このflowがmaximumであることを、本章の基本上界だけで示せ。
&&&
&&&prf 解答 [34-prf-source-bound-answer]
任意のflow値はsourceから出る容量和
$$
4+3+2=9
$$
以下です。値9のfeasible flowがこの上界を達成しているため、それより大きいflowは存在せずmaximumです。これは特別な場合の最適性証明書です。□
&&&
&&&exc flowを分解する [34-exc-decompose-flow]
arc $s\to a,a\to t,s\to b,b\to t,a\to b,b\to a$ にflowを順に $2,2,1,1,1,1$ 流す。feasibleであることを確認し、path flowとcycle flowへ分解せよ。
&&&
&&&prf 解答 [34-prf-decompose-flow-answer]
$a$ には $s$ から2、$b$ から1入り、$t$ へ2、$b$ へ1出ます。$b$ には $s$ から1、$a$ から1入り、$t$ へ1、$a$ へ1出るので保存則が成立します。値は3です。
これは
$$
2(s\to a\to t)+1(s\to b\to t)
$$
というpath flowと
$$
1(a\to b\to a)
$$
というcycle flowの和です。path係数和は $2+1=3$ でflow値に一致します。□
&&&
&&&exc matching networkを作る [34-exc-build-matching-network]
二部グラフ
$$
N(x_1)=\{y_1,y_2\},\quad
N(x_2)=\{y_2\},\quad
N(x_3)=\{y_2,y_3\}
$$
を容量1 networkへ変換し、値3のintegral flowを一つ書け。
&&&
&&&prf 解答 [34-prf-build-matching-network-answer]
sourceから各 $x_i$、各 $x_i$ から表示された $y_j$、各 $y_j$ からsinkへ容量1 arcを置きます。
matching
$$
\{x_1y_1,x_2y_2,x_3y_3\}
$$
に対応して三path
$$
s\to x_1\to y_1\to t,\quad
s\to x_2\to y_2\to t,\quad
s\to x_3\to y_3\to t
$$
へ各1流せば値3です。各容量1 arcを高々一回しか使いません。□
&&&
## 本章で得たもの
residual networkは、未使用容量を進むforward操作と、以前のflowを取り消すbackward操作を同時に記録します。augmenting pathに沿う更新は容量制約・保存則を保ち、flow値をbottleneckだけ増やします。整数容量ではFord--Fulkersonが有限停止しintegral flowを返します。
しかし本章では、residual pathがなくなったflowが必ずmaximumだとはまだ証明していません。これがmax-flow min-cut定理です。


4-1 ネットワーク流

## 交差は描き方の問題か、構造の問題か
$K_4$ を四角形と二本の対角線として描くと、対角線が交差します。しかし一頂点を三角形の内側へ移せば、辺を交差させずに描けます。交差する図を一つ見つけても、グラフが平面に描けない証明にはなりません。
一方 $K_5$ は、どのように頂点を置き、辺を曲げても交差なしには描けません。この違いを調べるには、「グラフ」と「具体的な平面上の描画」を区別する必要があります。
## planar graphとplane graph
&&&def planar graphとplane graph [05-def-planar-plane-graph]
グラフ $G$ が[[平面的グラフ|planar graph]]であるとは、頂点を平面上の相異なる点、辺をその端点を結ぶ有限simple polygonal arcとして、異なる辺の内部が交わらないように描けることをいう。
交差なしの具体的な描画が一つ固定されたグラフを[[平面グラフ|plane graph]]という。
plane graphの描画を平面から除いた残りの連結成分を[[面 (グラフ理論)|面]]という。外側へ無限に広がる成分も一つの面として数え、[[外面]]という。
&&&
本書では平面分離の依存を有限polygonal版で閉じるため、plane drawingをpolygonal arcによる描画として定義します。有限graphについて、一般の単純arcによる埋め込み、polygonal埋め込み、直線辺による埋め込みが同じplanarity概念を与えることは、Fáryの定理を含む別の構造問題です。本書の全構成とKuratowski定理は上のpolygonal定義だけで完結します。
同じplanar graphでも描き方により面の境界は変わることがあります。しかし面の個数はEuler公式によって頂点数と辺数から決まり、描き方に依存しません。
## 面の境界では辺を重複して数える
面の周囲を歩いたときに通る辺の本数を、その面の次数と呼びます。bridgeは同じ面の境界を両側から支えるため、同じ面の境界に二度現れます。
例えば木を平面に描くと面は外面一つだけです。辺が $n-1$ 本なら外面の境界walkでは各辺を往復し、面次数は $2(n-1)$ です。
&&&prop 面次数の和 [05-prop-face-degree-sum]
plane graph $G$ の面全体を $F(G)$ とすると、境界での重複を込めて
$$
\sum_{f\in F(G)}\deg(f)=2|E(G)|.
$$
&&&
&&&prf [05-prf-face-degree-sum]
各辺の細い近傍には二つの側があります。辺が二つの異なる面を隔てる場合は各面の境界に一度ずつ現れます。bridgeのように両側が同じ面に接する場合は、その面の境界に二度現れます。いずれの場合も一辺は面次数の総和へちょうど2を寄与します。全辺について足せば結論を得ます。□
&&&
## 平面上の閉曲線について使う事実
Euler公式の証明では、次の初等的な平面の事実を使います。
&&&lemma 面を横切るarc [05-lem-plane-arc-splits-face]
plane graphの一つの面の境界上にある二点を、その面の内部を通る単純arcで結ぶと、その面は二つに分かれる。従って頂点数を変えず辺を一本加えると、面数はちょうど1増える。
&&&
&&&prf [05-prf-plane-arc-splits-face]
追加したarcの両端を結ぶ面境界上のwalkを一つ選ぶと、arcと境界walkから不要な反復部分を除いて単純閉曲線を得られます。単純閉曲線は平面を内側と外側の二領域に分け、その曲線を横切らずには一方から他方へ移れません。追加arcの両側にあった面内の小領域は異なる連結成分に分かれます。
元の面のどの点もarcのいずれか一方の側から到達でき、他の面は変更されません。従って元の一面が二面になり、面数は1増えます。ここで使った有限polygonal曲線の内外二成分とcrossing corollaryは、折れ線に対するJordan曲線定理から従います。□
&&&
本書で使うのは、cycleまたは有限本のpolygonal arcから作る単純閉曲線に対する定理だけです。一般の連続Jordan curveは必要としません。
## Euler公式
&&&thm 連結plane graphのEuler公式 [05-thm-euler-plane-formula]
有限連結plane graph $G$ の頂点数を $v$、辺数を $e$、面数を $f$ とすると
$$
v-e+f=2.
$$
&&&
&&&prf [05-prf-euler-plane-formula]
$G$ は連結なので全域木 $T$ をもちます。$T$ は $v$ 頂点 $v-1$ 辺です。
まず平面に描かれた木 $T$ の面は一つです。頂点一つなら明らかです。頂点数2以上なら葉とその接続辺を削ると小さい木になり、帰納法で面は一つです。葉と一本の突き出した辺を戻しても閉曲線は作らず、面を二つに分けないため面数は一つのままです。従って木では
$$
v-(v-1)+1=2.
$$
元のplane graph $G$ のうち $T$ にない辺を、元の描画に従って一本ずつ戻します。戻す辺の内部は既に戻したグラフと交わらず、一つの面の内部にあります。面を横切るarcの補題により、一本戻すごとに辺数と面数がともに1増えます。従って $v-e+f$ の値は変わりません。
すべての辺を戻すと $G$ になり、その値は木のときと同じ2です。□
&&&
### 例：立方体グラフ
立方体の頂点と辺をgraphとして平面に描くと
$$
v=8,\qquad e=12.
$$
Euler公式から
$$
f=2-v+e=2-8+12=6.
$$
立方体の六つの正方形面と一致します。平面描画ではその一つが外面になります。
## 非連結の場合
&&&cor 一般のplane graphのEuler公式 [05-cor-euler-plane-components]
$c$ 個の連結成分をもつ有限plane graphについて
$$
v-e+f=1+c.
$$
&&&
&&&prf [05-prf-euler-plane-components]
異なる連結成分を結ぶように、既存の辺と交差しない辺を $c-1$ 本加えて連結にできます。異なる成分を結ぶ辺はcycleを作らず、一つの面の内部にbridgeとして置かれるので面数は変わりません。
得られた連結plane graphは頂点数 $v$、辺数 $e+c-1$、面数 $f$ です。連結版のEuler公式から
$$
v-(e+c-1)+f=2.
$$
整理すると $v-e+f=1+c$。□
&&&
## simple planar graphの辺数上界
Euler公式だけでは $K_5$ の非平面性はまだ見えません。各面が少なくとも三辺に囲まれることを合わせます。
&&&thm planar graphの辺数評価 [05-thm-planar-edge-bound]
$v\ge3$ のsimple planar graph $G$ に対して
$$
e\le3v-6.
$$
&&&
&&&prf [05-prf-planar-edge-bound]
辺を追加して各成分を結んでもsimpleかつplanarに保てるため、$G$ を連結としてよいです。固定したplane描画を考えます。
simple graphにはloopも平行辺もないので、各面の境界次数は少なくとも3です。bridgeがある場合も、その辺は境界で往復しますが、$v\ge3$ の連結simple graphでは面境界全体の長さが2になることはありません。従って面次数の和から
$$
3f\le\sum_f\deg(f)=2e.
$$
Euler公式 $v-e+f=2$ より $f=2-v+e$。代入して
$$
3(2-v+e)\le2e,
$$
従って
$$
e\le3v-6.
$$
□
&&&
この証明の「各面次数は3以上」は、木 $P_3$ の外面次数4でも成立します。ただし $K_2$ では外面次数2となるため $v\ge3$ が必要です。
## $K_5$ は非平面
$K_5$ は
$$
v=5,\qquad e=\binom52=10
$$
です。もしplanarなら辺数評価により
$$
10=e\le3\cdot5-6=9
$$
でなければならず矛盾します。従って $K_5$ は非平面です。
## bipartite planar graphのより強い評価
二部グラフには奇cycleがなく、特に三角形がありません。そのため面は少なくとも四辺に囲まれます。
&&&thm bipartite planar graphの辺数評価 [05-thm-bipartite-planar-edge-bound]
$v\ge3$ のsimple bipartite planar graph $G$ に対して
$$
e\le2v-4.
$$
&&&
&&&prf [05-prf-bipartite-planar-edge-bound]
前と同様、連結なplane描画を考えてよいです。二部グラフのclosed walkの長さは偶数で、simple graphに長さ2のcycleはありません。従って辺をもつ各面の境界次数は少なくとも4です。木の場合は $e=v-1\le2v-4$ が $v\ge3$ で直接成り立つので、cycleをもつ場合を考えれば全ての面について
$$
4f\le2e.
$$
Euler公式から
$$
4(2-v+e)\le2e,
$$
ゆえに
$$
e\le2v-4.
$$
□
&&&
## $K_{3,3}$ は非平面
$K_{3,3}$ は二部グラフで
$$
v=6,\qquad e=3\cdot3=9.
$$
もしplanarなら
$$
9=e\le2\cdot6-4=8
$$
となり矛盾します。従って $K_{3,3}$ は非平面です。
$K_5$ と $K_{3,3}$ は平面性を妨げる二つの基本形です。辺数評価はこの二つを見抜きますが、すべての非平面グラフを見抜くわけではありません。辺を途中で分割して頂点を増やすと上界を満たすようになっても、非平面性は変わらないからです。これがKuratowskiの定理へつながります。
## 三角形分割と極大planar graph
&&&prop 三角形分割の辺数 [05-prop-planar-triangulation-count]
$v\ge3$ の連結simple plane graphで、すべての面の境界次数が3なら
$$
e=3v-6,\qquad f=2v-4.
$$
&&&
&&&prf [05-prf-planar-triangulation-count]
面次数の和から $3f=2e$。Euler公式 $v-e+f=2$ へ $f=2e/3$ を代入すると
$$
v-e+\frac{2e}{3}=2,
$$
従って $e=3v-6$。さらに
$$
f=\frac{2e}{3}=2v-4.
$$
□
&&&
辺をこれ以上交差なしに加えられない極大simple planar graphでは、適切な条件下で全ての面が三角形になります。従って上界 $3v-6$ は単なる粗い評価ではなく、実際に達成されます。
## 演習
&&&exc 多面体の未知数 [05-exc-planar-polyhedron]
ある連結plane graphが12頂点18辺をもつ。面数を求めよ。
&&&
&&&prf 解答 [05-prf-planar-polyhedron-answer]
Euler公式から
$$
12-18+f=2,
$$
従って $f=8$ です。外面も一つとして数えています。□
&&&
&&&exc 正多面体の可能性 [05-exc-planar-regular-degree]
連結simple plane graphで、各頂点の次数が5、各面の次数が3であるとする。頂点数、辺数、面数を求めよ。
&&&
&&&prf 解答 [05-prf-planar-regular-degree-answer]
握手補題と面次数の和から
$$
5v=2e,\qquad3f=2e.
$$
従って $v=2e/5,f=2e/3$。Euler公式へ代入すると
$$
\frac{2e}{5}-e+\frac{2e}{3}=2.
$$
左辺の係数は $(6-15+10)/15=1/15$ なので $e=30$。従って
$$
v=12,\qquad f=20.
$$
正二十面体のgraphに対応します。□
&&&
&&&exc $K_{2,n}$ の平面性 [05-exc-planar-k2n]
すべての $n\ge1$ に対して $K_{2,n}$ がplanarであることを、交差しない描き方を言葉で構成して示せ。辺数評価と矛盾しないことも確認せよ。
&&&
&&&prf 解答 [05-prf-planar-k2n-answer]
二頂点 $u,v$ を置き、その間を結ぶ、内部では互いに交わらない $n$ 本のarcを平行に描きます。第 $i$ のarcの内部に頂点 $w_i$ を一つ置き、そのarcを $uw_i$ と $w_iv$ の二辺に分けます。異なるarcは端点 $u,v$ 以外で交わらないので、これは $K_{2,n}$ のplane描画です。
$v=n+2,e=2n$ なので、二部planar上界は
$$
2n\le2(n+2)-4=2n
$$
と等号で成立します。□
&&&
&&&exc planar上界の逆は成り立たない [05-exc-planar-bound-not-converse]
$K_{3,3}$ の各辺を一度ずつ分割して新頂点を9個加えたグラフ $H$ を考える。$H$ が $e\le3v-6$ を満たすが非平面であることを示せ。
&&&
&&&prf 解答 [05-prf-planar-bound-not-converse-answer]
元の $K_{3,3}$ は6頂点9辺です。各辺を分割すると、一辺が二辺になるため
$$
v(H)=6+9=15,\qquad e(H)=18.
$$
確かに
$$
18\le3\cdot15-6=39.
$$
もし $H$ がplanarなら、各次数2の新頂点の近くで二本の辺を滑らかにつなぎ、その頂点を消すことで $K_{3,3}$ のplane描画が得られます。しかし $K_{3,3}$ は非平面なので矛盾です。従って $H$ は非平面です。辺数上界は必要条件であって十分条件ではありません。□
&&&
&&&exc triangle-free planar graph [05-exc-planar-triangle-free]
$v\ge3$ の連結simple planar graphが三角形を含まないなら
$$
e\le2v-4
$$
であることを示せ。二部性は仮定しない。
&&&
&&&prf 解答 [05-prf-planar-triangle-free-answer]
三角形を含まないため、各面境界の長さは3にはなれません。simple graphなので長さ1,2もなく、cycleを含む場合は各面次数が少なくとも4です。木なら $e=v-1\le2v-4$。
従ってcycleを含む場合は
$$
4f\le2e.
$$
Euler公式と同じ計算から $e\le2v-4$ を得ます。二部グラフでなくても、三角形がないことだけで証明に必要な面次数下界が得られます。□
&&&
&&&exc planar graphには低次数頂点がある [05-exc-planar-low-degree]
$v\ge3$ のsimple planar graphには次数5以下の頂点が存在することを示せ。
&&&
&&&prf 解答 [05-prf-planar-low-degree-answer]
すべての頂点の次数が6以上だと仮定すると、握手補題から
$$
2e=\sum_v\deg(v)\ge6v,
$$
従って $e\ge3v$ です。しかしplanar辺数上界は
$$
e\le3v-6<3v
$$
なので矛盾します。ゆえに少なくとも一頂点は次数5以下です。この事実が五色定理の帰納法の入口になります。□
&&&

5-1 平面グラフ

7-1 Eulerグラフとde Bruijn列

## flowがこれ以上増えないことを何で証明するか
値の大きなfeasible flowを見つけても、それがmaximumだとは限りません。source側とsink側を分けるcutを一つ示し、そのcutを横切る総容量がflow値と同じなら、それ以上送れないことが証明できます。
max-flow min-cut定理は、最大flow値と最小cut容量が必ず一致すると主張します。算法が成功時にflow、停止時に同じ値のcutを返すため、解と最適性証明書が同時に得られます。
## network cutと容量
&&&def $s$--$t$ cut [35-def-network-cut]
networkの頂点集合を
$$
V=S\sqcup T,\qquad s\in S,\quad t\in T
$$
と分けたものを $s$--$t$ cut（[[s-tカット]]）という。
$S$ から $T$ へ向くarc集合を $\delta^+(S)$、$T$ から $S$ へ向くarc集合を $\delta^-(S)$ と書く。cut容量を
$$
c(S,T)=\sum_{a\in\delta^+(S)}c(a)
$$
と定める。
&&&
逆向きarcの容量はcut容量へ入りません。sourceからsinkへ正味に送る量を妨げるのは、source側からsink側へ出るarcだからです。
&&&lemma cutを横切る正味flow [35-lem-net-flow-across-cut]
任意のfeasible flow $f$ と $s$--$t$ cut $(S,T)$ に対して
$$
|f|=
\sum_{a\in\delta^+(S)}f(a)
-
\sum_{a\in\delta^-(S)}f(a).
$$
&&&
&&&prf [35-prf-net-flow-across-cut]
$S$ の各頂点について「流出－流入」を足します。$S$ 内部のarcは、一方の頂点で流出、他方で流入として現れ相殺します。$S$ から $T$ へのarcは流出として一度、$T$ から $S$ へのarcは流入として一度残ります。
$S$ 内で保存則が課されないのはsource $s$ だけで、sinkは $T$ にあります。従って頂点ごとの左辺の和はsourceの正味流出 $|f|$ であり、右辺が表示したcut横断flowです。□
&&&
&&&thm cutによる弱双対性 [35-thm-flow-cut-weak-duality]
任意のfeasible flow $f$ と任意の $s$--$t$ cut $(S,T)$ に対して
$$
|f|\le c(S,T).
$$
&&&
&&&prf [35-prf-flow-cut-weak-duality]
前補題から
$$
|f|
=\sum_{\delta^+(S)}f(a)-\sum_{\delta^-(S)}f(a)
\le\sum_{\delta^+(S)}f(a)
\le\sum_{\delta^+(S)}c(a)
=c(S,T).
$$
第二項は非負flowを引いており、forward arcでは容量制約を使いました。□
&&&
従って任意のcutは全flowへの上界証明書です。問題はmaximum flowと同じ値をもつcutが必ず存在するかです。
## residual到達集合が等号cutを作る
feasible flow $f$ のresidual network $D_f$ で、source $s$ から到達できる頂点全体を $S$、残りを $T$ とします。residual $s$--$t$ pathがないなら $t\in T$ なので、これはcutです。
&&&lemma 停止時cutの飽和条件 [35-lem-terminal-cut-saturation]
$D_f$ に $s$--$t$ pathがないとし、$S$ を $s$ からresidualに到達可能な頂点集合とする。このとき
1. $S$ から $T$ への全original arc $a$ は $f(a)=c(a)$。
2. $T$ から $S$ への全original arc $a$ は $f(a)=0$。
&&&
&&&prf [35-prf-terminal-cut-saturation]
$S$ から $T$ へのoriginal arc $a:u\to v$ で $f(a)<c(a)$ なら、正容量のforward residual arc $a^+:u\to v$ があります。$u$ は到達可能なので $v$ も到達可能となり、$v\in T$ に反します。従って飽和しています。
$T$ から $S$ へのoriginal arc $a:v\to u$ で $f(a)>0$ なら、正容量のbackward residual arc $a^-:u\to v$ があります。$u\in S$ から $v$ へ到達でき、やはり矛盾です。従ってflowは0です。□
&&&
&&&cor 停止時flowとcutの等号 [35-cor-terminal-equality]
上の $f,(S,T)$ に対して
$$
|f|=c(S,T).
$$
&&&
&&&prf [35-prf-terminal-equality]
cut横断flowの式と前補題から
$$
|f|
=\sum_{\delta^+(S)}f(a)-\sum_{\delta^-(S)}f(a)
=\sum_{\delta^+(S)}c(a)-0
=c(S,T).
$$
□
&&&
## max-flow min-cut定理
&&&thm max-flow min-cut theorem [35-thm-max-flow-min-cut]
有限capacitated networkにおいて
$$
\max_f |f|=\min_{(S,T)}c(S,T).
$$
さらにfeasible flow $f$ について次は同値である。
1. $f$ はmaximum flowである。
2. residual network $D_f$ に $s$--$t$ pathがない。
3. ある $s$--$t$ cut $(S,T)$ が $|f|=c(S,T)$ を満たす。
&&&
&&&prf [35-prf-max-flow-min-cut]
2なら、residual到達集合から作ったcutが停止時等号を満たすので3です。
3なら、任意のfeasible flow $g$ に弱双対性を使って
$$
|g|\le c(S,T)=|f|
$$
となるため、$f$ はmaximumで1です。
1なら2を示します。augmenting pathがあればaugmentation lemmaにより値が真に大きいfeasible flowを作れ、maximum性に反します。従ってpathはありません。
少なくともzero flowはfeasibleです。Ford--Fulkersonが有限停止する整数・有理容量では上の構成が直接maximumとminimum cutを与えます。一般の実容量でも、feasible flow全体は有限次元の閉有界集合でflow値は連続なのでmaximumが存在し、1から2、2から3により同じ結論を得ます。従って最大値と最小値は一致します。□
&&&
実容量での「閉有界集合上の連続関数は最大を取る」は有限次元解析の結果です。算法的には次節のEdmonds--Karpを使えば、容量の算術性に依存せず有限回で等号cutへ到達します。
## Ford--Fulkersonの正当性とintegral max flow
&&&cor Ford--Fulkersonの最大性 [35-cor-ford-fulkerson-correctness]
Ford--Fulkerson算法が停止したとき、出力flowはmaximumであり、residual到達集合からminimum cutが得られる。
&&&
&&&prf [35-prf-ford-fulkerson-correctness]
停止条件はresidual $s$--$t$ pathがないことです。max-flow min-cut定理の同値条件によりflowはmaximumで、到達集合のcut容量はその値に等しいためminimumです。□
&&&
&&&cor integral flow theorem [35-cor-integral-flow]
全容量が非負整数なら、整数値だけをもつmaximum flowと整数容量のminimum cutが存在する。
&&&
&&&prf [35-prf-integral-flow]
「ネットワーク流」で、整数容量に対するFord--Fulkersonは有限停止し、全反復でflowのintegralityを保つことを証明しました。停止flowは前系によりmaximumです。cut容量は整数容量の和なので整数です。□
&&&
## Edmonds--Karp算法
augmenting pathを任意に選ばず、residual graphでarc数最短のpathをBFSで選ぶFord--FulkersonをEdmonds--Karp算法と呼びます。
&&&lemma residual最短距離は減少しない [35-lem-edmonds-karp-distance]
一回の最短augmenting path更新の前後で、sourceから各頂点へのresidual最短距離は減少しない。
&&&
&&&prf [35-prf-edmonds-karp-distance]
更新前後の距離を $d,d'$ とします。$d'(v)<d(v)$ となる頂点があると仮定し、新しいresidual graphの最短path上で最初にこの不等式が起こる頂点を $v$、その直前を $u$ とします。従って
$$
d'(u)\ge d(u),\qquad d'(v)=d'(u)+1.
$$
arc $u\to v$ が更新前にもresidualなら
$$
d(v)\le d(u)+1\le d'(u)+1=d'(v),
$$
となり矛盾です。従って $u\to v$ は更新により新しく生じたbackward residual arcです。つまり更新に使った最短pathは逆向きarc $v\to u$ を含み、
$$
d(u)=d(v)+1
$$
です。
最初の不等式と合わせると
$$
d'(v)=d'(u)+1\ge d(u)+1=d(v)+2,
$$
これは $d'(v)<d(v)$ に反します。従って距離は減少しません。□
&&&
&&&thm Edmonds--Karpの計算量 [35-thm-edmonds-karp-complexity]
Edmonds--Karp算法は容量が任意の非負実数でも有限停止し、隣接listで
$$
O(|V||A|^2)
$$
時間でmaximum flowを求める。
&&&
&&&prf [35-prf-edmonds-karp-complexity]
各augmentationでbottleneck residual arcが少なくとも一本飽和し、residual graphから消えます。このarc $u\to v$ をその反復へchargeします。最短path上にあるので
$$
d(v)=d(u)+1.
$$
同じlabel付きresidual arc $u\to v$ が後に再び現れて、再度飽和chargeされるには、その間に逆向き $v\to u$ を通るaugmentationが必要です。その時点の距離を $\widetilde d$ とすると
$$
\widetilde d(u)=\widetilde d(v)+1.
$$
距離非減少性から $\widetilde d(v)\ge d(v)=d(u)+1$ なので
$$
\widetilde d(u)\ge d(u)+2.
$$
従って同じ向きのarcが再chargeされるたび、そのtailの距離は少なくとも2増えます。有限距離は高々 $|V|-1$ なので、各向きは $O(|V|)$ 回しかchargeされません。
original arc一つはforward・backwardの二つのlabel付きresidual向きを生むため、charge総数、従ってaugmentation回数は $O(|V||A|)$ です。一回のBFSと更新は $O(|A|)$ 時間なので、全体は $O(|V||A|^2)$ です。
有限回でresidual pathがなくなり、max-flow min-cut定理により出力はmaximumです。□
&&&
## directed edge版Mengerの定理
&&&def arc-disjoint pathとarc separator [35-def-arc-disjoint-separator]
有向グラフで、arcを共有しない複数の $s$--$t$ pathを[[弧素な道|arc-disjoint]]という。
削除すると $s$ から $t$ への有向pathがなくなるarc集合を $s$--$t$ [[弧分離集合|arc separator]]という。
&&&
&&&thm directed edge Menger theorem [35-thm-directed-edge-menger]
有限有向グラフで、$s$ から $t$ へのarc-disjoint pathの最大本数は、$s$--$t$ arc separatorの最小arc数に等しい。
&&&
&&&prf [35-prf-directed-edge-menger]
各arc容量を1とするnetworkを作ります。integral flow theoremによりintegral maximum flowがあります。各arc flowは0または1で、flow decompositionからcycleを除けば、値 $k$ のflowは $k$ 本の $s$--$t$ pathへ分解されます。容量1なのでpathはarcを共有しません。逆に $k$ 本のarc-disjoint pathへ各1流せば値 $k$ のflowです。従ってmaximum flow値はarc-disjoint path最大数です。
任意の $s$--$t$ cut $\delta^+(S)$ を削除すれば、$S$ 内の $s$ から $T$ 内の $t$ へ進めないためarc separatorです。容量1なのでcut容量はarc数です。
逆にarc separator $F$ を削除したグラフで $s$ から到達可能な頂点集合を $S$ とします。$t$ は到達不能なので $(S,V\setminus S)$ はcutです。元のグラフで $S$ から外へ出るarcは全て $F$ に属さなければならず、
$$
|\delta^+(S)|\le|F|.
$$
従ってminimum cut容量はminimum separator数と一致します。max-flow min-cut定理から三つの量が等しいです。□
&&&
## Hallの定理をflowで証明する
二部グラフ $G=(X\sqcup Y,E)$ から、「ネットワーク流」のmatching networkを作ります。今回は中間arc $x\to y$ の容量を
$$
M=|X|+1
$$
とし、$s\to x$ と $y\to t$ は容量1とします。
&&&cor Hallの定理のflow証明 [35-cor-hall-from-flow]
全ての $A\subseteq X$ で $|N(A)|\ge|A|$ なら、$X$ を飽和するmatchingが存在する。
&&&
&&&prf [35-prf-hall-from-flow]
任意の $s$--$t$ cut $(S,T)$ を考えます。中間arc $x\to y$ が一つでも $S$ から $T$ へ出れば、cut容量は少なくとも $M=|X|+1>|X|$ です。
そのような中間arcがない場合、$A=S\cap X$ の全近傍は $S\cap Y$ に含まれます。cut容量には、$s$ から $X\setminus A$ への $|X|-|A|$ 本と、$S\cap Y$ から $t$ への $|S\cap Y|$ 本が寄与します。従ってHall条件から
$$
c(S,T)
=|X|-|A|+|S\cap Y|
\ge |X|-|A|+|N(A)|
\ge |X|.
$$
一方、cut $S=\{s\}$ の容量は $|X|$ です。従ってminimum cut値は $|X|$、max-flow min-cut定理から値 $|X|$ のmaximum flowがあります。容量が整数なのでintegral flowを選べます。このflowでは $s\to x$ と $y\to t$ の容量が1であるため、各中間arc $x\to y$ のflowも実際には0または1です。positive-flowの中間arcを辺として選ぶと、一つの $x$ からも一つの $y$ からも高々一本しか選ばれません。したがって「ネットワーク流」と同じ対応により大きさ $|X|$ のmatching、すなわち $X$ を飽和するmatchingを得ます。□
&&&
## 演習
&&&exc cut上界を計算する [35-exc-compute-cut-bound]
networkにarc $s\to a,s\to b,a\to b,a\to t,b\to t$ があり、容量が順に $4,3,2,3,4$ である。cut $S=\{s,a\}$ の容量を求め、全flow値への上界を書け。
&&&
&&&prf 解答 [35-prf-compute-cut-bound-answer]
$S$ から外へ出るarcは $s\to b$、$a\to b$、$a\to t$ で、容量は3,2,3です。従って
$$
c(S,T)=3+2+3=8.
$$
弱双対性により任意のfeasible flowは値8以下です。$b\to a$ のような逆向きarcがあってもcut容量には入りません。□
&&&
&&&exc 等号条件を確認する [35-exc-cut-equality-conditions]
feasible flow $f$ とcut $(S,T)$ が $|f|=c(S,T)$ を満たすなら、全ての $S\to T$ arcが飽和し、全ての $T\to S$ arcのflowが0であることを示せ。
&&&
&&&prf 解答 [35-prf-cut-equality-conditions]
cut横断式から
$$
c(S,T)-|f|
=\sum_{\delta^+(S)}(c(a)-f(a))
+\sum_{\delta^-(S)}f(a).
$$
右辺の各項は非負です。左辺が0なら全項が0でなければならず、forward cut arcでは $f(a)=c(a)$、backward cut arcでは $f(a)=0$ です。□
&&&
&&&exc maximum flowとminimum cutを作る [35-exc-small-max-flow]
「ネットワーク流」の四頂点容量1 network
$$
s\to a,\ s\to b,\ a\to b,\ a\to t,\ b\to t
$$
についてmaximum flow値とminimum cutを一つ求めよ。
&&&
&&&prf 解答 [35-prf-small-max-flow-answer]
path $s\to a\to t$ と $s\to b\to t$ へ各1流せるので値2です。cut $S=\{s\}$ の容量は $c(s,a)+c(s,b)=2$ です。弱双対性から値は2を超えず、flowとcutが同値2なので双方最適です。□
&&&
&&&exc integral flowからpathを取り出す [35-exc-integral-paths]
全arc容量1のnetworkで値3のintegral flowがある。positive-flow部分にcycleが一つ含まれていても、三本のarc-disjoint $s$--$t$ pathを得られる理由を説明せよ。
&&&
&&&prf 解答 [35-prf-integral-paths-answer]
flow decompositionにより、flowは $s$--$t$ path flowとcycle flowへ分かれます。cycle flowはflow値へ寄与しないため除いても値3のままです。容量1かつintegralなので各path係数は1で、係数和3から三本のpathがあります。同じarcを二pathが使えばそのarc flowが2になり容量1に反するため、pathはarc-disjointです。□
&&&
&&&exc Mengerを小さい有向グラフへ使う [35-exc-small-menger]
arc
$$
s\to a,\ s\to b,\ a\to c,\ b\to c,\ a\to t,\ c\to t,\ b\to t
$$
をもつ有向グラフでarc-disjoint $s$--$t$ pathの最大本数とminimum arc separatorを求めよ。
&&&
&&&prf 解答 [35-prf-small-menger-answer]
path $s\to a\to t$ と $s\to b\to t$ はarc-disjointなので少なくとも2本です。sourceから出るarcは $s\to a,s\to b$ の二本だけで、これらを削除すれば全pathが消えます。従ってseparatorは2本以下で、Mengerの定理または直接の上界から最大path数も2以下です。よって両者とも2です。□
&&&
&&&exc Hall cutを具体化する [35-exc-hall-cut]
二部グラフで $X=\{a,b,c\}$、$N(a)=N(b)=N(c)=\{1,2\}$ とする。matching networkのminimum cutを一つ作り、その容量が2であることから全員を飽和できないことを示せ。
&&&
&&&prf 解答 [35-prf-hall-cut-answer]
$S=\{s,a,b,c,1,2\}$、$T=\{t\}$ とします。全中間arcは $S$ 内部にあり、cutを出るのは $1\to t,2\to t$ の二本だけです。従って容量は2です。
max-flow値は2以下であり、integral flowとmatchingの対応からmatching辺数も2以下です。$|X|=3$ なので全員を飽和できません。これはHall障害 $|N(X)|=2<3$ と同じcut証明です。□
&&&
## 本章で得たもの
任意のflowは任意のcut容量以下です。残余pathがなくなったとき、sourceからの到達集合が「forwardは全て飽和、backwardは全て0」のcutを作り、flow値とcut容量が一致します。これによりFord--Fulkersonの最大性、integer flow、Edmonds--Karp、Menger、Hallが一つの原理から導かれました。


4-2 最大流最小切断定理

7-2 Hamiltonグラフ

## networkの骨格を一つ選ぶ
連結グラフには、頂点間の到達可能性を保つために不要な辺が含まれていることがあります。cycle上の一本を除いても連結性は失われません。余分な辺を削り続けると、全頂点を結びながらcycleをもたない骨格が残ります。これがspanning treeです。
骨格を選んだ後、元の辺は二種類に分かれます。
- 木に入れた辺を一本除くと、頂点集合が二つへ分かれる。
- 木に入れなかった辺を一本加えると、ただ一つのcycleが生じる。
このcutとcycleは互いに対応し、「どの辺とどの辺を交換すれば別の骨格になるか」を完全に決めます。
## spanning treeとspanning forest
&&&def spanning treeとspanning forest [28-def-spanning-tree-forest]
グラフ $G$ の全頂点を含む部分グラフ $T$ が木であるとき、$T$ を $G$ の[[全域木|spanning tree]]（全域木）という。
$G$ の各連結成分においてspanning treeを一つずつ選び、それらを合わせた部分グラフを[[全域森|spanning forest]]（全域森）という。
&&&
spanningは「全頂点を含む」という意味であり、全辺を含むという意味ではありません。連結グラフだけがspanning treeをもちます。
&&&thm spanning treeの存在 [28-thm-spanning-tree-existence]
有限グラフ $G$ がspanning treeをもつための必要十分条件は、$G$ が連結であることである。
&&&
&&&prf [28-prf-spanning-tree-existence]
spanning tree $T$ があれば、$T$ 内のpathは $G$ のpathでもあるため、$G$ は連結です。
逆に $G$ が連結とします。$G$ の辺をすべて残した状態から、cycleがある限りそのcycle上の辺を一本削除します。cycle上の辺 $e=uv$ を削除しても、cycleの残りが $u$ から $v$ への別のpathを与えるため、任意のwalkで $e$ を使う箇所をそのpathへ置き換えられます。従って連結性は保たれます。
辺数は有限なので操作は停止します。停止時の部分グラフは全頂点を含み、連結でcycleをもちません。従って木であり、$G$ のspanning treeです。□
&&&
「幅優先探索と深さ優先探索」のBFS・DFS親辺もspanning treeを構成します。上の証明は「cycleを消す」削除型、探索は「新頂点へ届く辺を加える」追加型です。
&&&thm spanning treeの極小・極大特徴づけ [28-thm-spanning-tree-minmax]
連結グラフ $G$ の全頂点を含む部分グラフ $H$ について、次は同値である。
1. $H$ はspanning treeである。
2. $H$ は連結で、どの辺を一本削除しても非連結になる。
3. $H$ はcycleをもたず、$G$ の任意の辺を新たに一本加えるとcycleができる。
&&&
&&&prf [28-prf-spanning-tree-minmax]
1から2を示します。木の任意の辺はbridgeです。実際、辺 $uv$ を除いても $u,v$ 間のpathが残れば、そのpathと $uv$ がcycleを作ります。従ってどの辺を削除しても非連結です。
1から3を示します。木はcycleをもちません。$H$ にない $G$ の辺 $e=uv$ を加えると、木内の唯一の $u$--$v$ pathと $e$ がcycleを作ります。
2から1を示します。$H$ にcycleがあれば、その上の辺を一本削除しても連結性が保たれ、2に反します。従って $H$ は連結でcycleをもたない木です。
3から1を示します。もし $H$ が非連結なら、$G$ は連結なので異なる $H$-成分を結ぶ辺 $e\in E(G)\setminus E(H)$ があります。この辺を加えても異なる成分を一本で結ぶだけでcycleはできず、3に反します。従って $H$ は連結であり、cycleをもたないので木です。□
&&&
ここで「極小連結」は辺の包含について極小、「極大acyclic」は辺の包含について極大という意味です。辺数が最少・最大という数値的主張だけではありません。
## 木に一本足すと生じる基本cycle
以後、$G$ を連結グラフ、$T$ をそのspanning treeとします。
&&&def fundamental cycle [28-def-fundamental-cycle]
$e=uv\in E(G)\setminus E(T)$ に対し、$T$ 内の唯一の $u$--$v$ pathと $e$ からなるcycleを、$T$ に関する $e$ の[[基本閉路|fundamental cycle]]（基本cycle）といい $C_T(e)$ と書く。
&&&
&&&prop 基本cycleの一意性 [28-prop-fundamental-cycle-unique]
$T+e$ に含まれるcycleは $C_T(e)$ ただ一つである。
&&&
&&&prf [28-prf-fundamental-cycle-unique]
$T$ 自身はcycleをもたないため、$T+e$ のcycleは新しい辺 $e=uv$ を含まなければなりません。$e$ をcycleから除くと、残りは $T$ 内の $u$--$v$ pathです。木内のpathは一意なので、それは $C_T(e)$ を定義したpathに限られます。従ってcycleは一つだけです。□
&&&
&&&thm cycle交換条件 [28-thm-cycle-exchange]
$e\in E(G)\setminus E(T)$ と $f\in E(T)$ に対して
$$
T+e-f
$$
がspanning treeであるための必要十分条件は
$$
f\in E(C_T(e))
$$
である。
&&&
&&&prf [28-prf-cycle-exchange]
$f\in C_T(e)$ とします。$T+e$ の唯一のcycleは $C_T(e)$ なので、その上の $f$ を除くとcycleがなくなります。またcycleから一本を除いた残りにより $f$ の両端は依然として結ばれているため、$T+e-f$ は連結です。全頂点を含む連結acyclic graphなのでspanning treeです。
逆に $f\notin C_T(e)$ とします。$T+e$ にある唯一のcycle $C_T(e)$ は $f$ を含まないため、$f$ を除いてもそのcycleが残ります。従って $T+e-f$ は木ではありません。□
&&&
一本の非木辺を入れたいなら、交換相手は基本cycle上から、しかもそこからならどの木辺を選んでもよいと分かります。
## 木から一本引くと生じる基本cut
頂点集合 $A\subseteq V(G)$ に対し、ちょうど一端だけが $A$ に属する辺全体を
$$
\delta_G(A)=\{xy\in E(G)\mid x\in A, y\notin A\}
$$
と書きます。$\delta_G(A)=\delta_G(V\setminus A)$ です。
&&&def cutとfundamental cut [28-def-fundamental-cut]
空でない真部分集合 $A\subsetneq V(G)$ に対する辺集合 $\delta_G(A)$ を[[カット (グラフ理論)|cut]]という。
木辺 $f\in E(T)$ を除くと $T-f$ はちょうど二つの連結成分をもつ。その一方の頂点集合を $A_f$ としたとき
$$
D_T(f)=\delta_G(A_f)
$$
を $T$ に関する $f$ の[[基本カット|fundamental cut]]（基本cut）という。
&&&
どちらの成分を $A_f$ と選んでもcutは同じです。$f$ 自身は $D_T(f)$ に属します。
&&&lemma 木辺削除後は二成分 [28-lem-tree-edge-two-components]
木 $T$ の辺 $f=xy$ を削除すると、$T-f$ はちょうど二つの連結成分をもち、$x,y$ は異なる成分に属する。
&&&
&&&prf [28-prf-tree-edge-two-components]
$x,y$ が $T-f$ でも同じ成分にあれば、$f$ を使わない $x$--$y$ pathがあり、それと $f$ がcycleを作るので矛盾です。
任意の頂点 $v$ を取ります。$T$ 内の $v$--$x$ pathが $f$ を使わなければ $v$ は $x$ の成分に属します。使うなら、そのpathは $f=xy$ を一度通り、$v$ から $y$ までの部分は $f$ を使わないので $v$ は $y$ の成分に属します。従って全頂点はこの二成分のどちらかに入り、成分はちょうど二つです。□
&&&
&&&thm cut交換条件 [28-thm-cut-exchange]
$f\in E(T)$ と $e\in E(G)\setminus E(T)$ に対して
$$
T-f+e
$$
がspanning treeであるための必要十分条件は
$$
e\in D_T(f)
$$
である。
&&&
&&&prf [28-prf-cut-exchange]
$T-f$ の二成分を $A_f$ とその補集合とします。$e\in D_T(f)$ なら $e$ は二成分を結ぶので、$T-f+e$ は連結です。その辺数は $|V(T)|-1$ のままなので、木の特徴づけによりspanning treeです。
$e\notin D_T(f)$ なら $e$ の両端は同じ成分にあります。従って他方の成分との間に辺は加わらず、$T-f+e$ は非連結です。ゆえにspanning treeではありません。□
&&&
## cycleとcutの双対的対応
二つの交換条件は同じ事実を別方向から見ています。
&&&thm 基本cycle・基本cutの対応 [28-thm-cycle-cut-incidence]
$e\in E(G)\setminus E(T)$、$f\in E(T)$ に対し
$$
f\in C_T(e)\quad\Longleftrightarrow\quad e\in D_T(f).
$$
&&&
&&&prf [28-prf-cycle-cut-incidence]
$f\in C_T(e)$ ならcycle交換条件により $T+e-f$ はspanning treeです。辺の加減は可換なので $T-f+e$ もspanning treeであり、cut交換条件から $e\in D_T(f)$ です。
逆に $e\in D_T(f)$ ならcut交換条件から $T-f+e$ はspanning treeです。従って $T+e-f$ もspanning treeで、cycle交換条件から $f\in C_T(e)$ です。□
&&&
直接には、$f$ を除いて分かれる二側を $e$ が横切ることと、$e$ の両端を結ぶ木内pathが $f$ を通ることが同値です。
## 二つのspanning treeを近づける
交換法則は、一つのspanning treeから別のspanning treeへ一辺ずつ移れることも示します。
&&&thm spanning treeの対称交換 [28-thm-symmetric-tree-exchange]
同じ連結グラフ $G$ の二つのspanning treeを $T_1,T_2$ とする。任意の
$$
e\in E(T_1)\setminus E(T_2)
$$
に対し、ある
$$
f\in E(T_2)\setminus E(T_1)
$$
が存在して、$T_1-e+f$ と $T_2-f+e$ はともにspanning treeになる。
&&&
&&&prf [28-prf-symmetric-tree-exchange]
$T_1-e$ の二成分の頂点集合を $A$ と $V\setminus A$ とします。$e$ の両端は異なる側にあります。
$T_2+e$ の基本cycle $C_{T_2}(e)$ を考えます。このcycleから $e$ を除いた $T_2$ 内のpathは、$e$ の一端から他端へ進むのでcut $\delta_G(A)$ を少なくとも一本横切ります。その横切る辺を $f$ とします。
$T_1$ では $e$ が二側を結ぶ唯一の木辺です。従って $f\ne e$ が $T_1$ にも属していれば、$T_1-e$ の二成分を $f$ が結んでしまい矛盾です。よって $f\in E(T_2)\setminus E(T_1)$ です。
$f$ は $T_1-e$ の二成分を結ぶので、cut交換条件から $T_1-e+f$ はspanning treeです。また $f$ は $C_{T_2}(e)$ 上にあるので、cycle交換条件から $T_2+e-f$ もspanning treeです。□
&&&
&&&cor spanning tree交換グラフの連結性 [28-cor-tree-exchange-graph-connected]
$G$ のspanning treeを頂点とし、一辺を交換して移り合える二つを隣接させたグラフは連結である。
&&&
&&&prf [28-prf-tree-exchange-graph-connected]
二つのspanning tree $T,T'$ を取ります。$T=T'$ なら何もする必要はありません。異なるなら $e\in E(T)\setminus E(T')$ を一つ選びます。対称交換定理により、ある $f\in E(T')\setminus E(T)$ と交換して
$$
T_1=T-e+f
$$
をspanning treeにできます。この交換で $T'$ と共通する辺が一本増えます。
異なる辺は有限本なので、この操作を繰り返すと有限回で $T'$ に到達します。各一歩が一辺交換なので、交換グラフ内のpathが得られます。□
&&&
## 具体例――四角形に対角線を入れる
頂点 $1,2,3,4$ と辺
$$
12,23,34,41,13
$$
をもつグラフを考え、spanning tree
$$
T=\{12,23,34\}
$$
を選びます。
非木辺 $41$ の基本cycleは
$$
C_T(41)=\{41,12,23,34\},
$$
非木辺 $13$ の基本cycleは
$$
C_T(13)=\{13,12,23\}
$$
です。従って13を追加するとき交換できる木辺は12または23であり、34を除いてもcycle $1,2,3,1$ が残るため木にはなりません。
木辺23を除くと成分は $\{1,2\}$ と $\{3,4\}$ です。従って
$$
D_T(23)=\{23,41,13\}.
$$
実際、23を13または41と交換すればspanning treeになります。対応定理により
$$
23\in C_T(13),\quad 13\in D_T(23)
$$
が同時に成り立ちます。
## 重みを入れる前の交換原理
各辺に長さ・費用・危険度などの重みが付くと、spanning treeの中で重み和が最小のものを探したくなります。交換定理から、候補木 $T$ にない辺 $e$ を入れるとき、削除できるのは $C_T(e)$ 上の辺だけだと分かります。
もしそのcycle上に $e$ より重い木辺 $f$ があれば
$$
w(T+e-f)=w(T)+w(e)-w(f)<w(T)
$$
となり、$T$ は最小ではありません。逆にcutを横切る最軽量辺は、適切な交換によって最小木へ安全に取り込めます。
## 演習
&&&exc cycle削除でspanning treeを作る [28-exc-delete-cycles]
完全グラフ $K_4$ の辺集合
$$
\{12,13,14,23,24,34\}
$$
からcycle上の辺を順に削除し、spanning treeを一つ作れ。各削除後も連結であることを確認せよ。
&&&
&&&prf 解答 [28-prf-delete-cycles-answer]
三角形 $1,2,3,1$ から辺13を削除します。残る辺は $12,14,23,24,34$ で、例えば1から2を経て3へ行け、4へは14で行けるので連結です。
残るcycle $1,2,4,1$ から24を削除します。辺は $12,14,23,34$ で、path $2,1,4,3,2$ が全頂点を結ぶので連結です。
この四辺にはcycle $1,2,3,4,1$ があるので34を削除します。残る
$$
\{12,14,23\}
$$
は全4頂点を含み、1を中心に2,4へ、2を経て3へ到達できる連結グラフです。3辺しかなくcycleをもたないのでspanning treeです。□
&&&
&&&exc 基本cycleを全て求める [28-exc-fundamental-cycles]
本文の四角形と対角線のグラフで、別のspanning tree
$$
T'=\{12,13,14\}
$$
を選ぶ。各非木辺23,34,41の基本cycleを求めよ。ただし41は辺14と同じ無向辺なので、非木辺の一覧をまず訂正せよ。
&&&
&&&prf 解答 [28-prf-fundamental-cycles-answer]
無向辺41は14と同じで既に $T'$ に入っています。従って非木辺は23と34だけです。
23の両端を結ぶ $T'$ 内pathは $2,1,3$ なので
$$
C_{T'}(23)=\{23,12,13\}.
$$
34の両端を結ぶpathは $3,1,4$ なので
$$
C_{T'}(34)=\{34,13,14\}.
$$
入力の辺を無向か有向か確認し、同じ辺を二重に数えないことが重要です。□
&&&
&&&exc 基本cutを全て求める [28-exc-fundamental-cuts]
同じ $T'=\{12,13,14\}$ について、各木辺12,13,14のfundamental cutを求めよ。
&&&
&&&prf 解答 [28-prf-fundamental-cuts-answer]
12を除くと $\{2\}$ と $\{1,3,4\}$ に分かれます。元のグラフで2から外へ出る辺は12,23なので
$$
D_{T'}(12)=\{12,23\}.
$$
同様に13を除くと $\{3\}$ が分かれ、3に接続する元の辺は13,23,34なので
$$
D_{T'}(13)=\{13,23,34\}.
$$
14を除くと $\{4\}$ が分かれ、接続辺は14,34なので
$$
D_{T'}(14)=\{14,34\}.
$$
例えば $13\in C_{T'}(23)$ と $23\in D_{T'}(13)$ が対応しています。□
&&&
&&&exc 交換できない辺を説明する [28-exc-invalid-exchange]
本文の $T=\{12,23,34\}$ に非木辺13を加え、木辺34を除いたグラフがspanning treeでないことを、cycleとcutの二通りで説明せよ。
&&&
&&&prf 解答 [28-prf-invalid-exchange-answer]
cycle側では
$$
C_T(13)=\{13,12,23\}
$$
であり34を含みません。従って13を加えて34を除いてもcycle $1,2,3,1$ が残ります。
cut側では、$T-34$ の成分は $\{1,2,3\}$ と $\{4\}$ です。辺13の両端はともに前者にあるため、このcutを横切りません。従って13を加えても頂点4は切り離されたままです。実際、得られるグラフは一方にcycleをもちながら非連結です。□
&&&
&&&exc 二つの木を対称交換する [28-exc-symmetric-exchange]
四角形と対角線のグラフで
$$
T_1=\{12,23,34\},\qquad T_2=\{12,14,34\}
$$
とする。$e=23\in T_1\setminus T_2$ に対して対称交換定理の $f$ を一つ求め、交換後の二つの木を書け。
&&&
&&&prf 解答 [28-prf-symmetric-exchange-answer]
$T_1-23$ の成分は $\{1,2\}$ と $\{3,4\}$ です。$T_2$ で23の両端2,3を結ぶpathは
$$
2,1,4,3
$$
なので、$T_2+23$ の基本cycleは $23,12,14,34$ です。このpathで二成分を横切る辺として $f=14$ を選べます。
交換後は
$$
T_1-23+14=\{12,14,34\},
$$
$$
T_2-14+23=\{12,23,34\}.
$$
この例では二つの木がそのまま入れ替わります。どちらも連結な3辺グラフなのでspanning treeです。□
&&&
&&&exc bridgeと全域木 [28-exc-bridge-in-every-tree]
連結グラフ $G$ の辺 $e$ について、次が同値であることを示せ。
1. $e$ はbridgeである。
2. $e$ は $G$ のすべてのspanning treeに含まれる。
3. あるspanning tree $T$ で $D_T(e)=\{e\}$ となる。
&&&
&&&prf 解答 [28-prf-bridge-in-every-tree-answer]
1から2。$e$ を含まないspanning treeがあれば、その木内で $e$ の両端を結ぶpathがあり、$G-e$ でも両端がつながります。spanning treeは全頂点を結ぶので $G-e$ も連結となり、$e$ がbridgeであることに反します。
2から3。spanning tree $T$ を一つ取ると2により $e\in T$ です。$D_T(e)$ に別の辺 $f$ があれば、cut交換条件により $T-e+f$ は $e$ を含まないspanning treeとなり2に反します。従って $D_T(e)=\{e\}$ です。
3から1。$T-e$ の二成分間を結ぶ $G$ の辺は $D_T(e)$ の辺そのものです。それが $e$ だけなら、$G-e$ では二成分を結ぶ辺がなく非連結です。従って $e$ はbridgeです。□
&&&
## 本章で得たもの
spanning treeは極小な連結骨格であると同時に、極大なacyclic部分グラフです。非木辺を加えると一意なfundamental cycle、木辺を除くと一意な二分割に対応するfundamental cutが生じます。そして
$$
f\in C_T(e)\Longleftrightarrow e\in D_T(f)
$$
が交換可能性を二方向から記述します。


2-2 全域木と切断・閉路の性質

## 一人分を増やすには既存の割当を動かす
現在のmatchingに未割当の学生 $a$ がいるとします。$a$ が希望する研究室1は学生 $b$ に割当済みでも、$b$ を空いている研究室2へ移せるなら
$$
a-1-b-2
$$
という交互の鎖に沿って割当を反転できます。辺 $a1,b2$ を採用し、辺 $1b$ を外せば、matchingの辺数が一つ増えます。
この局所的な組替えが、「これ以上増やせない」ことを判定する完全な基準になります。maximum matchingであることとaugmenting pathが存在しないことが同値だというBergeの補題を証明します。
## maximalとmaximumを区別する
&&&def maximal matchingとmaximum matching [32-def-maximal-maximum-matching]
matching $M$ が[[極大マッチング|maximal]]であるとは、$M$ に新しい辺を一本加えてより大きなmatchingにできないことをいう。
matching $M$ が[[最大マッチング|maximum]]であるとは、$G$ の任意のmatching $N$ に対して
$$
|M|\ge|N|
$$
となることをいう。maximum matchingの辺数を[[マッチング数|matching number]]といい $\nu(G)$ と書く。
&&&
maximumならmaximalですが、逆は偽です。四頂点path $1-2-3-4$ で $M=\{23\}$ は、端点を共有しない辺を追加できないのでmaximalです。しかし $\{12,34\}$ は二辺のmatchingなので、$M$ はmaximumではありません。
## alternating pathとaugmenting path
&&&def alternating pathとaugmenting path [32-def-alternating-augmenting-path]
matching $M$ に対し、matchingに属さない辺と属する辺が交互に現れるpathを $M$-[[交互路|alternating path]]という。
両端が $M$ に飽和されておらず、最初と最後の辺が $M$ に属さない $M$-alternating pathを $M$-[[増加路|augmenting path]]という。
&&&
augmenting pathの辺数は奇数で、非matching辺がmatching辺より一つ多くなります。二集合 $A,B$ のsymmetric differenceを
$$
A\triangle B=(A\setminus B)\cup(B\setminus A)
$$
と書きます。$M\triangle E(P)$ は、path上のmatching辺を外し、非matching辺を入れる操作です。
&&&lemma augmenting pathによる増加 [32-lem-augmenting-flip]
$P$ が $M$-augmenting pathなら
$$
M'=M\triangle E(P)
$$
はmatchingであり、$|M'|=|M|+1$ である。
&&&
&&&prf [32-prf-augmenting-flip]
$P$ の内部頂点では、path上の二辺の一方が $M$ に属し、他方が属しません。反転後もその二辺のうち一方だけが選ばれます。pathの両端は元の $M$ で未飽和であり、反転後は最初または最後の非matching辺一本だけに接続します。
path外では $M$ を変えません。path内部の頂点がpath外の $M$-辺にも接続することはありません。もしあれば、内部頂点はpath上の $M$-辺と合わせて二本のmatching辺に接続するからです。従って $M'$ はmatchingです。
$P$ 上では非matching辺がmatching辺より一本多いので、反転により辺数は1増えます。□
&&&
## 二つのmatchingの差はpathと偶cycleに分かれる
&&&lemma matchingのsymmetric difference分解 [32-lem-matching-symmetric-difference]
二つのmatching $M,N$ に対し、辺集合 $M\triangle N$ が誘導する部分グラフの各非孤立連結成分は、次のいずれかである。
1. $M$ と $N$ の辺が交互に並ぶpath。
2. $M$ と $N$ の辺が交互に並ぶ偶数長cycle。
特に各成分で、$M$-辺数と $N$-辺数の差の絶対値は高々1である。
&&&
&&&prf [32-prf-matching-symmetric-difference]
各頂点には $M$ の辺が高々一本、$N$ の辺が高々一本接続します。従って $M\triangle N$ 内の次数は高々2です。有限連結グラフで全頂点次数が高々2なら、非孤立成分はpathまたはcycleです。
同じmatchingの二辺は端点を共有しないため、成分内で隣り合う二辺がともに $M$、またはともに $N$ に属することはありません。従って辺は交互に並びます。cycleでは交互に出発種類へ戻るため長さは偶数で、両matchingの辺数は等しいです。pathでは両端の辺種類が同じならその種類が一本多く、異なれば同数です。□
&&&
## Bergeの補題
&&&thm Bergeの補題 [32-thm-berge]
有限グラフ $G$ のmatching $M$ がmaximumであるための必要十分条件は、$M$-augmenting pathが存在しないことである。
&&&
&&&prf [32-prf-berge]
$M$-augmenting pathがあれば、反転補題により辺数が $|M|+1$ のmatchingを作れるので、$M$ はmaximumではありません。
逆に $M$ がmaximumでないとします。$|N|>|M|$ を満たすmatching $N$ を取ります。$M\triangle N$ を前補題によりpathと偶cycleへ分解します。
全成分を合わせると $N$-辺が $M$-辺より多いので、少なくとも一成分では $N$-辺が $M$-辺より多くなります。cycleでは同数で、pathで差は高々1なので、その成分は最初と最後がともに $N$-辺であるalternating pathです。
このpathの両端には $M$-辺が接続しません。もしpath外に $M$-辺があれば、その辺は $N$ に属さないため $M\triangle N$ に入り、同じ成分のpathをさらに延長するからです。従って両端は $M$ で未飽和で、このpathは $M$-augmenting pathです。
よってaugmenting pathがなければ $M$ はmaximumです。□
&&&
この定理は任意の有限グラフで成り立ちます。ただしaugmenting pathを効率よく見つける方法は、二部グラフと一般グラフで異なります。二部グラフでは単純な交互探索で十分ですが、一般グラフではodd cycleを縮約するblossomの処理が必要です。
## 二部グラフで交互探索をする
二部グラフ $G=(X\sqcup Y,E)$ とmatching $M$ を考え、未飽和な $X$ 頂点を全て探索の根にします。
&&&alg 二部グラフのaugmenting path探索 [32-alg-bipartite-augmenting-search]
1. 全ての未飽和頂点 $x\in X$ をqueueへ入れ、rootとして印を付ける。
2. $X$ 頂点からは $M$ に属さない辺だけを $Y$ 側へたどる。
3. 到達した $Y$ 頂点が未飽和なら、親pointerを逆にたどってaugmenting pathを返す。
4. 到達した $Y$ 頂点がmatching辺 $yx'$ をもつなら、その一本だけをたどって $x'$ を探索へ加える。
5. queueが空になるまで3が起こらなければ、augmenting pathなしと報告する。
&&&
&&&thm 二部交互探索の正当性 [32-thm-bipartite-search-correctness]
算法 [32-alg-bipartite-augmenting-search] が未飽和 $Y$ 頂点へ到達したとき、親pointer pathは $M$-augmenting pathである。到達せず終了したなら、$M$-augmenting pathは存在しない。
&&&
&&&prf [32-prf-bipartite-search-correctness]
未飽和 $X$ rootから未飽和 $Y$ へ至る親pointer pathは、構成上、非matching辺から始まり、matching辺と非matching辺を交互に通り、非matching辺で終わります。探索木内のpathなので頂点を繰り返しません。両端が未飽和なのでaugmenting pathです。
逆に $M$-augmenting path
$$
x_0,y_1,x_1,y_2,\ldots,x_{k-1},y_k
$$
が存在するとします。$x_0$ は未飽和なので最初からqueueに入ります。$x_{i-1}$ が到達済みなら、非matching辺 $x_{i-1}y_i$ を算法は調べるので $y_i$ へ到達します。$i<k$ なら $y_i$ のmatching辺はpath上の $y_ix_i$ ただ一つなので、算法は $x_i$ へ進みます。帰納法により未飽和終点 $y_k$ へ到達し、成功するはずです。従って失敗終了時にaugmenting pathは存在しません。□
&&&
&&&alg 二部maximum matching算法 [32-alg-bipartite-maximum-matching]
空matching $M=\varnothing$ から始める。前算法で $M$-augmenting path $P$ が見つかる限り
$$
M\leftarrow M\triangle E(P)
$$
と更新する。pathが見つからなければ $M$ を出力する。
&&&
&&&thm 反復augmenting算法の正当性と停止 [32-thm-repeated-augmentation]
反復算法は有限回で停止し、二部グラフのmaximum matchingを出力する。孤立頂点を前処理し、隣接listによるBFSを毎回最初から行えば、計算時間は
$$
O(|V||E|)
$$
である。
&&&
&&&prf [32-prf-repeated-augmentation]
一回の反転ごとにmatchingの辺数は1増えます。matching辺数は高々 $\min(|X|,|Y|)\le |V|/2$ なので有限回で停止します。停止時には探索定理によりaugmenting pathがなく、Bergeの補題からmaximumです。
一回のBFSでは各頂点を高々一度queueへ入れ、各辺を高々定数回調べるため $O(|V|+|E|)$ 時間です。孤立頂点を除いたグラフでは全頂点に接続辺があり、次数和から $|V|\le2|E|$ です。反復回数は $O(|V|)$ なので全体は $O(|V||E|)$ です。□
&&&
高速なHopcroft--Karp算法は、最短augmenting pathを一度に複数反転して $O(\sqrt{|V|}|E|)$ を達成します。本章のCoreは単純算法までとし、速度改善はFurther Topicsに置きます。
## 失敗した探索はHall障害を返す
左側 $X$ の全頂点を飽和したいのに探索が失敗したとします。探索で到達した頂点を左右に分けて $Z_X\subseteq X,Z_Y\subseteq Y$ と書きます。
&&&thm 交互探索が返すHall障害 [32-thm-search-hall-obstruction]
二部グラフで $M$ がmaximumだが $X$ を飽和しないとする。全ての未飽和 $X$ 頂点から交互探索を行い、到達集合を $Z_X,Z_Y$ とする。このとき
$$
N(Z_X)=Z_Y,\qquad |Z_X|>|Z_Y|.
$$
従って $Z_X$ はHall条件の失敗を具体的に証明する。
&&&
&&&prf [32-prf-search-hall-obstruction]
$x\in Z_X$ の任意の隣接頂点 $y$ を考えます。辺 $xy$ が $M$ に属さなければ探索規則により $y\in Z_Y$ です。$xy\in M$ なら、$x$ は未飽和rootではなく、$x$ へ到達するときにそのmatching辺を $y$ からたどっています。従ってやはり $y\in Z_Y$ です。ゆえに $N(Z_X)\subseteq Z_Y$。逆に $Z_Y$ の頂点は $Z_X$ からの辺で到達したので $Z_Y\subseteq N(Z_X)$ です。
$M$ はmaximumなのでaugmenting pathがなく、到達した $Y$ 頂点は全て $M$ で飽和されています。各 $y\in Z_Y$ のmatching相手は探索規則により $Z_X$ に入ります。反対に、$Z_X$ のうちrootでない頂点は、到達した $Y$ 頂点のmatching相手として入ります。
従って $M$ は $Z_Y$ と「$Z_X$ から未飽和rootを除いた部分」の間に全単射を与えます。未飽和rootは少なくとも一つあるので
$$
|Z_X|>|Z_Y|=|N(Z_X)|.
$$
□
&&&
成功時にはより大きいmatching、失敗時には不可能性を示す集合が得られます。算法が答えだけでなく証明書も返す典型例です。
## 具体例――三人の割当を組み替える
$$
X=\{a,b,c\},\qquad Y=\{1,2,3\}
$$
とし
$$
N(a)=\{1\},\quad N(b)=\{1,2\},\quad N(c)=\{2,3\}.
$$
現在のmatchingを $M=\{b1,c2\}$ とします。$a$ は未飽和です。交互探索は
$$
a\xrightarrow{\notin M}1
\xrightarrow{\in M}b
\xrightarrow{\notin M}2
\xrightarrow{\in M}c
\xrightarrow{\notin M}3
$$
というaugmenting pathを見つけます。反転すると
$$
M'=\{a1,b2,c3\}
$$
となり、三人全員が割り当てられます。
## 一般グラフで何が難しくなるか
三角形のようなodd cycleでは、根からある頂点へ偶数長で到達したか奇数長で到達したかが、左右の部で固定されません。交互探索木の二枝を結ぶ辺が現れたとき、二部グラフのように直ちにaugmenting pathとも失敗とも判定できない場合があります。
Bergeの補題自体は一般グラフでも正しいので、課題は探索です。Edmondsのblossom算法は交互なodd cycleを一頂点へ縮約し、縮約グラフで見つけたpathを元へ展開します。この処理はFurther Topicsとし、Coreでは二部グラフ算法を完全に扱います。
## 演習
&&&exc maximalだがmaximumでないmatching [32-exc-maximal-not-maximum]
六頂点path $1-2-3-4-5-6$ で、maximalだがmaximumでないmatchingを一つ挙げ、そのmatchingに対するaugmenting pathを示せ。
&&&
&&&prf 解答 [32-prf-maximal-not-maximum-answer]
$M=\{23,45\}$ とします。未使用辺12は頂点2、34は既存二辺の端点、56は頂点5と接するため、どの辺も追加できずmaximalです。
しかしpath $1,2,3,4,5,6$ は
$$
12\notin M, 23\in M, 34\notin M, 45\in M, 56\notin M
$$
と交互で、両端1,6は未飽和です。反転すると $\{12,34,56\}$ となり、辺数3のperfect matchingを得ます。□
&&&
&&&exc symmetric differenceを分解する [32-exc-decompose-symmetric-difference]
cycle $C_6$ の辺を順に $12,23,34,45,56,61$ とし
$$
M=\{12,34,56\},\qquad N=\{23,45,61\}
$$
とする。$M\triangle N$ の成分と辺の交互性を調べよ。
&&&
&&&prf 解答 [32-prf-decompose-symmetric-difference-answer]
$M,N$ は共通辺をもたず、和集合が $C_6$ の全六辺なので $M\triangle N=E(C_6)$ です。非孤立成分は偶cycle一つで、辺は
$$
12\in M, 23\in N, 34\in M, 45\in N, 56\in M, 61\in N
$$
と交互に並びます。各matchingの辺は3本で、反転しても大きさは変わりません。□
&&&
&&&exc augmenting pathを反転する [32-exc-flip-path]
matching $M=\{x_2y_1,x_3y_2\}$ とpath
$$
x_1,y_1,x_2,y_2,x_3,y_3
$$
が与えられたとする。必要な非matching辺を明記し、反転後のmatchingを書け。
&&&
&&&prf 解答 [32-prf-flip-path-answer]
必要な非matching辺は
$$
x_1y_1,\quad x_2y_2,\quad x_3y_3
$$
です。$x_1,y_3$ が未飽和ならaugmenting pathで、反転後は
$$
M'=\{x_1y_1,x_2y_2,x_3y_3\}
$$
となり、辺数は2から3へ増えます。□
&&&
&&&exc 探索失敗からHall集合を得る [32-exc-hall-certificate]
$$
N(a)=N(b)=N(c)=\{1,2\},\qquad N(d)=\{3,4\}
$$
で、matching $M=\{a1,b2,d3\}$ から未飽和頂点 $c$ を根に交互探索する。到達集合 $Z_X,Z_Y$ を求めよ。
&&&
&&&prf 解答 [32-prf-hall-certificate-answer]
$c$ から1,2へ到達し、それらのmatching相手 $a,b$ へ到達します。$a,b$ の近傍から新しい頂点は出ないので
$$
Z_X=\{a,b,c\},\qquad Z_Y=\{1,2\}.
$$
従って $N(Z_X)=Z_Y$ かつ $2<3$ で、Hall障害です。□
&&&
&&&exc path成分の辺数差 [32-exc-component-edge-difference]
$M\triangle N$ の一成分がalternating pathであるとき、その両端の辺種類により $|M\cap E(P)|-|N\cap E(P)|$ を分類せよ。
&&&
&&&prf 解答 [32-prf-component-edge-difference-answer]
両端がともに $M$-辺なら $M$-辺が一本多く、差は1です。両端の種類が異なれば同数で差は0です。両端がともに $N$-辺なら $N$-辺が一本多く、差は $-1$ です。これは交互列を端から書けば直ちに確認できます。□
&&&
&&&exc 完全二部グラフでの反復回数 [32-exc-complete-bipartite-iterations]
空matchingから反復augmenting算法を $K_{p,q}$ に適用する。停止時のmatching辺数とaugmenting回数を求めよ。また $p\le q$ のとき長さ1のpathだけを選び続けられることを示せ。
&&&
&&&prf 解答 [32-prf-complete-bipartite-iterations-answer]
maximum matchingの大きさは小さい部の頂点数
$$
\min(p,q)
$$
であり、空から一回ごとに1増えるため反復回数も同じです。
$p\le q$ とし、現在の大きさを $k<p$ とします。両側に未飽和頂点があり、完全二部グラフではその二頂点間に辺があります。この一辺自体が長さ1のaugmenting pathなので、毎回そのようなpathを選べます。□
&&&
## 本章で得たもの
augmenting pathの反転はmatchingを一つ増やします。二つのmatchingのsymmetric differenceがalternating pathと偶cycleへ分解されるため、augmenting pathがないことはmaximumであることと同値です。
二部グラフでは交互BFSによりpathを見つけられ、反復すればmaximum matchingが得られます。探索が失敗した場合も、到達集合が $|N(S)|<|S|$ を満たすHall障害を返します。


3-2 増加路

## 描き方と頂点名は本質ではない
同じ交通網を紙の上で違う形に描き、町へ違う名前を付けても、どの町どうしが結ばれているかが保存されていれば同じgraphです。その「同じ」を全単射として定義します。
部分graph・誘導部分graph・補graphは次のように定義されます。本章では、それらの構成が頂点名の付け替えと両立することを証明し、同型を否定する不変量、同型を構成する具体的方法、自己同型が数え上げへ与える影響まで進みます。
## graph同型
&&&def graph同型 [05-def-graph-isomorphism]
単純graph $G,H$ の間の[[グラフ同型|graph同型]]とは、全単射
$$
\varphi:V(G)\longrightarrow V(H)
$$
で、任意の相異なる $u,v\in V(G)$ に対して
$$
uv\in E(G)
\quad\Longleftrightarrow\quad
\varphi(u)\varphi(v)\in E(H)
$$
を満たすものをいう。
同型が存在するとき $G\cong H$ と書く。
&&&
条件は辺を辺へ送るだけでなく、非辺も非辺へ送ることを要求しています。全単射であり辺数が等しい場合には「辺を辺へ送る」だけから逆向きも従いますが、定義では最初から同値として書く方が安全です。
&&&prop graph同型は同値関係 [05-prop-graph-isomorphism-equivalence]
有限単純graph全体で、同型関係 $\cong$ は反射的・対称的・推移的である。
&&&
&&&prf [05-prf-graph-isomorphism-equivalence]
恒等写像 $\operatorname{id}_{V(G)}$ は隣接関係をそのまま保つので $G\cong G$ です。
$\varphi:G\to H$ が同型なら全単射なので逆写像 $\varphi^{-1}:V(H)\to V(G)$ があります。定義の同値を逆向きに読めば、$\varphi^{-1}$ も隣接・非隣接を保ちます。従って $G\cong H$ なら $H\cong G$ です。
$\varphi:G\to H$ と $\psi:H\to K$ が同型なら、合成 $\psi\circ\varphi$ は全単射です。また
$$
uv\in E(G)
\Longleftrightarrow
\varphi(u)\varphi(v)\in E(H)
\Longleftrightarrow
\psi(\varphi(u))\psi(\varphi(v))\in E(K).
$$
従って合成も同型で、推移律が成り立ちます。□
&&&
## 同型が保存する量
&&&prop 同型による次数と近傍の保存 [05-prop-isomorphism-preserves-neighborhoods]
$\varphi:G\to H$ が同型なら、各 $v\in V(G)$ に対して
$$
\varphi(N_G(v))=N_H(\varphi(v))
$$
であり、
$$
\deg_G(v)=\deg_H(\varphi(v)).
$$
&&&
&&&prf [05-prf-isomorphism-preserves-neighborhoods]
$u\in N_G(v)$ であることは $uv\in E(G)$ と同値です。同型の定義から、これは
$$
\varphi(u)\varphi(v)\in E(H),
$$
すなわち $\varphi(u)\in N_H(\varphi(v))$ と同値です。$\varphi$ は全単射なので近傍どうしを全単射に移し、その要素数である次数も等しくなります。□
&&&
&&&prop 同型による道と連結性の保存 [05-prop-isomorphism-preserves-paths]
$\varphi:G\to H$ が同型なら、頂点列
$$
v_0,v_1,\ldots,v_k
$$
が $G$ のwalk、trail、path、cycleであることと
$$
\varphi(v_0),\varphi(v_1),\ldots,\varphi(v_k)
$$
が $H$ で同じ種類の列であることは同値である。従って連結性、連結成分数、各cycle長は同型で保存される。
&&&
&&&prf [05-prf-isomorphism-preserves-paths]
連続する二頂点が隣接するという条件は、同型によって前後同値に保存されます。$\varphi$ は単射なので、頂点の一致・相異なりも保存します。また辺 $uv$ は辺 $\varphi(u)\varphi(v)$ へ一対一に移るので、辺の重複の有無も保存されます。従ってwalk、trail、path、cycleの各定義条件がすべて保存されます。
$u$ から $v$ へのpathは $\varphi(u)$ から $\varphi(v)$ へのpathへ移り、逆写像で逆向きも従います。従って同じ連結成分に属する関係が保存され、成分数も保存されます。□
&&&
同様に、辺数、次数列、三角形数、長さ $k$ のcycle数、clique数、独立集合数、彩色数などは同型不変量です。
&&&def graph不変量 [05-def-graph-invariant]
graph $G$ に値 $I(G)$ を対応させ、$G\cong H$ なら必ず
$$
I(G)=I(H)
$$
となるものを[[グラフ不変量|graph不変量]]という。
&&&
不変量が異なれば非同型だと直ちに分かります。しかし一つ、あるいはいくつかの不変量が一致しても、同型とは限りません。
### 同じ次数列でも非同型
$K_{3,3}$ と三角柱graphは、ともに6頂点3-正則です。しかし $K_{3,3}$ は二部graphなので三角形をもちません。三角柱graphは上面と下面に三角形をもちます。三角形の有無は同型で保存されるため、二つは非同型です。
この例では次数列の次に三角形数を見ることで区別できました。同型判定では、安い不変量から順に試し、異なればそこで終了し、一致した場合だけ写像の構成へ進みます。
## 部分graph・誘導部分graph・埋め込み
ここで、$V(H)\subseteq V(G)$、$E(H)\subseteq E(G)$ を満たす部分graphと、選んだ頂点間の全辺を残す誘導部分graph $G[S]$ を定義しました。
&&&def graph埋め込み [05-def-graph-embedding]
単射
$$
\iota:V(H)\longrightarrow V(G)
$$
が
$$
uv\in E(H)
\Longrightarrow
\iota(u)\iota(v)\in E(G)
$$
を満たすとき、$H$ から $G$ への[[グラフ埋め込み|部分graph埋め込み]]という。
さらに
$$
uv\in E(H)
\Longleftrightarrow
\iota(u)\iota(v)\in E(G)
$$
を満たすとき[[誘導埋め込み]]という。
&&&
部分graph埋め込みでは、$H$ にない辺が像の頂点間に存在しても構いません。誘導埋め込みでは非辺も保存するため、像上の誘導部分graphが $H$ と同型になります。
&&&prop 埋め込みと部分graph [05-prop-embedding-subgraph-equivalence]
$H$ が $G$ と同型な部分graphとして現れることと、$H$ から $G$ への部分graph埋め込みが存在することは同値である。誘導部分graphについても、部分graph埋め込みを誘導埋め込みへ置き換えれば同じである。
&&&
&&&prf [05-prf-embedding-subgraph-equivalence]
$J\subseteq G$ と $H\cong J$ が与えられれば、同型 $H\to J$ と包含写像 $J\hookrightarrow G$ の合成が部分graph埋め込みです。
逆に埋め込み $\iota$ があれば、頂点集合 $\iota(V(H))$ と辺集合
$$
\{\iota(u)\iota(v)\mid uv\in E(H)\}
$$
からなる $G$ の部分graph $J$ を取れます。$\iota:H\to J$ は全単射で隣接関係を前後同値に保存するので同型です。
誘導の場合、非辺も保存する条件により $J=G[\iota(V(H))]$ となります。逆向きも同じ合成で従います。□
&&&
### 頂点・辺の削除
$v\in V(G)$ に対して
$$
G-v=G[V(G)\setminus\{v\}]
$$
と書きます。辺 $e\in E(G)$ に対しては、頂点を残して $e$ だけを削除したgraphを $G-e$ と書きます。
頂点削除は必ず誘導部分graphを作り、辺削除は一般には誘導部分graphを作りません。この二操作は「切断点・橋・ブロック」でcut vertexとbridgeを定義するときに使います。
## 補graphと同型
&&&prop 補graphは同型と可換 [05-prop-complement-commutes-isomorphism]
$$
G\cong H
\quad\Longleftrightarrow\quad
\overline G\cong\overline H.
$$
さらに $S\subseteq V(G)$ に対して
$$
\overline{G[S]}=\overline G[S],
$$
ただし左辺の補graphは頂点集合 $S$ 上で取る。
&&&
&&&prf [05-prf-complement-commutes-isomorphism]
$\varphi:G\to H$ が同型なら、相異なる $u,v$ に対し
$$
\begin{aligned}
uv\in E(\overline G)
&\Longleftrightarrow uv\notin E(G)\\
&\Longleftrightarrow
\varphi(u)\varphi(v)\notin E(H)\\
&\Longleftrightarrow
\varphi(u)\varphi(v)\in E(\overline H).
\end{aligned}
$$
従って同じ $\varphi$ が補graph間の同型です。逆向きは補graphをもう一度取り
$$
\overline{\overline G}=G
$$
を使えば従います。
二つ目の式では、$u,v\in S$ に対し、左辺でも右辺でも「$uv$ が $G$ の辺でない」ときちょうど辺になります。頂点集合もともに $S$ なので等しいです。□
&&&
この命題から、$S$ が $G$ のcliqueであることと、$S$ が $\overline G$ の独立集合であることが同値になります。
## 自己補graph
&&&def 自己補graph [05-def-self-complementary-graph]
$$
G\cong\overline G
$$
を満たすgraph $G$ を[[自己補グラフ|自己補graph]]という。
&&&
&&&prop 自己補graphの頂点数 [05-prop-self-complementary-order]
$n$ 頂点の自己補graphが存在するなら
$$
n\equiv0\ \text{または}\ 1\pmod4.
$$
&&&
&&&prf [05-prf-self-complementary-order]
$G\cong\overline G$ なら辺数は等しいです。一方、補graphの辺数公式から
$$
|E(G)|+|E(\overline G)|=\binom n2.
$$
従って
$$
2|E(G)|=\binom n2=\frac{n(n-1)}2,
$$
すなわち
$$
|E(G)|=\frac{n(n-1)}4.
$$
右辺が整数なので $4\mid n(n-1)$ です。連続する二整数の一方だけが偶数であり、その偶数が4の倍数でなければならないため
$$
n\equiv0\quad\text{または}\quad1\pmod4.
$$
□
&&&
これは必要条件であって、この命題だけでは存在を示していません。$P_4$ は自己補です。頂点をpath順に $1-2-3-4$ とすると、補graphの辺は
$$
13,\ 14,\ 24
$$
です。写像
$$
1\mapsto3,\quad2\mapsto1,\quad3\mapsto4,\quad4\mapsto2
$$
は $P_4$ から補graphへの同型になります。
## 隣接行列による同型判定
$V(G)=\{v_1,\ldots,v_n\}$ に対し、隣接行列を
$$
(A_G)_{ij}=
\begin{cases}
1,&v_iv_j\in E(G),\\
0,&v_iv_j\notin E(G)
\end{cases}
$$
と定めます。単純graphなので対角成分は0で、行列は対称です。
&&&thm 置換行列による同型判定 [05-thm-isomorphism-permutation-matrix]
$n$ 頂点graph $G,H$ が同型であるための必要十分条件は、ある置換行列 $P$ が存在して
$$
A_H=P^{\mathsf T}A_GP
$$
となることである。
&&&
&&&prf [05-prf-isomorphism-permutation-matrix]
同型 $\varphi:V(G)\to V(H)$ があるとします。$H$ の頂点順序を、$\varphi(v_1),\ldots,\varphi(v_n)$ に並べ替える置換行列を $P$ と取ります。行と列を同じ置換で並べ替えた行列 $P^{\mathsf T}A_GP$ の $(i,j)$ 成分は、対応する二頂点が $G$ で隣接するかを表します。同型により、それは $H$ の対応する二頂点が隣接することと同値なので $A_H$ と一致します。
逆に等式を満たす置換行列 $P$ は頂点の全単射を定めます。行列の $(i,j)$ 成分が前後で等しいことは、対応する頂点対が辺であることが前後同値であることを意味します。従ってその全単射はgraph同型です。□
&&&
この定理は「頂点名の付け替え」が隣接行列の行と列を同時に置換することだと述べています。全置換を試せば有限時間で同型判定できますが、候補は $n!$ 個あります。実際の判定では次数、近傍次数multiset、成分、短いcycleなどの不変量で候補を先に絞ります。
## 自己同型群
&&&def graphの自己同型群 [05-def-graph-automorphism-group]
graph $G$ から自分自身への同型全体を
$$
\operatorname{Aut}(G)
$$
と書く。写像の合成を積とすると、これを $G$ の[[グラフの自己同型群|自己同型群]]という。
&&&
&&&prop 自己同型は群をなす [05-prop-automorphisms-form-group]
$\operatorname{Aut}(G)$ は写像の合成について有限群をなす。また
$$
\operatorname{Aut}(G)=\operatorname{Aut}(\overline G)
$$
である。
&&&
&&&prf [05-prf-automorphisms-form-group]
同型の合成は同型なので積について閉じています。写像の合成は結合的です。恒等写像は自己同型であり、自己同型の逆写像も同型です。頂点集合が有限なので、その置換全体の部分集合である $\operatorname{Aut}(G)$ も有限です。従って有限群です。
補graphと同型の命題により、$G$ の自己同型 $\varphi$ は同じ写像のまま $\overline G$ の自己同型になります。逆向きも補を二回取れば従うため、二つの自己同型集合は等しいです。□
&&&
### 具体例
- $K_n$ では任意の頂点置換が辺を辺へ送るので
  $|\operatorname{Aut}(K_n)|=n!$。
- $P_n$、$n\ge2$ では、次数1の二端点を固定するか交換するかで自己同型が決まり
  $|\operatorname{Aut}(P_n)|=2$。
- $C_n$、$n\ge3$ では、一頂点の像を $n$ 通り、その隣の頂点の像を時計回り・反時計回りの2通りに選べるので
  $|\operatorname{Aut}(C_n)|=2n$。
$P_n$ の主張では、端点の像が決まると、その端点から距離 $k$ の唯一の頂点の像も順に決まります。$C_n$ では最初の頂点と向きが決まれば、隣接関係により全頂点の像が決まります。どの選択も実際に恒等・反転、または回転・鏡映を与えるので、上の個数を尽くします。
## ラベル付き実現の個数
同じ抽象graphへ頂点名 $1,\ldots,n$ を付ける方法は $n!$ 通りに見えます。しかし自己同型だけ異なる二つの付け方は、同じlabelled edge setを与えます。
&&&thm ラベル付き実現数 [05-thm-labelled-copies-automorphism]
$n$ 頂点の抽象graph $G$ を、固定した頂点集合 $[n]$ 上のgraphとして実現する異なる方法の個数は
$$
\frac{n!}{|\operatorname{Aut}(G)|}.
$$
&&&
&&&prf [05-prf-labelled-copies-automorphism]
全単射
$$
\lambda:V(G)\to[n]
$$
は $n!$ 個あります。各 $\lambda$ は辺 $uv$ を辺 $\lambda(u)\lambda(v)$ へ送り、$[n]$ 上のlabelled graphを作ります。
二つの全単射 $\lambda,\lambda'$ が同じlabelled graphを作るための必要十分条件は
$$
\alpha=\lambda'^{-1}\circ\lambda
$$
が $G$ の自己同型であることです。実際、同じ辺集合を作ることは
$$
uv\in E(G)
\Longleftrightarrow
\alpha(u)\alpha(v)\in E(G)
$$
と同値です。
一つのlabelled実現を与える $\lambda$ に対し、同じ実現を与える付け方は自己同型 $\alpha$ を用いた
$$
\lambda\circ\alpha
$$
の形でちょうど $|\operatorname{Aut}(G)|$ 個あります。従って $n!$ 個の全単射は同じ大きさの組へ分かれ、異なる実現数は
$$
\frac{n!}{|\operatorname{Aut}(G)|}
$$
です。□
&&&
例えば $C_5$ のlabelled実現数は
$$
\frac{5!}{|\operatorname{Aut}(C_5)|}
=\frac{120}{10}=12.
$$
これは $K_5$ の10本の辺から5本を選ぶ $\binom{10}{5}=252$ 通りのうち、5-cycleになるものが12個あるという意味です。
## 頂点推移性
&&&def 頂点推移graph [05-def-vertex-transitive-graph]
任意の $u,v\in V(G)$ に対し
$$
\varphi(u)=v
$$
となる自己同型 $\varphi\in\operatorname{Aut}(G)$ が存在するとき、$G$ を[[頂点推移グラフ|頂点推移graph]]という。
&&&
&&&prop 頂点推移なら正則 [05-prop-vertex-transitive-regular]
有限頂点推移graphは正則である。
&&&
&&&prf [05-prf-vertex-transitive-regular]
任意の $u,v$ に対し $u$ を $v$ へ送る自己同型があります。同型は次数を保存するので
$$
\deg(u)=\deg(v).
$$
すべての頂点次数が等しいため正則です。□
&&&
逆は成り立ちません。$C_3\cup C_4$ は全頂点次数2で正則ですが、自己同型は三角形成分の頂点を四角形成分へ送れません。cycle長と成分の大きさが保存されるからです。従って頂点推移ではありません。
## 演習
&&&exc 明示的な同型 [05-exc-isomorphism-explicit-map]
$G$ の頂点集合を $\{1,2,3,4\}$、辺集合を
$$
\{12,23,34\}
$$
とする。$H$ の頂点集合を $\{a,b,c,d\}$、辺集合を
$$
\{ac,cd,db\}
$$
とする。$G\cong H$ を示す同型を一つ与えよ。
&&&
&&&prf 解答 [05-prf-isomorphism-explicit-map-answer]
$$
\varphi(1)=a,\quad
\varphi(2)=c,\quad
\varphi(3)=d,\quad
\varphi(4)=b
$$
と置きます。これは頂点集合間の全単射であり、三辺
$$
12,\ 23,\ 34
$$
をそれぞれ
$$
ac,\ cd,\ db
$$
へ送ります。両graphは4頂点3辺なので、残る三つの非辺も非辺へ送られます。従って同型です。□
&&&
&&&exc 同じ次数列の非同型graph [05-exc-isomorphism-prism-k33]
$K_{3,3}$ と三角柱graphが非同型であることを、次数列だけではなく別の不変量を用いて示せ。
&&&
&&&prf 解答 [05-prf-isomorphism-prism-k33-answer]
どちらも6頂点3-正則なので次数列は
$$
(3,3,3,3,3,3)
$$
です。
$K_{3,3}$ は二部graphであり、すべてのcycle長は偶数なので三角形をもちません。三角柱graphは上下の底面に三角形を二つもちます。三角形の個数は同型不変量なので、二つは非同型です。□
&&&
&&&exc $P_4$ の自己補性 [05-exc-isomorphism-p4-self-complementary]
頂点 $1,2,3,4$ と辺 $12,23,34$ をもつ $P_4$ の補graphを求め、本文と異なる同型 $P_4\to\overline{P_4}$ を一つ与えよ。
&&&
&&&prf 解答 [05-prf-isomorphism-p4-self-complementary-answer]
$K_4$ の六辺から $12,23,34$ を除くので
$$
E(\overline{P_4})=\{13,14,24\}.
$$
例えば
$$
1\mapsto2,\quad
2\mapsto4,\quad
3\mapsto1,\quad
4\mapsto3
$$
と置くと
$$
12\mapsto24,\qquad
23\mapsto14,\qquad
34\mapsto13.
$$
三辺を補graphの三辺へ全単射に移すため、同型です。□
&&&
&&&exc cliqueと独立集合 [05-exc-isomorphism-clique-independent-complement]
$S\subseteq V(G)$ とする。$G[S]$ が完全graphであることと、$\overline G[S]$ が空graphであることが同値であることを証明せよ。
&&&
&&&prf 解答 [05-prf-isomorphism-clique-independent-complement-answer]
$G[S]$ が完全であるとは、$S$ の相異なる任意の二頂点が $G$ で隣接することです。補graphでは各頂点対について隣接・非隣接が逆になるため、これは $S$ のどの二頂点も $\overline G$ で隣接しないことと同値です。後者は $\overline G[S]$ が空graphであることです。□
&&&
&&&exc cycleのlabelled実現 [05-exc-isomorphism-labelled-cycles]
固定頂点集合 $[6]$ 上に、$C_6$ と同型なgraphはいくつあるか。
&&&
&&&prf 解答 [05-prf-isomorphism-labelled-cycles-answer]
$|\operatorname{Aut}(C_6)|=2\cdot6=12$ です。従ってラベル付き実現数は
$$
\frac{6!}{12}
=\frac{720}{12}
=60.
$$
□
&&&
&&&exc 自己同型群の軌道 [05-exc-isomorphism-automorphism-orbits]
star graph $K_{1,4}$ の自己同型群が頂点集合上にもつ軌道を求め、自己同型群の位数を求めよ。
&&&
&&&prf 解答 [05-prf-isomorphism-automorphism-orbits-answer]
中心頂点は次数4、四つの葉は次数1です。自己同型は次数を保存するので中心を中心へ送り、葉全体を葉全体へ送ります。従って頂点軌道は
$$
\{\text{中心}\},\qquad
\{\text{四つの葉}\}
$$
の二つです。
四つの葉は任意に置換でき、その置換は隣接関係を保存します。中心の像は固定されるので、自己同型は葉の置換と一対一です。従って
$$
|\operatorname{Aut}(K_{1,4})|=4!=24.
$$
□
&&&

1-1 同型・部分グラフ・補グラフ

> **前提知識**：グラフ彩色、平面性判定の構造
> 
## greedy算法の成否は順序で決まる
「グラフ彩色」では、頂点を一つずつ見て、既に塗られた隣接頂点が使っていない最小の色を選ぶgreedy coloringを導入しました。最大次数を $\Delta$ とすれば、どの順序でも高々 $\Delta+1$ 色です。
しかし同じgraphでも順序を変えると使用色数は変わります。重要なのは「各頂点を塗る時点で、先に塗られた隣接頂点が何個いるか」です。退化度は、全ての部分graphに必ず低次数頂点があることを使い、そのような良い順序を後ろから作ります。
## 順序付きgreedy bound
&&&def backward degree [38-def-backward-degree]
頂点順序
$$
v_1,v_2,\ldots,v_n
$$
に対して、$v_i$ より前に置かれた隣接頂点の個数
$$
b_i=\bigl|N(v_i)\cap\{v_1,\ldots,v_{i-1}\}\bigr|
$$
を $v_i$ の[[後方次数|backward degree]]という。
&&&
&&&thm ordering greedy bound [38-thm-ordering-greedy-bound]
順序 $v_1,\ldots,v_n$ に沿ってgreedy coloringを行うと、使用色数は
$$
1+\max_i b_i
$$
以下である。
&&&
&&&prf [38-prf-ordering-greedy-bound]
$v_i$ を塗る時点で既に色をもつ隣接頂点は、順序で前にあるものだけです。その個数は $b_i$ なので、禁止される色は高々 $b_i$ 個です。
従って色 $1,2,\ldots,b_i+1$ の中には少なくとも一色、禁止されていないものがあります。greedy算法は使用可能な最小色を選ぶので、$v_i$ の色は高々 $b_i+1$ です。全頂点について最大を取れば結論を得ます。□
&&&
最大次数上界 $\chi(G)\le\Delta(G)+1$ は、$b_i\le\deg(v_i)\le\Delta(G)$ と置いた特別な場合です。順序を工夫すれば $\Delta$ よりずっと小さい上界が得られます。
&&&example 二部graphでも悪い順序は多数の色を使う [38-ex-crown-order]
二部を
$$
A=\{a_1,\ldots,a_r\},\qquad B=\{b_1,\ldots,b_r\}
$$
とし、$a_i b_j$ を $i\ne j$ のとき全て結ぶcrown graphを考えます。二部graphなので、本当の彩色数は2です。
ところが
$$
a_1,b_1,a_2,b_2,\ldots,a_r,b_r
$$
の順でfirst-fit greedy coloringを行うと、$a_i,b_i$ はともに色 $i$ になります。実際、$a_i$ は先に塗られた $b_1,\ldots,b_{i-1}$ と全て隣接するため色 $1,\ldots,i-1$ を使えず、$b_i$ も同様に $a_1,\ldots,a_{i-1}$ と隣接します。一方 $a_i,b_i$ は非隣接なので同じ色 $i$ を使えます。
したがって2-colorable graphでも、悪い順序ならgreedy算法は $r$ 色を使います。退化順序はこの危険を一様に抑えます。
&&&
## 退化度
&&&def degeneracy [38-def-degeneracy]
非負整数 $k$ に対して、graph $G$ が $k$-degenerateであるとは、$G$ の全ての非空部分graphが次数 $k$ 以下の頂点をもつことをいう。
$G$ が $k$-degenerateとなる最小の $k$ を[[退化度]]といい、
$$
d(G)
$$
と書く。
&&&
「全ての部分graph」を調べる定義は強く見えますが、頂点を一つずつ削る順序と同値です。
&&&thm degeneracy ordering characterization [38-thm-degeneracy-ordering]
有限graph $G$ と非負整数 $k$ に対して次は同値である。
1. $G$ は $k$-degenerateである。
2. 頂点を
   $$
   u_1,u_2,\ldots,u_n
   $$
   と並べ、各 $u_i$ が後ろの集合 $\{u_{i+1},\ldots,u_n\}$ に高々 $k$ 個の隣接頂点しかもたないようにできる。
3. 頂点を
   $$
   v_1,v_2,\ldots,v_n
   $$
   と並べ、各頂点のbackward degreeを高々 $k$ にできる。
&&&
&&&prf [38-prf-degeneracy-ordering]
1を仮定します。$G$ 自身に次数 $k$ 以下の頂点があるので、それを $u_1$ として削除します。残った誘導部分graphも $G$ の部分graphなので、再び次数 $k$ 以下の頂点 $u_2$ があります。これを空になるまで繰り返します。
$u_i$ を選んだ時点で残っているのは $u_i,u_{i+1},\ldots,u_n$ です。従って $u_i$ の後ろの隣接頂点数は、その時点の次数であり高々 $k$ です。よって2です。
2の順序を逆にして
$$
v_i=u_{n+1-i}
$$
と置きます。$v_i$ より前の頂点は、元の $u$ 順序で $u_{n+1-i}$ より後ろにあった頂点です。その隣接数は高々 $k$ なので3です。
3を仮定し、$H$ を任意の非空部分graphとします。$H$ の頂点のうち、順序で最も後ろにあるものを $v_j$ とします。$H$ 内の他の全頂点は $v_j$ より前にあるため、
$$
\deg_H(v_j)\le b_j\le k.
$$
従って全ての非空部分graphに次数 $k$ 以下の頂点があり、1です。□
&&&
証明はそのまま算法です。現在次数が最小の頂点を削除してstackへ積み、最後にstackを逆順で取り出せば退化順序が得られます。
## 退化度のmin--max表示
部分graph $H$ の最小次数を $\delta(H)$ と書きます。
&&&thm degeneracy min--max formula [38-thm-degeneracy-minmax]
有限graph $G$ に対して
$$
d(G)=\max_{\varnothing\ne H\subseteq G}\delta(H).
$$
右辺では全ての非空部分graphを動かす。
&&&
&&&prf [38-prf-degeneracy-minmax]
右辺を $r$ とします。全ての非空部分graph $H$ で $\delta(H)\le r$ なので、各 $H$ は次数 $r$ 以下の頂点をもちます。従って $G$ は $r$-degenerateであり、
$$
d(G)\le r.
$$
一方、最大値を達成する部分graph $H_0$ では全頂点次数が少なくとも $r$ です。もし $G$ が $(r-1)$-degenerateなら、$H_0$ に次数 $r-1$ 以下の頂点が必要となり矛盾します。従って $d(G)\ge r$ です。両不等式から等号を得ます。□
&&&
任意の部分graph $H$ を、その頂点集合が誘導するgraph $G[V(H)]$ へ置き換えると辺は増えるだけなので最小次数は下がりません。従って最大値は誘導部分graphだけを調べても同じです。
&&&example 基本graphの退化度 [38-ex-basic-degeneracy]
treeに二頂点以上あれば、全ての非空部分forestは孤立頂点またはleafをもつので $d(T)\le1$ です。辺を含む部分graphの最小次数は1なので $d(T)=1$ です。
cycle $C_n$ は全頂点次数2なので $d(C_n)\ge2$、最大次数も2なので $d(C_n)=2$ です。
完全graph $K_n$ は最小次数 $n-1$ なので
$$
d(K_n)=n-1.
$$
完全二部graph $K_{p,q}$ では、$p\le q$ とすると全体の最小次数は $p$ です。一方、どの部分graphにも $q$ 側由来の頂点があればその次数は高々 $p$ なので
$$
d(K_{p,q})=p=\min\{p,q\}.
$$
&&&
## 退化度から彩色する
&&&thm degeneracy coloring theorem [38-thm-degeneracy-coloring]
有限graph $G$ は
$$
d(G)+1
$$
色でproperに頂点彩色できる。特に
$$
\chi(G)\le d(G)+1\le\Delta(G)+1.
$$
&&&
&&&prf [38-prf-degeneracy-coloring]
$k=d(G)$ とし、退化順序の特徴づけからbackward degreeが高々 $k$ の順序を取ります。この順序でgreedy coloringを行えば、ordering greedy boundにより高々 $k+1$ 色です。
また任意の部分graphの最小次数はその最大次数以下なので
$$
d(G)=\max_H\delta(H)\le\Delta(G).
$$
従って二つ目の不等式も得られます。□
&&&
&&&cor clique bound from degeneracy [38-cor-clique-degeneracy]
$G$ のclique numberを $\omega(G)$ とすると
$$
\omega(G)\le d(G)+1.
$$
&&&
&&&prf [38-prf-clique-degeneracy]
$r$ 頂点clique $K_r$ は $G$ の部分graphで、その最小次数は $r-1$ です。min--max公式から
$$
d(G)\ge r-1.
$$
最大の $r=\omega(G)$ を取れば結論を得ます。□
&&&
この下界と彩色上界が一致するgraphもありますが、一般には一致しません。例えば奇cycleは $d=2$ で3色必要なので一致し、偶cycleは同じ退化度2でも2色で足ります。
## $k$-coreとpeeling
&&&def $k$-core [38-def-k-core]
graph $G$ の $k$-core（[[k-core]]）とは、最小次数が少なくとも $k$ である極大な誘導部分graphをいう。空graphになる場合も許す。
&&&
&&&prop $k$-coreの一意性 [38-prop-k-core-unique]
$G$ の $k$-coreは一意であり、次数 $k$ 未満の頂点をなくなるまで任意の順序で削除して得られる。
&&&
&&&prf [38-prf-k-core-unique]
最小次数が少なくとも $k$ の誘導部分graph $G[A]$ と $G[B]$ があるとします。$A$ の頂点は $A\cup B$ 内でも $A$ 内にいた少なくとも $k$ 個の隣接頂点を保ち、$B$ の頂点も同様です。従って $G[A\cup B]$ の最小次数も少なくとも $k$ です。
したがって、その性質をもつ全頂点集合の和集合が最大の一つを作り、$k$-coreは一意です。
peelingで削除される頂点 $v$ は、削除時点の残存graphで次数 $k$ 未満です。もし $v$ がある最小次数 $k$ 以上の誘導部分graph $H$ に属したなら、$v$ より先に削除された $H$ の頂点を最初のものとして取ると、その削除時点では他の $H$ 頂点が全て残っており、次数は少なくとも $k$ のはずで矛盾します。従って削除頂点はどの候補coreにも属しません。
停止時に残った誘導部分graphは最小次数が少なくとも $k$ です。削除頂点は最大候補へ入れず、残存頂点は候補を作るので、それが一意な $k$-coreです。削除順序によらないことも従います。□
&&&
&&&cor degeneracy and cores [38-cor-degeneracy-cores]
$d(G)$ は、非空な $k$-coreが存在する最大の $k$ に等しい。
&&&
&&&prf [38-prf-degeneracy-cores]
非空な $k$-coreがあれば、それは最小次数 $k$ 以上の部分graphなのでmin--max公式から $d(G)\ge k$ です。
逆に $d(G)=r$ なら、最小次数 $r$ の部分graphが存在します。その頂点集合が誘導するgraphも最小次数 $r$ 以上なので、$r$-coreは非空です。従って最大値は $r$ です。□
&&&
$k$-coreはnetworkの「互いに少なくとも $k$ 本の接続を保つ密な中心部」を抽出します。退化度は、そのcoreが何段階まで残るかを一つの数にまとめたものです。
## acyclic orientationとの同値
&&&def acyclic orientation [38-def-acyclic-orientation]
無向graphの各辺へ向きを付けて有向cycleが生じないとき、その向き付けを[[非巡回向き付け|acyclic orientation]]という。
&&&
&&&thm degeneracy orientation formula [38-thm-degeneracy-orientation]
有限graph $G$ に対して
$$
d(G)=
\min_{\mathcal O}
\max_{v\in V(G)}\deg_{\mathcal O}^+(v),
$$
ここで $\mathcal O$ は全acyclic orientationを動き、$\deg_{\mathcal O}^+(v)$ はoutdegreeである。
&&&
&&&prf [38-prf-degeneracy-orientation]
$k=d(G)$ とし、各頂点が後ろに高々 $k$ 個の隣接頂点をもつ退化順序 $u_1,\ldots,u_n$ を取ります。各辺を順序の前から後ろへ向けます。添字は有向辺に沿って真に増えるので有向cycleはありません。各 $u_i$ のoutdegreeは後ろの隣接頂点数であり高々 $k$ です。従って右辺は $k$ 以下です。
逆にacyclic orientation $\mathcal O$ を取り、最大outdegreeを $r$ とします。有限acyclic digraphにはsourceを順に削除するtopological ordering
$$
u_1,\ldots,u_n
$$
があり、全arcは前から後ろへ向きます。従って各 $u_i$ の後ろの隣接頂点数はoutdegree以下で、高々 $r$ です。退化順序の特徴づけから $d(G)\le r$ です。全orientationで最小を取れば右辺は $d(G)$ 以上となり、等号です。□
&&&
順序・peeling・core・acyclic orientationは同じ疎性を別の言葉で見ています。問題に合う表現へ切り替えられることが抽象化の利点です。
## planar graphへの適用
&&&thm planar degeneracy bounds [38-thm-planar-degeneracy-bounds]
頂点数3以上のsimple planar graphは5-degenerateである。さらにtriangle-freeなら3-degenerateである。
&&&
&&&prf [38-prf-planar-degeneracy-bounds]
simple planar graphの任意の部分graphもsimple planarです。頂点数 $n_H\ge3$ の非空部分graph $H$ に対して、「平面グラフ」の辺数評価から
$$
|E(H)|\le3|V(H)|-6.
$$
従って平均次数は
$$
\frac{2|E(H)|}{|V(H)|}<6.
$$
全頂点次数が6以上なら平均も6以上になるので、$H$ は次数5以下の頂点をもちます。頂点数1または2でも次数は高々1です。従って元のgraphは5-degenerateです。
triangle-freeの場合、任意の部分graphもtriangle-freeであり、
$$
|E(H)|\le2|V(H)|-4
$$
です。頂点数3以上なら平均次数は4未満なので次数3以下の頂点があります。小さい場合も同様です。従って3-degenerateです。□
&&&
&&&cor algorithmic color bounds for planar graphs [38-cor-planar-color-bounds]
simple planar graphは退化順序に沿うgreedy算法で6-colorableであり、triangle-freeなら4-colorableである。
&&&
&&&prf [38-prf-planar-color-bounds]
前定理とdegeneracy coloring theoremを順に使えば
$$
\chi(G)\le5+1=6
$$
および
$$
\chi(G)\le3+1=4
$$
です。証明中の低次数頂点削除を記録し、逆順にgreedy彩色すれば実際の彩色を構成できます。□
&&&
一般の平面graphで6色を5色へ減らすには、次数5の頂点の五つの隣接色を単に数えるだけでは足りません。
## 計算量
隣接list、現在次数、次数ごとのbucketを用意します。次数最小の頂点をbucketから取り出して削除し、その隣接頂点の次数を1ずつ下げます。各頂点は一度削除され、各辺は端点削除時に定数回だけ調べられるため、退化順序と全core numberを
$$
O(|V|+|E|)
$$
時間で計算できます。
得た順序の逆順greedy coloringも各辺を定数回見るので線形時間です。したがって退化度上界は存在証明であるだけでなく、彩色を出力する算法でもあります。
## 演習
&&&exc wheelの退化度 [38-exc-wheel-degeneracy]
cycle $C_n$ の全頂点へ新しい中心頂点を接続したwheel $W_{n+1}$（$n\ge4$）の退化度を求めよ。
&&&
&&&prf 解答 [38-prf-wheel-degeneracy-answer]
rim頂点の次数は3、中心の次数は $n$ なので、全体の最小次数は3です。従って $d(W_{n+1})\ge3$ です。
任意の部分graphを考えます。中心を含まなければcycleの部分graphなので次数2以下の頂点があります。中心を含む場合も、rim側の誘導部分がcycle全体でなければ端に当たるrim頂点の部分graph内次数は中心への一本を加えて高々2です。cycle全体を含めばrim頂点次数は3です。従って全ての部分graphに次数3以下の頂点があり、$d(W_{n+1})\le3$ です。ゆえに退化度は3です。□
&&&
&&&exc 退化順序から彩色する [38-exc-color-from-order]
頂点順序 $u_1,\ldots,u_6$ で、各 $u_i$ が後ろに高々2個の隣接頂点をもつ。どの順序でgreedy彩色すれば3色上界が得られるか説明せよ。
&&&
&&&prf 解答 [38-prf-color-from-order-answer]
順序を逆にして
$$
u_6,u_5,\ldots,u_1
$$
の順で塗ります。$u_i$ を塗る時点で既に塗られた隣接頂点は、元の順序で $u_i$ より後ろにあったものだけなので高々2個です。従って禁止色は高々2色で、三色のうち少なくとも一色を使えます。□
&&&
&&&exc coreをpeelingする [38-exc-core-peeling]
path $P_5$ に、その中央三頂点が作る三角形となるよう両端以外の三頂点間へ不足辺を加えたgraphを考える。1-core、2-core、3-coreを求めよ。
&&&
&&&prf 解答 [38-prf-core-peeling-answer]
graphに孤立頂点はないので1-coreは全graphです。
2-coreを求めるには次数1の両端を削除します。残る中央三頂点は三角形で各次数2なので停止し、2-coreはこの三角形です。
3-coreでは、まず両端を削除した後の三角形の各次数が2で3未満なので全て削除されます。従って3-coreは空です。最大の非空core番号は2なので、退化度も2です。□
&&&
&&&exc cliqueから退化度を下から押さえる [38-exc-clique-lower-bound]
$G$ が $K_6$ を部分graphとして含むとき、$d(G)$ と $\chi(G)$ への下界を求めよ。
&&&
&&&prf 解答 [38-prf-clique-lower-bound-answer]
$K_6$ の最小次数は5なので、退化度のmin--max公式から
$$
d(G)\ge5.
$$
またcliqueの六頂点は互いに隣接し、全て異なる色が必要なので
$$
\chi(G)\ge6.
$$
退化度彩色定理は上界 $\chi(G)\le d(G)+1$ を与えますが、ここでは $d(G)$ の正確な値が不明なので、それだけから上界6とは言えません。□
&&&
&&&exc orientationから退化度を読む [38-exc-orientation-bound]
あるgraphに最大outdegree2のacyclic orientationが与えられた。退化度と彩色数への上界を証明せよ。
&&&
&&&prf 解答 [38-prf-orientation-bound-answer]
degeneracy orientation formulaから
$$
d(G)\le2.
$$
またdegeneracy coloring theoremから
$$
\chi(G)\le d(G)+1\le3.
$$
構成的にはorientationのtopological orderingを取り、逆順にgreedy彩色すれば各頂点を見る時点の既彩色隣接頂点は高々2個です。□
&&&
&&&exc triangle-free planar graph [38-exc-triangle-free-planar]
頂点数 $n\ge3$ のtriangle-free simple planar graphで、次数3以下の頂点が必ず存在することを、平均次数から直接証明せよ。
&&&
&&&prf 解答 [38-prf-triangle-free-planar-answer]
各face境界長が少なくとも4なので、「平面グラフ」のEuler公式による評価から
$$
|E|\le2|V|-4
$$
です。従って平均次数は
$$
\frac{1}{|V|}\sum_v\deg(v)
=\frac{2|E|}{|V|}
\le4-\frac{8}{|V|}
<4.
$$
全頂点次数が4以上なら平均次数も4以上となるので矛盾します。従って少なくとも一頂点の次数が3以下です。□
&&&
## 本章で得たもの
退化度は次の四つを同じ数で結びます。
- 全ての部分graphに現れる低次数頂点
- 頂点を削るpeeling順序
- 非空な $k$-coreの最大段階
- acyclic orientationで抑えられる最大outdegree
この同値性から、$d$-degenerate graphはgreedy算法で $d+1$ 色に塗れます。simple planar graphには $d\le5$、triangle-free planar graphには $d\le3$ が成り立つため、六色・四色の構成的上界が得られました。


6-2 貪欲彩色と退化度

> **前提知識**：平面グラフ
> 
## 辺数評価をすり抜ける非平面グラフ
「平面グラフ」では、simple planar graphが
$$
e\le3v-6
$$
を満たすことを示しました。しかしこれは必要条件にすぎません。
$K_{3,3}$ の各辺の途中へ新頂点を一つずつ置くと、頂点数は6から15、辺数は9から18になります。上界
$$
18\le3\cdot15-6=39
$$
を十分に満たします。それでも平面には描けません。途中の次数2頂点を消して二本の辺をつなげば、$K_{3,3}$ の平面描画が得られてしまうからです。
つまり平面性の障害は辺の密度だけでなく、「辺を長いpathへ引き伸ばしても残る構造」にあります。
## 辺の分割とsubdivision
&&&def 辺の分割とsubdivision [05-def-edge-subdivision]
グラフ $G$ の辺 $uv$ を削除し、新しい頂点 $w$ と二辺 $uw,wv$ を加える操作を[[辺の分割]]という。
辺の分割を有限回行って得られるグラフを $G$ の[[細分グラフ|subdivision]]という。$G$ と $H$ が共通のsubdivisionをもつとき、両者は[[同相なグラフ|homeomorphic]]であるという。
&&&
一つの辺を何度も分割することは、その辺を内部頂点が互いに異なるpathへ置き換えることです。元の頂点をbranch vertex、途中に入れた次数2頂点をdivision vertexと呼びます。
&&&thm subdivisionと平面性 [05-thm-subdivision-planarity]
グラフ $G$ がplanarであるための必要十分条件は、$G$ の任意のsubdivisionがplanarであることである。また、一つでもplanarなsubdivisionがあれば $G$ はplanarである。
&&&
&&&prf [05-prf-subdivision-planarity]
$G$ のplane描画があれば、分割する辺の曲線上に新頂点を置くだけで、辺を交差させずに分割後のグラフを描けます。これを繰り返せば任意のsubdivisionがplanarです。
逆に、$G$ のsubdivision $H$ がplane描画をもつとします。分割で加えられた次数2頂点 $w$ の近くでは、二辺 $uw,wv$ は $w$ 以外で交わらない二本のarcです。その二本を一つのarcとして滑らかにつなぎ、$w$ を消します。この操作は十分小さい近傍内で行えるため、他の辺との交差を作りません。
division vertexを一つずつ消すと $G$ のplane描画を得ます。従って $G$ はplanarです。□
&&&
この定理により、$K_5$ または $K_{3,3}$ のsubdivisionはすべて非平面です。
## subdivisionを部分グラフとして含む
&&&def topological minor [05-def-topological-minor]
グラフ $G$ が、グラフ $H$ のsubdivisionと同型な部分グラフを含むとき、$H$ は $G$ の[[位相的マイナー|topological minor]]であるという。
&&&
別の言い方をすると、$H$ の各頂点を $G$ の相異なるbranch vertexへ送り、$H$ の各辺を、それらを結ぶpathへ置き換えます。異なる辺に対応するpathはbranch vertex以外の内部頂点を共有してはいけません。
&&&cor Kuratowski障害の十分性 [05-cor-kuratowski-obstruction-sufficient]
グラフ $G$ が $K_5$ または $K_{3,3}$ をtopological minorとして含むなら、$G$ は非平面である。
&&&
&&&prf [05-prf-kuratowski-obstruction-sufficient]
$G$ がplanarだと仮定します。planar graphの部分グラフは、不要な辺と頂点をplane描画から削ればplanarです。従って $G$ に含まれる $K_5$ または $K_{3,3}$ のsubdivisionもplanarになります。
subdivisionと平面性の定理から、元の $K_5$ または $K_{3,3}$ もplanarになってしまいます。しかし「平面グラフ」で両者が非平面であることを証明しました。矛盾です。□
&&&
この方向だけでも、具体的な非平面性証明に強力です。重要なのは、見た目ではなくbranch vertexと内部で交わらないpathを明示することです。
## 辺の縮約とminor
&&&def 辺の縮約とminor [05-def-edge-contraction-minor]
辺 $uv$ の[[辺の縮約|縮約]]とは、$u,v$ を一つの新頂点へ同一視し、それらに接続していた辺を新頂点へ接続し直す操作をいう。生じたloopは削除し、平行辺は単純グラフとして扱う場合一本にまとめる。
頂点削除、辺削除、辺縮約を有限回行って $H$ が得られるとき、$H$ は $G$ の[[グラフマイナー|minor]]であるという。
&&&
&&&thm planar graphのminorはplanar [05-thm-planar-minors]
planar graphから頂点削除、辺削除、辺縮約で得られるグラフはplanarである。
&&&
&&&prf [05-prf-planar-minors]
頂点や辺の削除はplane描画から対応する点・曲線を消すだけなので平面性を保ちます。
辺 $uv$ の縮約では、plane描画上のarc $uv$ に沿って頂点 $u$ を $v$ へ連続的に動かします。$uv$ の内部は他の頂点や辺に触れないので、十分細い近傍の中で、$u$ に接続する辺の端だけを一緒に引き寄せられます。$u$ と $v$ が重なった後にloopを消し、平行辺を一本へまとめても交差は生じません。
各操作が平面性を保つため、有限回の操作で得られるminorもplanarです。□
&&&
&&&cor minorによる非平面性 [05-cor-nonplanar-minor-obstruction]
$G$ が $K_5$ または $K_{3,3}$ をminorとして含むなら、$G$ は非平面である。
&&&
&&&prf [05-prf-nonplanar-minor-obstruction]
$G$ がplanarなら、その全minorも前定理によりplanarです。しかし $K_5,K_{3,3}$ は非平面なので、それらをminorとしてもつことはできません。対偶を取れば主張を得ます。□
&&&
topological minorなら、各辺を置き換えたpathを縮約して元のグラフを得られるためminorでもあります。逆は一般には成り立ちません。minorでは、一つのbranch vertexに対応する部分を連結な頂点集合まで膨らませられるからです。
## Kuratowskiの定理が主張すること
ここまでで「$K_5$ または $K_{3,3}$ のsubdivisionを含めば非平面」という方向を完全に証明しました。Kuratowskiの定理は、逆方向も成り立つと主張します。
&&&thm Kuratowskiの定理 [05-thm-kuratowski]
有限グラフ $G$ がplanarであるための必要十分条件は、$G$ が $K_5$ と $K_{3,3}$ のいずれもtopological minorとして含まないことである。
&&&
十分性、すなわち「二つの障害を含まなければplane描画が存在する」の証明は長く、平面内のbridge配置を整理する複数の補題を必要とします。この第一周では定理を判定規則として使用しません。完全証明は「平面性判定の構造」で、次の順に独立して行います。
1. 非平面グラフから辺数最小の反例を取る。
2. 最小反例が3-connectedに近い構造をもつことを示す。
3. cycleに対するbridgeと、そのattachmentの交差を調べる。
4. 交互配置するbridgeから $K_{3,3}$ subdivisionを作る。
5. 交互配置しない場合からplane embeddingを組み立て、最小性に反する。
従って本章で証明済みとして使ってよいのは「障害を見つければ非平面」という方向です。逆方向を用いる箇所は「平面性判定の構造」以後に限定します。
## Wagnerの見方との違い
minorを使った対応定理は次の形です。
> 有限グラフがplanarであるための必要十分条件は、$K_5,K_{3,3}$ をminorとして含まないことである。
これはWagnerの定理です。Kuratowskiはsubdivision、Wagnerはminorを使います。結論は似ていますが、一般のグラフ $H$ について「$H$ をminorに含む」と「$H$ subdivisionを含む」は同じではありません。平面性では二つの特別な障害がどちらの言葉でも完全な特徴づけを与えます。
Wagnerの定理も本章では推論に使用しません。「平面性判定の構造」のKuratowski証明後に、縮約との対応を補論として証明します。
## 障害を手で見つける方法
具体的なグラフから $K_5$ subdivisionを探すなら、次数4以上のbranch vertex候補を5個選び、それぞれの組を結ぶ10本のpathを探します。$K_{3,3}$ なら、左右3個ずつのbranch vertex候補と、左右の各組を結ぶ9本のpathを探します。
確認事項は三つです。
1. branch vertexはすべて相異なる。
2. 各pathの内部にbranch vertexを含まない。
3. 異なるpathの内部頂点は互いに交わらない。
単に「$K_{3,3}$ のように見える」だけでは不十分です。pathを辺へ縮めたとき、本当に目的のグラフになることを確認します。
## 例――分割された $K_{3,3}$
左右のbranch vertexを
$$
X=\{a,b,c\},\qquad Y=\{1,2,3\}
$$
とします。九つの組 $(x,i)\in X\times Y$ ごとに新頂点 $w_{xi}$ を置き、二辺
$$
xw_{xi},\qquad w_{xi}i
$$
を加えます。
各 $x$-$i$ pathは $x,w_{xi},i$ で、内部頂点 $w_{xi}$ は九つすべて異なります。従ってこのグラフ全体が $K_{3,3}$ のsubdivisionであり、前に証明した系だけで非平面だと結論できます。辺数上界は満たしますが、構造的障害は消えていません。
## 最小非平面性と辺の削除
&&&def edge-minimal nonplanar [05-def-edge-minimal-nonplanar]
非平面グラフ $G$ が[[辺極小非平面的グラフ|edge-minimal nonplanar]]であるとは、任意の辺 $e$ に対して $G-e$ がplanarであることをいう。
&&&
任意の有限非平面グラフから、平面性を回復しない限り辺を削り続ければedge-minimal nonplanar部分グラフが得られます。この有限降下は簡単ですが、「その最小障害が必ず $K_5$ または $K_{3,3}$ のsubdivisionを含む」と示す部分がKuratowski定理の核心です。
&&&prop edge-minimal nonplanar graphにはbridgeがない [05-prop-minimal-nonplanar-no-bridge]
edge-minimal nonplanar graph $G$ はbridgeをもたない。
&&&
&&&prf [05-prf-minimal-nonplanar-no-bridge]
bridge $e=uv$ があると仮定します。$G-e$ は二つの側へ分かれます。edge-minimal性により $G-e$ はplanarなので、各連結成分を別々の小円盤内にplane描画できます。
$u$ を含む成分と $v$ を含む成分の描画を離して置き、両者の外面に $u,v$ が来るよう描画を反転・変形します。二つの円盤の外側を通るarcで $u$ と $v$ を結べば、他の辺と交差せずにbridge $e$ を戻せます。すると $G$ がplanarになり矛盾です。従ってbridgeはありません。□
&&&
## 演習
&&&exc subdivisionの次数 [05-exc-kuratowski-subdivision-degrees]
$K_5$ の各辺を任意回分割して得たグラフで、次数4の頂点はいくつあり、それ以外の新頂点の次数はいくつか。
&&&
&&&prf 解答 [05-prf-kuratowski-subdivision-degrees-answer]
元の $K_5$ の五頂点は各次数4です。辺を分割しても元の頂点に接続する辺が途中で切り替わるだけで、次数は変わりません。
分割で加えた新頂点は、置き換えたpathの前後の二頂点とのみ隣接するため次数2です。従って次数4のbranch vertexが5個あり、全division vertexの次数は2です。□
&&&
&&&exc topological minorからminorへ [05-exc-kuratowski-topological-to-minor]
$H$ が $G$ のtopological minorなら、$H$ が $G$ のminorでもあることを証明せよ。
&&&
&&&prf 解答 [05-prf-kuratowski-topological-to-minor-answer]
$G$ の部分グラフ $S$ が $H$ のsubdivisionと同型だとします。まず $G$ から $S$ に属さない頂点と辺を削除して $S$ を得ます。
$H$ の各辺を置き換えたpathで、内部のdivision vertexに接続する辺を順に縮約します。異なるpathは内部頂点を共有しないため、この操作は他の辺対応を壊しません。全pathを一本の辺へ戻すと $H$ が得られます。従って $H$ はminorです。□
&&&
&&&exc 非平面性の保存 [05-exc-kuratowski-additions]
非平面グラフへ頂点や辺を追加して得たグラフも非平面であることを示せ。
&&&
&&&prf 解答 [05-prf-kuratowski-additions-answer]
追加後のグラフを $G'$、元の非平面グラフを $G$ とします。$G$ は $G'$ の部分グラフです。もし $G'$ がplanarなら、そのplane描画から追加した頂点と辺を削除して $G$ のplane描画が得られます。これは $G$ の非平面性に反します。従って $G'$ も非平面です。□
&&&
&&&exc Petersen graphのminor [05-exc-kuratowski-petersen-minor]
Petersen graphを、外側の5-cycle $v_0v_1\cdots v_4v_0$、内側の頂点 $u_0,\ldots,u_4$、spoke $v_iu_i$、内側の辺 $u_iu_{i+2}$（添字は5を法とする）で定める。五本のspoke $v_iu_i$ をすべて縮約すると得られるグラフを記述せよ。
&&&
&&&prf 解答 [05-prf-kuratowski-petersen-minor-answer]
各spokeを縮約し、$v_i,u_i$ を一頂点 $w_i$ にまとめます。外側の辺から $w_iw_{i+1}$ が、内側の辺から $w_iw_{i+2}$ が得られます。
5頂点では、相異なる二頂点の添字差は5を法として $\pm1$ または $\pm2$ のいずれかです。従ってすべての二頂点間に辺があり、得られる単純グラフは $K_5$ です。よってPetersen graphは $K_5$ minorをもち、非平面です。□
&&&
&&&exc 辺数評価では判定できない [05-exc-kuratowski-sparse-obstruction]
$K_5$ の各辺を $r\ge1$ 回分割したグラフ $G_r$ の頂点数と辺数を求め、$e\le3v-6$ を満たすことを確認せよ。それでも非平面である理由を述べよ。
&&&
&&&prf 解答 [05-prf-kuratowski-sparse-obstruction-answer]
$K_5$ は5頂点10辺です。一辺ごとに $r$ 個の新頂点を加えるので
$$
v=5+10r.
$$
一辺は $r+1$ 本へ分かれるので
$$
e=10(r+1)=10r+10.
$$
右辺は
$$
3v-6=3(5+10r)-6=30r+9.
$$
$r\ge1$ なら
$$
10r+10\le30r+9
$$
です。しかし $G_r$ は $K_5$ のsubdivisionそのものなので、subdivisionと平面性の定理により非平面です。□
&&&
&&&exc 最小障害の次数 [05-exc-kuratowski-minimum-degree]
頂点削除についても最小、すなわち任意の頂点を削るとplanarになる非平面グラフ $G$ を考える。$G$ に次数0または1の頂点が存在しないことを示せ。
&&&
&&&prf 解答 [05-prf-kuratowski-minimum-degree-answer]
次数0の頂点 $v$ があれば、$G-v$ のplane描画へ、どの辺とも交わらない位置に孤立頂点 $v$ を戻せます。従って $G$ もplanarとなり矛盾です。
次数1の頂点 $v$ と唯一の隣接頂点 $u$ があれば、$G-v$ のplane描画で $u$ の十分小さい近傍に $v$ を置き、短いarc $uv$ を描けます。他の辺と交差しません。やはり $G$ がplanarとなり矛盾です。従って最小次数は少なくとも2です。□
&&&

5-2 Euler公式の限界とKuratowskiの定理

## 最安のnetworkは局所的選択で作れるか
都市を頂点、建設可能な回線を辺、費用を辺重みとします。全都市を通信可能にしたい一方、cycle上の一本は連結性だけを目的にするなら冗長です。従って最安networkはspanning treeの中から探せばよいことになります。
しかし、目についた最軽量辺を順に選ぶだけで、本当に全体の費用が最小になるでしょうか。一般の最適化問題では、局所的に最良な選択が大域的最適解を壊すことがあります。本章では、spanning treeの交換法則があるためにgreedy選択が安全であることを証明します。
## 重み付きグラフと最小全域木
&&&def weighted graphとminimum spanning tree [29-def-weighted-mst]
有限グラフ $G=(V,E)$ の各辺 $e$ に実数 $w(e)$ を対応させたものを[[重み付きグラフ|weighted graph]]という。辺集合 $F\subseteq E$ の重みを
$$
w(F)=\sum_{e\in F}w(e)
$$
と定める。
$G$ が連結であるとき、$G$ のspanning treeのうち重みが最小のものを[[最小全域木|minimum spanning tree]]、略してMSTという。
&&&
重みは負でも構いません。どのspanning treeも辺数が $|V|-1$ であり、候補は有限個なので最小値は必ず達成されます。
&&&prop MSTの存在 [29-prop-mst-existence]
有限連結weighted graphは少なくとも一つMSTをもつ。
&&&
&&&prf [29-prf-mst-existence]
有限グラフの辺部分集合は有限個しかないので、spanning treeも有限個です。連結性により少なくとも一つspanning treeが存在します。従ってspanning treeの重みからなる空でない有限実数集合は最小値をもち、その値を取る木がMSTです。□
&&&
## cutを横切る軽い辺は安全である
頂点集合の非自明な分割 $V=S\sqcup(V\setminus S)$ を考えます。この二側を結ぶには、どのspanning treeもcut $\delta(S)$ の辺を少なくとも一本使わなければなりません。
&&&thm cut property [29-thm-cut-property]
有限連結weighted graph $G$ のcut $\delta(S)$ において、重みが最小の辺を $e$ とする。このとき $e$ を含むMSTが存在する。
さらに $e$ がこのcut上で一意な最軽量辺なら、すべてのMSTが $e$ を含む。
&&&
&&&prf [29-prf-cut-property]
まずMST $T$ を一つ取ります。$e\in T$ なら前半は終わりです。$e\notin T$ とします。$T+e$ には「全域木と切断・閉路の性質」のfundamental cycle $C_T(e)$ がただ一つできます。$e$ はcutの一方から他方へ渡るので、このcycleは元の側へ戻るために、$e$ 以外にもcutを横切る辺 $f$ を含みます。
$e$ はcut上の最軽量辺なので $w(e)\le w(f)$ です。cycle交換定理により
$$
T'=T+e-f
$$
はspanning treeで、
$$
w(T')=w(T)+w(e)-w(f)\le w(T).
$$
$T$ はMSTなのでこれより軽いspanning treeはなく、等号が成り立って $T'$ もMSTです。しかも $e\in T'$ です。
次に $e$ が一意な最軽量辺とします。$e$ を含まないMST $T$ があったと仮定すると、上と同じ $f$ に対して $w(e)<w(f)$ です。従って $w(T')<w(T)$ となり、$T$ の最小性に反します。ゆえにすべてのMSTが $e$ を含みます。□
&&&
「最軽量辺を必ず含む」ではなく、同率がある場合は「それを含むMSTが少なくとも一つある」です。この量化の違いが重要です。
## cycle上の重い辺は捨てられる
cut propertyの双対がcycle propertyです。
&&&thm cycle property [29-thm-cycle-property]
有限連結weighted graph $G$ のcycle $C$ 上で重み最大の辺を $e$ とする。このとき $e$ を含まないMSTが存在する。
さらに $e$ が $C$ 上で一意な最重量辺なら、どのMSTも $e$ を含まない。
&&&
&&&prf [29-prf-cycle-property]
まずMST $T$ を一つ取ります。$e\notin T$ なら前半は終わりです。$e\in T$ とします。$T-e$ は二成分に分かれます。cycle $C$ から $e$ を除いた残りは $e$ の両端を結ぶpathなので、この二成分を横切る辺 $f\in C\setminus\{e\}$ が少なくとも一本あります。
$e$ はcycle上の最重量辺なので $w(f)\le w(e)$ です。cut交換定理により
$$
T'=T-e+f
$$
はspanning treeで、
$$
w(T')=w(T)-w(e)+w(f)\le w(T).
$$
従って $T'$ もMSTで、$e$ を含みません。
$e$ が一意な最重量辺なら $w(f)<w(e)$ です。$e$ を含むMSTを仮定すると上の交換でさらに軽いspanning treeができて矛盾します。従ってどのMSTも $e$ を含みません。□
&&&
cut propertyは「採用してよい辺」、cycle propertyは「除外してよい辺」を与えます。Kruskal算法はcycleを作らない最軽量辺を採用し、Prim算法は一つの成長中の頂点集合から外へ出る最軽量辺を採用します。
## forestを壊さない安全辺
算法の途中では、まだspanning treeではなく複数成分からなるforestを持ちます。
&&&def MSTへ拡張可能なforest [29-def-extendable-forest]
$G$ のforest $F$ が[[最小全域木へ拡張可能な森|MSTへ拡張可能]]であるとは、あるMST $T$ が存在して
$$
E(F)\subseteq E(T)
$$
となることをいう。
&&&
&&&lemma forest成分間の安全辺 [29-lem-safe-edge-forest]
$F$ をMSTへ拡張可能なspanning forestとする。相異なる $F$-成分を結ぶ全辺の中から最軽量辺 $e$ を選ぶ。このとき $F+e$ もMSTへ拡張可能である。
&&&
&&&prf [29-prf-safe-edge-forest]
$F$ を含むMST $T$ を取ります。$e\in T$ なら同じ $T$ が $F+e$ を含みます。
$e=uv\notin T$ とします。$u$ を含む $F$-成分の頂点集合を $S$ とします。$v$ は別の $F$-成分にあるので $e\in\delta(S)$ です。$T+e$ の基本cycleはcut $\delta(S)$ を $e$ 以外の辺 $f$ でも横切ります。
$F$ の辺は一つの $F$-成分の内部にしかないので、cutを横切る $f$ は $F$ に属しません。また $f$ は相異なる $F$-成分を結ぶ辺です。$e$ の選び方から
$$
w(e)\le w(f).
$$
従って $T'=T+e-f$ はMSTであり、$F+e$ を含みます。よって $F+e$ はMSTへ拡張可能です。□
&&&
この補題では、同率辺のどれを選んでも「その選択を含むMST」へ交換できます。未来の選択肢を完全に固定しなくても、少なくとも一つの最適解へ延長できるという不変量を保ちます。
## Kruskal算法
&&&alg Kruskal算法 [29-alg-kruskal]
入力：有限連結weighted graph $G=(V,E)$。
1. 辺を重みの非減少順に並べる。同率辺の順序は任意とする。
2. $F$ を全頂点と辺0本からなるforestとする。
3. 並べた順に辺 $e$ を調べる。
4. $F+e$ がcycleを作らない、すなわち $e$ の両端が異なる $F$-成分にあるなら $e$ を採用する。
5. $|V|-1$ 本を採用したら出力する。
&&&
&&&thm Kruskal算法の正当性 [29-thm-kruskal-correctness]
Kruskal算法は停止し、MSTを出力する。
&&&
&&&prf [29-prf-kruskal-correctness]
採用辺集合 $F$ がMSTへ拡張可能であることを不変量にします。初期forestは空辺集合であり、任意のMSTに含まれるので拡張可能です。
Kruskalが辺 $e$ を採用する時点で、$e$ は相異なる $F$-成分を結びます。また、それより軽い辺はすべて既に調べられています。もし相異なる $F$-成分を結ぶより軽い辺があれば、その辺を調べた時点でも両端は異なる成分にあり、採用されていたはずです。従って $e$ は現在の相異なる成分を結ぶ全辺の中で最軽量です。安全辺補題により $F+e$ もMSTへ拡張可能です。
cycleを作る辺は採用しないので、$F$ は常にforestです。もし全辺を調べても $F$ が非連結なら、$G$ の連結性により異なる $F$-成分を結ぶ辺があります。その辺は調べた時点でcycleを作らず採用されたはずなので矛盾です。従って最終的に $F$ は連結となり、$|V|-1$ 辺のspanning treeです。
終了時の $F$ はあるMST $T$ に含まれます。しかし $F,T$ はともに $|V|-1$ 本の辺をもつので $F=T$ です。従って出力はMSTです。□
&&&
### cycle判定と実行時間
単純な実装では、辺を採用するたびにDFSで両端が既に同じ成分か調べられます。辺数を $m$、頂点数を $n$ とすると、sortingに $O(m\log m)$、各辺のDFSに $O(n+m)$ かかるため、全体を
$$
O(m\log m+m(n+m))
$$
で実行できます。
より速い初等的実装として、各頂点に現在の成分番号を記録し、各成分の頂点listと大きさを持ちます。辺の両端の成分番号は $O(1)$ で比較できます。二成分を併合するときは、小さい方のlistに属する全頂点の成分番号を大きい方へ書き換えます。
一頂点の番号が書き換わるたび、その頂点が新たに属する成分の大きさは以前の少なくとも2倍です。成分の大きさは $n$ を超えないため、一頂点の番号は高々 $\lfloor\log_2 n\rfloor$ 回しか書き換わりません。従って全併合に要する書換えは $O(n\log n)$ 回です。sortingの $O(m\log m)$ と各辺の定数時間判定を合わせ、連結グラフでは $m\ge n-1$ なので全体は $O(m\log m)$ 時間、$O(n+m)$ 空間で実行できます。さらに高速なunion by rankとpath compressionもありますが、上の実装だけでこの評価は完結しています。
## Prim算法
Kruskal算法が複数の木を同時に育てるのに対し、Prim算法は一つの木だけを育てます。
&&&alg Prim算法 [29-alg-prim]
入力：有限連結weighted graph $G=(V,E)$ と開始頂点 $r$。
1. $S=\{r\}$、$F=\varnothing$ とする。
2. $S\ne V$ の間、cut $\delta(S)$ 上の最軽量辺 $e=uv$ を選ぶ。ただし $u\in S,v\notin S$ とする。
3. $e$ を $F$ に加え、$v$ を $S$ に加える。
4. $F$ を出力する。
&&&
$G$ は連結なので $S\ne V$ なら $\delta(S)$ は空ではありません。
&&&thm Prim算法の正当性 [29-thm-prim-correctness]
Prim算法は任意の開始頂点からMSTを出力する。
&&&
&&&prf [29-prf-prim-correctness]
各段階で、$F$ は頂点集合 $S$ を結ぶ木であり、あるMSTに含まれることを不変量にします。初期状態では一頂点と空辺集合なので成立します。
選んだ $e$ はcut $\delta(S)$ の最軽量辺です。$F$ を含むMST $T$ を一つ取ります。$e\notin T$ なら、cut propertyの証明と同じ交換を行います。$T+e$ のcycleには $e$ 以外のcut辺 $f$ があり、$F$ の辺はすべて $S$ 内部にあるため $f\notin F$ です。$w(e)\le w(f)$ なので $T+e-f$ は $F+e$ を含むMSTです。従って拡張可能性が保たれます。
$e$ は新頂点 $v$ を既存の木へ一本だけで接続するため、cycleを作らず、$F+e$ は $S\cup\{v\}$ を結ぶ木です。各反復で $|S|$ が1増えるので $n-1$ 回で $S=V$ となります。そのとき $F$ はspanning treeで、あるMSTに含まれ、辺数が等しいためそれ自身がMSTです。□
&&&
隣接行列から毎回cut辺を走査する単純実装は $O(n^2)$ 時間で実行できます。疎なグラフでは、各未採用頂点について現在の $S$ へつなぐ最軽量辺をpriority queueで管理すると、binary heapの挿入・更新・削除最小の各操作が $O(\log n)$ であり、全辺を高々定数回調べて $O(m\log n)$ 時間になります。
## 同率重みとMSTの一意性
同率重みがあるからといって必ず複数のMSTがあるわけではありません。しかし全辺重みが相異なれば一意性を保証できます。
&&&thm 相異なる辺重みならMSTは一意 [29-thm-distinct-weights-unique]
有限連結weighted graphで全ての辺重みが互いに異なるなら、MSTはただ一つである。
&&&
&&&prf [29-prf-distinct-weights-unique]
相異なる二つのMST $T_1,T_2$ があると仮定します。対称差
$$
E(T_1)\triangle E(T_2)
$$
の中で最も軽い辺を $e$ とし、必要なら番号を交換して $e\in T_1\setminus T_2$ とします。
$T_2+e$ の基本cycleは、$T_1-e$ が作るcutを横切る辺 $f\in T_2\setminus T_1$ を含みます。$e,f$ はともに対称差にあり、$e$ をその中の最軽量辺に選び、重みは相異なるので
$$
w(e)<w(f).
$$
cycle交換により $T_2+e-f$ はspanning treeで、その重みは
$$
w(T_2)+w(e)-w(f)<w(T_2)
$$
です。これは $T_2$ がMSTであることに反します。従ってMSTは一意です。□
&&&
逆は偽です。三角形の辺重みを1,1,2とすると、重み1の二辺を使うspanning treeだけが重み2で最小です。同率辺があってもMSTは一意です。
&&&prop 異なるMST間の同率交換 [29-prop-equal-exchange-between-msts]
$T_1,T_2$ を同じweighted graphの異なるMSTとする。$T_1\triangle T_2$ 内の最軽量辺 $e$ が $T_1\setminus T_2$ に属するとする。このとき、ある $f\in T_2\setminus T_1$ が存在して
$$
w(e)=w(f)
$$
であり、$T_1-e+f$ と $T_2-f+e$ はともにMSTになる。
&&&
&&&prf [29-prf-equal-exchange-between-msts]
「全域木と切断・閉路の性質」の対称交換定理の証明どおり、$T_1-e$ のcutを横切り、$T_2+e$ の基本cycle上にある $f\in T_2\setminus T_1$ を選べます。両方の交換後はspanning treeです。
$e$ は対称差内の最軽量辺なので $w(e)\le w(f)$ です。$T_2-f+e$ がspanning treeであり、$T_2$ はMSTなので
$$
w(T_2)-w(f)+w(e)\ge w(T_2),
$$
従って $w(e)\ge w(f)$ です。両方から $w(e)=w(f)$ を得ます。そのため交換後の二木の重みは元のMSTと等しく、どちらもMSTです。□
&&&
## KruskalとPrimを同じ例で動かす
頂点 $A,B,C,D,E$ と次の重み付き辺を考えます。
$$
\begin{array}{c|ccccccc}
\text{辺}&AB&AC&BC&BD&CD&CE&DE\\ \hline
\text{重み}&1&4&2&5&1&3&2
\end{array}
$$
Kruskal算法では重み順に $AB(1),CD(1),BC(2),DE(2),CE(3),AC(4),BD(5)$ と調べます。
1. $AB,CD$ を採用する。
2. $BC$ は二成分を結ぶので採用する。
3. $DE$ は新頂点 $E$ の成分を結ぶので採用する。
4. 4辺で5頂点が一つにつながったので終了する。
得る木は
$$
\{AB,BC,CD,DE\},\qquad w=1+2+1+2=6.
$$
Prim算法を $A$ から始めると、cut上の最軽量辺を順に
$$
AB(1), BC(2), CD(1), DE(2)
$$
と選び、同じ木を得ます。選択順は違っても、交換原理が最適性を保証します。
## 演習
&&&exc Kruskal算法を実行する [29-exc-run-kruskal]
頂点 $1,2,3,4$ と辺重み
$$
w(12)=1,\quad w(13)=3,\quad w(14)=4,\quad
w(23)=2,\quad w(24)=5,\quad w(34)=1
$$
をもつ $K_4$ にKruskal算法を適用し、採用・棄却の理由とMSTの重みを書け。
&&&
&&&prf 解答 [29-prf-run-kruskal-answer]
重み順は $12(1),34(1),23(2),13(3),14(4),24(5)$ です。最初の12と34はcycleを作らないので採用します。23は成分 $\{1,2\}$ と $\{3,4\}$ を結ぶので採用します。この時点で4頂点を結ぶ3辺の木ができ、終了します。
得るMSTは
$$
\{12,34,23\},\qquad w=1+1+2=4.
$$
13以降を調べる実装なら、13はcycle $1,2,3,1$ を作るため棄却されます。既にspanning treeが完成しているので残りは不要です。□
&&&
&&&exc Prim算法を別の始点から実行する [29-exc-run-prim]
直前の $K_4$ で、頂点4からPrim算法を実行せよ。同率がないので各段階の選択を明示し、Kruskal算法と同じMSTになることを確認せよ。
&&&
&&&prf 解答 [29-prf-run-prim-answer]
$S=\{4\}$ から出る辺は34(1),14(4),24(5)なので34を選びます。$S=\{3,4\}$ から外へ出る辺は23(2),13(3),14(4),24(5)なので23を選びます。$S=\{2,3,4\}$ から残る頂点1へ出る辺は12(1),13(3),14(4)なので12を選びます。
得る辺集合は
$$
\{34,23,12\}
$$
で、Kruskalの出力と同じ、重み4のMSTです。□
&&&
&&&exc cut propertyで必須辺を見つける [29-exc-cut-forced-edge]
連結weighted graphで、ある頂点 $v$ に接続する辺の重みが全て相異なり、その中で $e$ が最軽量であるとする。$e$ がすべてのMSTに含まれることを示せ。
&&&
&&&prf 解答 [29-prf-cut-forced-edge-answer]
cut $\delta(\{v\})$ は $v$ に接続する全辺からなります。仮定により $e$ はこのcut上の一意な最軽量辺です。cut propertyの一意性部分から、すべてのMSTが $e$ を含みます。□
&&&
&&&exc cycle propertyで不要辺を見つける [29-exc-cycle-forbidden-edge]
辺重み付きcycle
$$
v_1v_2\cdots v_kv_1
$$
で、辺 $v_kv_1$ の重みが他の全辺より真に大きい。このcycleを含む任意の連結グラフのMSTが $v_kv_1$ を含まないことを示せ。
&&&
&&&prf 解答 [29-prf-cycle-forbidden-edge-answer]
$v_kv_1$ は与えられたcycle上の一意な最重量辺です。cycle propertyの一意性部分から、その辺を含むMSTは存在しません。グラフのcycle外にどのような辺があっても、このcycle内の交換だけで重い辺を除けるため結論は変わりません。□
&&&
&&&exc 同率重みで複数のMST [29-exc-tied-multiple-mst]
四角形 $C_4$ の各辺重みを1とし、対角線一本の重みを2とする。このグラフのMSTをすべて列挙し、Kruskal算法の同率辺の順序により出力が変わり得ることを説明せよ。
&&&
&&&prf 解答 [29-prf-tied-multiple-mst-answer]
四角形の辺だけから三辺を選び、cycleを切ったものはspanning treeで重み3です。四角形の四辺のうちどれを除くかにより4通りあります。
対角線を含むspanning treeは、残り二辺の重みが各1なので総重みは少なくとも4です。従ってMSTは四角形から一辺を除いた4本、正確には4通りです。
Kruskal算法は重み1の四辺を任意順に調べ、最初の三辺がcycleを作らなければ採用します。四本目はcycleを作り棄却されます。同率辺の順序により棄却される四角形辺が変わるため、4通りのMSTが出力され得ます。□
&&&
&&&exc 負の重み [29-exc-negative-weights]
三角形の辺重みが $-5,-2,4$ である。MSTを求め、Kruskal・Primの証明が負の重みでも変わらない理由を述べよ。
&&&
&&&prf 解答 [29-prf-negative-weights-answer]
三頂点のspanning treeは三辺から二辺を選んだものです。最軽量の二辺 $-5,-2$ を選ぶと総重みは $-7$ で、他は $-1$ または2です。従ってMSTは重み $-5,-2$ の二辺です。
Kruskal算法は重みの大小順しか使わず、負かどうかを使いません。Prim算法とcut propertyの交換式
$$
w(T+e-f)=w(T)+w(e)-w(f)
$$
も $w(e)\le w(f)$ だけを使います。従って負の重みでも証明はそのまま成立します。□
&&&
## 本章で得たもの
cut上の最軽量辺はあるMSTへ安全に取り込め、cycle上の最重量辺はあるMSTから安全に除けます。「全域木と切断・閉路の性質」の交換法則に重み比較を加えるだけで、KruskalとPrimという異なるgreedy算法の正当性を同じ不変量から証明できました。
$$
n^{n-2}
$$
であるCayley公式を全単射として証明します。


2-3 最小全域木

## 解と上界の証明書が同じ大きさになる
matchingは互いに端点を共有しない辺を選びます。一方、vertex coverは全ての辺を少数の頂点で監視します。matchingの各辺は離れているため、どんなvertex coverも各matching辺から少なくとも一端ずつ選ばなければなりません。従って
$$
\text{matchingの大きさ}\le\text{vertex coverの大きさ}
$$
です。
一般グラフでは不等号が厳しいことがあります。三角形のmaximum matchingは1辺ですが、全三辺を覆うには2頂点必要です。しかし二部グラフでは必ず等号になります。augmenting path探索に失敗したときの到達集合から、最小coverを実際に構成できます。
## vertex coverと弱双対性
&&&def vertex coverとcovering number [33-def-vertex-cover]
グラフ $G$ の頂点集合 $C\subseteq V(G)$ が[[頂点被覆|vertex cover]]であるとは、全ての辺が少なくとも一方の端点を $C$ にもつことをいう。
vertex coverの[[頂点被覆数|最小頂点数]]を $\tau_v(G)$ と書く。matching numberは $\nu(G)$ と書く。
&&&
$\tau_v$ と下添字を付けるのは、spanning tree数に用いた記号との衝突を避けるためです。
&&&prop matchingとvertex coverの弱双対性 [33-prop-weak-duality]
任意の有限グラフ $G$、matching $M$、vertex cover $C$ に対して
$$
|M|\le|C|
$$
である。従って
$$
\nu(G)\le\tau_v(G).
$$
&&&
&&&prf [33-prf-weak-duality]
$C$ は各matching辺 $e\in M$ の少なくとも一端を含みます。$M$ の異なる辺は端点を共有しないため、一つのcover頂点を二本のmatching辺の代表にはできません。各 $e\in M$ に $C$ 内の一端を対応させると単射が得られ、$|M|\le|C|$ です。最大matchingと最小coverを選べば第二式を得ます。□
&&&
## maximum matchingからminimum coverを作る
二部グラフ $G=(X\sqcup Y,E)$ のmaximum matching $M$ を取ります。全ての未飽和 $X$ 頂点から、「増加路」の規則で交互探索します。
- $X$ から $Y$ へは非matching辺をたどる。
- $Y$ から $X$ へはmatching辺をたどる。
到達した集合を $Z_X\subseteq X,Z_Y\subseteq Y$ とし
$$
C=(X\setminus Z_X)\cup Z_Y
$$
と置きます。
&&&lemma 交互到達集合から得るcover [33-lem-alternating-cover]
$M$ がmaximumなら $C=(X\setminus Z_X)\cup Z_Y$ はvertex coverである。
&&&
&&&prf [33-prf-alternating-cover]
coverされない辺 $xy$ があると仮定します。$x\notin X\setminus Z_X$ なので $x\in Z_X$、また $y\notin Z_Y$ です。
$xy\notin M$ なら、探索は到達済みの $x$ からこの非matching辺をたどって $y$ へ到達するので矛盾です。
$xy\in M$ なら、$x$ は未飽和rootではありません。到達したmatched $X$ 頂点は、そのmatching相手からmatching辺をたどって到達します。matching辺は一意なので相手は $y$ であり、やはり $y\in Z_Y$ です。従ってcoverされない辺はありません。□
&&&
&&&lemma 構成したcoverの大きさ [33-lem-alternating-cover-size]
上の設定で
$$
|C|=|M|.
$$
&&&
&&&prf [33-prf-alternating-cover-size]
maximum matchingにはaugmenting pathがないので、到達した全ての $Y$ 頂点は飽和されています。各 $y\in Z_Y$ のmatching相手は $Z_X$ に属します。逆に $Z_X$ のうち未飽和rootでない頂点は、ある $Z_Y$ 頂点のmatching相手として到達します。
未飽和root全体を $U\subseteq X$ とすると、matching辺は $Z_Y$ と $Z_X\setminus U$ の間に全単射を与えます。
また $X\setminus Z_X$ の頂点は全て飽和され、そのmatching相手は $Y\setminus Z_Y$ にあります。従って $M$ は
- $Z_X\setminus U$ と $Z_Y$ の間の辺、
- $X\setminus Z_X$ と $Y\setminus Z_Y$ の間の辺
へ分かれます。ゆえに
$$
|M|=|Z_Y|+|X\setminus Z_X|=|C|.
$$
□
&&&
## Kőnigの定理
&&&thm Kőnigの定理 [33-thm-konig]
任意の有限二部グラフ $G$ に対して
$$
\nu(G)=\tau_v(G).
$$
すなわちmaximum matchingの辺数とminimum vertex coverの頂点数は等しい。
&&&
&&&prf [33-prf-konig]
maximum matching $M$ から前節の $C$ を作ると、$C$ はvertex coverで $|C|=|M|$ です。従って
$$
\tau_v(G)\le|C|=|M|=\nu(G).
$$
弱双対性は逆向きの不等式を与えるので等号です。構成した $C$ はminimum vertex coverです。□
&&&
証明は算法でもあります。「増加路」の反復augmenting算法でmaximum matchingを求め、最後の失敗探索で $Z_X,Z_Y$ を記録すれば、minimum vertex coverも同時に出力できます。
## 具体例
$$
X=\{a,b,c,d\},\qquad Y=\{1,2,3,4\}
$$
とし、辺を
$$
a1,\ a2,\ b1,\ b2,\ c2,\ c3,\ d3
$$
とします。matching $M=\{a1,b2,c3\}$ では $d$ が未飽和です。$d$ から交互探索すると
$$
d\to3\to c\to2\to b\to1\to a
$$
と到達します。従って
$$
Z_X=\{a,b,c,d\},\qquad Z_Y=\{1,2,3\}.
$$
未飽和な右頂点4へは辺がないのでaugmenting pathはありません。構成するcoverは
$$
C=(X\setminus Z_X)\cup Z_Y=\{1,2,3\}
$$
で、$|C|=3=|M|$ です。
## Hallの定理をKőnigから導く
「二部グラフとマッチング」ではHallの結婚定理を帰納法で証明しました。Kőnigの定理からは、最小coverを介した別証明が得られます。
&&&cor Hallの結婚定理の双対的証明 [33-cor-hall-from-konig]
有限二部グラフ $(X,Y)$ が全ての $S\subseteq X$ について
$$
|N(S)|\ge|S|
$$
を満たすなら、$X$ を飽和するmatchingをもつ。
&&&
&&&prf [33-prf-hall-from-konig]
$X$ を飽和するmatchingがないと仮定すると、Kőnigの定理により大きさ $|C|<|X|$ のvertex cover $C$ があります。
$S=X\setminus C$ と置きます。$S$ から出る辺は左端でcoverされていないため、右端が全て $C\cap Y$ に入ります。従って $N(S)\subseteq C\cap Y$ です。一方
$$
|N(S)|\le|C\cap Y|
=|C|-|C\cap X|
<|X|-|C\cap X|=|S|.
$$
これはHall条件に反します。従って $X$ を飽和するmatchingが存在します。□
&&&
帰納証明はHall条件の組合せ的な十分性を、Kőnig証明はmatchingとcoverの双対性を示します。
## Hall deficiencyの正確な公式
&&&thm Hall deficiency formula [33-thm-hall-deficiency]
有限二部グラフ $G=(X\sqcup Y,E)$ に対し
$$
\operatorname{def}(G)
=\max_{S\subseteq X}\bigl(|S|-|N(S)|\bigr)
$$
と置く。このとき
$$
\nu(G)=|X|-\operatorname{def}(G).
$$
&&&
&&&prf [33-prf-hall-deficiency]
任意のmatching $M$ と $S\subseteq X$ を考えます。$S$ 内で飽和できる頂点は、相異なる $N(S)$ の頂点へ対応するので高々 $|N(S)|$ 個です。従って
$$
|X|-|M|\ge |S|-|N(S)|.
$$
全ての $S$ で最大を取り、さらにmaximum matchingを選ぶと
$$
\nu(G)\le |X|-\operatorname{def}(G).
$$
逆向きを示します。maximum matching $M$ の未飽和 $X$ 頂点から交互探索し、到達集合を $Z_X,Z_Y$ とします。「増加路」から $N(Z_X)=Z_Y$ で、matchingは $Z_Y$ と、$Z_X$ から未飽和rootを除いた集合を全単射で結びます。未飽和root数は $|X|-|M|$ なので
$$
|Z_X|-|N(Z_X)|=|X|-|M|.
$$
従って $\operatorname{def}(G)\ge |X|-\nu(G)$ です。二つの不等式を合わせて公式を得ます。□
&&&
Hall条件は $\operatorname{def}(G)=0$ の場合です。この公式は、全員を割り当てられないとき最大何人まで可能かも答えます。
## independent setとの補関係
&&&def independent set [33-def-independent-set]
頂点集合 $I\subseteq V(G)$ で、$I$ 内の二頂点を結ぶ辺が存在しないものを[[独立集合 (グラフ理論)|independent set]]という。その最大頂点数を $\alpha(G)$ と書く。
&&&
&&&prop coverとindependent setの補関係 [33-prop-cover-independent-complement]
$C$ がvertex coverであることと $V(G)\setminus C$ がindependent setであることは同値である。従って
$$
\alpha(G)+\tau_v(G)=|V(G)|.
$$
&&&
&&&prf [33-prf-cover-independent-complement]
$C$ がcoverなら、補集合内の二頂点を結ぶ辺は両端ともcover外となるため存在しません。逆に補集合がindependentなら、任意の辺の少なくとも一端が $C$ に属するので $C$ はcoverです。
補集合を取る操作が大きさ $k$ のcoverと大きさ $|V|-k$ のindependent setを対応させるため、最小と最大の間に等式が成り立ちます。□
&&&
Kőnigの定理と合わせると、二部グラフでは
$$
\alpha(G)=|V(G)|-\nu(G)
$$
です。
## edge coverとの関係
&&&def edge cover [33-def-edge-cover]
辺集合 $F\subseteq E(G)$ が[[辺被覆|edge cover]]であるとは、全ての頂点が $F$ の少なくとも一本の辺の端点になっていることをいう。孤立頂点をもつグラフにはedge coverは存在しない。最小edge coverの辺数を $\rho(G)$ と書く。
&&&
&&&thm Gallaiのedge cover公式 [33-thm-edge-cover-formula]
孤立頂点をもたない有限グラフ $G$ に対して
$$
\rho(G)=|V(G)|-\nu(G).
$$
&&&
&&&prf [33-prf-edge-cover-formula]
maximum matching $M$ を取ります。$M$ で未飽和な各頂点 $v$ について接続辺を一本選び、$M$ へ加えます。未飽和二頂点を結ぶ辺は存在しません。もしあれば $M$ に追加できるからです。従って各追加辺は未飽和頂点を一つずつ新たに覆い、得るedge coverの辺数は
$$
|M|+(|V|-2|M|)=|V|-\nu(G).
$$
よって $\rho(G)\le |V|-\nu(G)$ です。
逆にminimum edge cover $F$ を取り、包含についても極小にします。$(V,F)$ はcycleをもちません。cycle辺を一本除いても全cycle頂点が覆われるからです。また四頂点path $a-b-c-d$ を含めば、中央辺 $bc$ を除いても $b$ は $ab$、$c$ は $cd$ に覆われ、極小性に反します。
従って $(V,F)$ の各連結成分はstarです。各starから辺を一本選ぶとmatchingになります。成分数を $k$ とするとこのmatchingは $k$ 辺です。star forestでは
$$
|F|=|V|-k
$$
なので $\nu(G)\ge k=|V|-|F|$、すなわち $|F|\ge|V|-\nu(G)$ です。両不等式から公式を得ます。□
&&&
この公式は一般グラフで成立し、二部性を必要としません。
## 0--1行列とrook
$m\times n$ の0--1行列で、1の位置を二部グラフの辺とみなします。行を $X$、列を $Y$ とすると、同じ行・列を共有しない1の選択はmatching、全ての1を覆う行・列の選択はvertex coverです。
Kőnigの定理により、置けるrookの最大個数は、全ての1を覆うために選ぶ行・列の最小本数と一致します。
## 演習
&&&exc minimum coverを確認する [33-exc-construct-cover]
本文の具体例で $C=\{1,2,3\}$ が全辺を覆うことを確認し、大きさ2のcoverが存在しないことをmatchingから証明せよ。
&&&
&&&prf 解答 [33-prf-construct-cover-answer]
全ての辺の右端は1,2,3のいずれかなので $C$ はcoverです。一方 $M=\{a1,b2,c3\}$ は3辺のmatchingです。弱双対性により任意のvertex coverは少なくとも3頂点必要です。従って大きさ2のcoverは存在せず、$C$ はminimumです。□
&&&
&&&exc 三角形で等号が壊れる [33-exc-triangle-gap]
三角形 $K_3$ について $\nu(K_3)$ と $\tau_v(K_3)$ を求めよ。
&&&
&&&prf 解答 [33-prf-triangle-gap-answer]
matchingは二辺を同時に選べないので $\nu(K_3)=1$ です。一頂点だけでは反対側の辺を覆えず、任意の二頂点なら全辺を覆うので $\tau_v(K_3)=2$ です。従って等号は成立しません。三角形は二部グラフでないためKőnig定理の仮定外です。□
&&&
&&&exc deficiencyを計算する [33-exc-compute-deficiency]
二部グラフで
$$
N(a)=N(b)=N(c)=\{1,2\},\qquad N(d)=\{2,3\}
$$
とする。$\operatorname{def}(G)$ とmaximum matchingの大きさを求めよ。
&&&
&&&prf 解答 [33-prf-compute-deficiency-answer]
$S=\{a,b,c\}$ では不足が $3-2=1$、全体 $X$ でも近傍が $\{1,2,3\}$ なので不足は $4-3=1$ です。他の集合の不足は1以下なので $\operatorname{def}(G)=1$。従って
$$
\nu(G)=|X|-1=3.
$$
実際 $a1,b2,d3$ が大きさ3のmatchingです。□
&&&
&&&exc independent setを求める [33-exc-independent-via-matching]
偶cycle $C_8$ のmatching numberとindependence numberを求めよ。
&&&
&&&prf 解答 [33-prf-independent-via-matching-answer]
交互の四辺を選ぶperfect matchingがあるので $\nu(C_8)=4$ です。二部グラフなので
$$
\alpha(C_8)=|V|-\nu(C_8)=8-4=4.
$$
実際、一つおきの四頂点がindependent setです。□
&&&
&&&exc minimum edge cover [33-exc-minimum-edge-cover]
六頂点path $P_6$ と五頂点cycle $C_5$ のminimum edge cover数を求め、具体例を書け。
&&&
&&&prf 解答 [33-prf-minimum-edge-cover-answer]
$P_6$ は辺12,34,56からなるperfect matchingをもつので $\nu=3$、従って $\rho=6-3=3$ です。この三辺がedge coverです。
$C_5$ のmaximum matchingは2辺なので $\rho=5-2=3$。例えば辺12,34,45が全頂点を覆います。□
&&&
&&&exc rookとline cover [33-exc-rook-line-cover]
$$
\begin{pmatrix}
1&1&0&0\\
0&1&1&0\\
0&0&1&1
\end{pmatrix}
$$
の1の位置に、同じ行・列を共有しないrookを最大何個置けるか。また全ての1を覆う行・列の最小本数を求めよ。
&&&
&&&prf 解答 [33-prf-rook-line-cover-answer]
位置 $(1,1),(2,2),(3,3)$ にrookを置けば3個です。行が三つなので4個は不可能です。Kőnigの定理によりminimum line cover数も3で、例えば全三行を選べば実現します。□
&&&
## 本章で得たもの
matchingは実行可能な割当、vertex coverはそれ以上の割当が不可能であることを示す上界証明書です。二部グラフでは交互探索から両者を同じ大きさで構成でき、Kőnigの等式が成立します。
同じ双対性から、Hallの別証明、最大不足と未割当数の一致、independent set、edge cover、rook配置が一つの枠組みに入りました。


3-3 HallとKőnig

> **前提知識**：グラフ彩色、平面双対
> 
## 六色から五色へ減らす壁
simple planar graphには次数5以下の頂点があるので、低次数頂点を一つ削って帰納的に彩色すれば六色で塗れます。しかし五色で同じことをすると、削除した頂点 $v$ の次数が5で、その五近傍が五色を全て使っている場合に止まります。
五色定理の工夫は、既存の彩色を固定しないことです。二色だけを使う連結成分では、その二色を丸ごと交換してもproper coloringは壊れません。ある交換ができなければ、その二色pathが平面を分離し、別の交換が必ずできることを証明します。
## 二色部分graphとKempe chain
&&&def bichromatic subgraph and Kempe chain [39-def-kempe-chain]
proper coloring
$$
\varphi:V(G)\longrightarrow\{1,\ldots,q\}
$$
と相異なる二色 $a,b$ に対して、色が $a$ または $b$ の頂点が誘導する部分graphを
$$
G[a,b]
$$
と書き、[[二色誘導部分グラフ]]という。
$G[a,b]$ の一つの連結成分を $a$--$b$ Kempe componentといい、その中のpathを[[Kempe鎖|Kempe chain]]という。
&&&
proper coloringなので、$G[a,b]$ の各辺は色 $a$ と色 $b$ の頂点を結びます。従ってKempe chain上では二色が交互に現れます。
&&&lemma Kempe swap lemma [39-lem-kempe-swap]
proper coloring $\varphi$ の一つの $a$--$b$ Kempe component $K$ 上で、色 $a$ と $b$ を交換し、他の頂点の色を変えない。この操作後もproper coloringである。
&&&
&&&prf [39-prf-kempe-swap]
辺 $xy$ を任意に取ります。
両端が $K$ の外なら色は変わりません。両端が $K$ 内なら、元の色は $a,b$ の異なる二色であり、両方を交換しても異なるままです。
ちょうど一端 $x$ が $K$ 内だとします。交換後の $x$ の色は $a$ または $b$ です。もし外側の端 $y$ が同じ色なら、$y$ も色 $a$ または $b$ であり、辺 $xy$ によって $x$ と同じ $G[a,b]$ の連結成分へ入ります。これは $y\notin K$ に反します。
従ってどの辺の両端も同色にならず、交換後もproperです。□
&&&
&&&example path成分の色を反転する [39-ex-kempe-path-swap]
色1と色3の誘導部分graphにpath
$$
x_0-x_1-x_2-x_3
$$
があり、色が順に $1,3,1,3$ だとします。この成分全体で交換すると $3,1,3,1$ になります。
重要なのはpathの一部だけでなく連結成分全体を交換することです。一部だけを変えると、切れ目の辺で同色が隣り合う可能性があります。
&&&
## 次数5以下の頂点
&&&lemma planar low-degree lemma [39-lem-planar-low-degree]
頂点数3以上のsimple planar graphには次数5以下の頂点が存在する。
&&&
&&&prf [39-prf-planar-low-degree]
本巻第5章のEuler公式から
$$
|E|\le3|V|-6.
$$
従って平均次数は
$$
\frac{1}{|V|}\sum_{v\in V}\deg(v)
=\frac{2|E|}{|V|}
\le6-\frac{12}{|V|}
<6.
$$
全頂点次数が6以上なら平均も6以上となるので矛盾します。従って次数5以下の頂点があります。□
&&&
この補題は六色定理と五色定理の共通の入口です。違いは、次数がちょうど5で五色全てが近傍に現れたときの処理にあります。
## 近傍の巡回順と分離
plane embeddingで頂点 $v$ の十分小さい円周を考えると、$v$ に接続する辺が円周を横切る順序が定まります。次数5なら隣接頂点を
$$
v_1,v_2,v_3,v_4,v_5
$$
と巡回順に名付けられます。
&&&lemma alternating neighbours separation [39-lem-alternating-neighbours-separation]
simple plane graphで、頂点 $v$ の相異なる四近傍
$$
v_1,v_2,v_3,v_4
$$
がこの巡回順に現れるとする。$G-v$ に、内部で $v_2,v_4$ を通らない $v_1$--$v_3$ path $P$ があるとき、
$$
P\cup vv_1\cup vv_3
$$
は単純閉曲線を含み、その曲線の局所的に反対側へ $v_2,v_4$ が位置する。
特に、$G-v$ にある $v_2$--$v_4$ pathが $P$ と頂点を共有しないことは不可能である。
&&&
&&&prf [39-prf-alternating-neighbours-separation]
$P$ をsimple pathとして取ります。$P$ は $v$ を含まず、辺 $vv_1,vv_3$ は $v$ 以外で互いにも $P$ にも交わりません。従って
$$
C=vv_1\cup P\cup v_3v
$$
は単純cycleで、plane embedding上の単純閉曲線です。
$v$ の十分小さい円周上で、$vv_1,vv_2,vv_3,vv_4$ はこの順に横切ります。閉曲線 $C$ は円周を $vv_1$ と $vv_3$ の位置で横切るため、$vv_2$ の短い始部分と $vv_4$ の短い始部分は $C$ の異なる側にあります。辺は $C$ を横切れないので、頂点 $v_2,v_4$ も $C$ の異なる側にあります。
$G-v$ の $v_2$--$v_4$ pathは、一方の側から他方へ移るため、本巻第5章の交互端点定理により $C$ と交わらなければなりません。$v$ はpathに含まれず、plane graphの辺同士は内部で交差しないので、交点は $P$ 上の頂点です。従って $P$ と頂点非共有な $v_2$--$v_4$ pathは存在しません。□
&&&
この補題が「一方のKempe chainが存在すれば、交互位置のもう一方は存在できない」という排他性を与えます。
## 平面五色定理
&&&thm five-color theorem [39-thm-five-color]
全てのloopless planar graphは5-colorableである。すなわち
$$
\chi(G)\le5.
$$
&&&
&&&prf [39-prf-five-color]
平行辺は頂点彩色条件を変えないので一本にまとめ、simple graphとしてよいです。頂点数 $n=|V(G)|$ について帰納します。
$n\le5$ なら、各頂点へ異なる色を与えて高々5色で塗れます。
$n\ge6$ とし、plane embeddingを一つ固定します。low-degree lemmaにより次数5以下の頂点 $v$ を取れます。帰納法から $G-v$ は色集合 $\{1,2,3,4,5\}$ でproperに塗れます。
$\deg(v)\le4$ なら、近傍が使う色は高々4色なので、使われていない色を $v$ へ与えられます。$\deg(v)=5$ でも、五近傍が使う色が4色以下なら同じです。
残る場合、$v$ は相異なる五近傍をもち、それらが五色を一度ずつ使っています。plane embeddingにおける巡回順に
$$
v_1,v_2,v_3,v_4,v_5
$$
と名付け、色名を付け替えて
$$
\varphi(v_i)=i
\qquad(1\le i\le5)
$$
としてよいです。
$G-v$ の二色部分graph $G[1,3]$ を考えます。$v_1$ と $v_3$ が異なるKempe componentに属するなら、$v_1$ を含む成分だけで色1と3を交換します。Kempe swap lemmaによりproper coloringは保たれ、$v$ の近傍から色1が消えます。そこで $v$ を色1にすれば彩色を拡張できます。
従って、残るのは $v_1,v_3$ が同じ1--3 Kempe componentに属する場合です。この成分内にsimple $v_1$--$v_3$ path $P_{13}$ があります。
次に $G[2,4]$ を考えます。もし $v_2,v_4$ が同じ2--4 Kempe componentに属するなら、内部が色2または4だけからなるsimple path $P_{24}$ があります。色集合が互いに素なので $P_{13}$ と $P_{24}$ は頂点を共有しません。しかし近傍は
$$
v_1,v_2,v_3,v_4
$$
の巡回順にあり、alternating neighbours separation lemmaはそのような二pathの共存を禁止します。矛盾です。
従って $v_2,v_4$ は異なる2--4 Kempe componentに属します。$v_2$ を含む成分だけで色2と4を交換すると、proper coloringを保ったまま $v$ の近傍から色2が消えます。$v$ を色2にして彩色を拡張できます。
全ての場合に $G-v$ の5-coloringを $G$ へ拡張できました。帰納法により全planar graphは5-colorableです。□
&&&
証明は「1--3交換ができる」か、「できないため1--3 pathがあり、その分離によって2--4交換ができる」かの完全な二分法です。
## 手でKempe交換を実行する
&&&example 五近傍が五色を使う局面 [39-ex-five-neighbour-recolor]
頂点 $v$ の近傍が巡回順に $v_1,\ldots,v_5$ で、それぞれ色1から5を使うとします。
- $v_1,v_3$ が1--3成分でつながらなければ、$v_1$ 側の成分をswapし、$v$ を色1にする。
- つながるなら1--3 pathが平面を分離するので、$v_2,v_4$ は2--4成分でつながらない。$v_2$ 側をswapし、$v$ を色2にする。
どちらの場合も、既彩色頂点の色数を増やさず、局所的な連結成分探索だけで一色を空けます。
&&&
## 構成算法として読む
証明は彩色を実際に作ります。
1. 現在のplanar graphから次数5以下の頂点を削除し、stackへ積む。
2. graphが空になったら、stackを逆順に戻す。
3. 戻す頂点の近傍色が4色以下なら空いた色を使う。
4. 五色全てが現れたら、二色誘導部分graphを探索してKempe componentを交換する。
各Kempe componentはBFSまたはDFSで見つかります。単純に毎回graph全体を探索しても多項式時間で5-coloringを構成できます。高速な実装ではplane embeddingのrotationと動的な色成分管理を用いますが、本章の証明にそのデータ構造は必要ありません。
## なぜ同じ議論で四色定理にならないか
四色を使う帰納法では、次数5の頂点の五近傍が四色を使う局面が生じます。一色が二回現れるため、一見すると交換しやすそうです。しかし複数のKempe chainが同時に存在し、ある交換で一色を空けようとすると別の隣接頂点へ同じ色が移る場合があります。
五色証明では、五近傍が全て異色なので
$$
\{1,3\}\cap\{2,4\}=\varnothing
$$
となり、二本の候補pathが頂点を共有できません。この明確な分離が四色の場合にはそのまま残りません。
歴史的にもKempeは四色定理を同様の交換で証明したと考えましたが、複数chainの相互作用に穴がありました。五色定理では上の二chainだけで完全な排他性が成立するため、議論は正しいです。四色定理にはさらに強い構造解析とreducible configurationが必要です。
## face coloringとdual
連結plane graph $H$ のface coloringは、dual graph $H^*$ のvertex coloringです。従って $H^*$ がloopをもたない、すなわち $H$ がbridgeをもたない場合、五色定理から $H$ の面を高々五色で塗れます。
bridgeがあるとdualにloopができ、通常のproper vertex coloringは不可能です。しかしbridgeは同じ面を両側にもつため、地図彩色ではその辺を国境として異色を要求しません。bridgeを無視したdualのsimple化を塗れば、やはり五色の面彩色を得られます。
## 演習
&&&exc Kempe swapを辺ごとに確認する [39-exc-check-kempe-swap]
色redとblueの一つのKempe componentだけで二色を交換する。component外との境界辺で同色衝突が起こらない理由を説明せよ。
&&&
&&&prf 解答 [39-prf-check-kempe-swap-answer]
境界辺 $xy$ で $x$ がcomponent内、$y$ が外だとします。交換後の $x$ と $y$ が同色になるなら、$y$ の色もredまたはblueです。すると $xy$ はred--blue誘導部分graphの辺であり、$y$ は $x$ と同じ連結成分へ入るはずです。これは $y$ がcomponent外という仮定に反します。従って境界で衝突しません。□
&&&
&&&exc 近傍色が重複する場合 [39-exc-repeated-neighbour-color]
次数5の頂点 $v$ を削除して5-coloringしたところ、その近傍色が
$$
1,2,3,4,4
$$
だった。Kempe交換を使わずに彩色を拡張せよ。
&&&
&&&prf 解答 [39-prf-repeated-neighbour-color-answer]
近傍では色5が使われていません。従って $v$ を色5にすれば、全ての隣接頂点と異なる色になりproper coloringが得られます。Kempe交換が必要なのは五近傍が五色を一度ずつ使う場合だけです。□
&&&
&&&exc 二本のKempe pathの排他性 [39-exc-exclusive-kempe-paths]
$v$ の近傍 $v_1,v_2,v_3,v_4$ が巡回順にあり、色がそれぞれ1,2,3,4である。$G-v$ に1--3 pathがあるなら、2--4 pathが存在しないことを示せ。
&&&
&&&prf 解答 [39-prf-exclusive-kempe-paths-answer]
1--3 path $P_{13}$ と二辺 $vv_1,vv_3$ は単純閉曲線を作り、巡回順から $v_2,v_4$ はその反対側にあります。2--4 pathがあればこの曲線を横切る必要があります。
pathは $v$ を使わず、plane embeddingの辺は内部で交差しないので、交点は $P_{13}$ の頂点でなければなりません。しかし1--3 pathの頂点色は1または3、2--4 pathでは2または4なので頂点共有は不可能です。従って2--4 pathは存在しません。□
&&&
&&&exc 五色証明の帰納法 [39-exc-five-color-induction]
五色定理の証明で、削除頂点 $v$ の次数が0から4の場合と、次数5だが近傍色が重複する場合を一つの条件でまとめよ。
&&&
&&&prf 解答 [39-prf-five-color-induction-answer]
共通条件は「$v$ の近傍で使われている色が高々4色」であることです。次数4以下なら近傍頂点数自体が4以下なのでこの条件を満たします。次数5でも色が重複すれば異なる近傍色数は4以下です。
いずれも五色のうち少なくとも一色が近傍で未使用なので、その色を $v$ へ与えれば帰納的彩色を拡張できます。□
&&&
&&&exc wheelを五色以下で塗る [39-exc-color-wheel]
奇cycle $C_{2m+1}$ に中心頂点を加えたwheelをproperに彩色し、その彩色数を求めよ。
&&&
&&&prf 解答 [39-prf-color-wheel-answer]
奇cycleは3色必要で、3色で塗れます。中心はrimの全頂点と隣接するため、その3色のどれも使えず第四色が必要です。従ってwheelは4-colorableであり、
$$
\chi(W_{2m+2})=4.
$$
これは平面graphで五色上界が常に鋭いわけではないことを示します。□
&&&
&&&exc dualによる面彩色 [39-exc-dual-face-coloring]
bridgeをもたない連結plane graphの面が高々五色でproperに塗れることを、dualと五色定理から証明せよ。
&&&
&&&prf 解答 [39-prf-dual-face-coloring-answer]
「平面双対」から、bridgeに対応するdual edgeだけがloopです。元graphにbridgeがないのでdual $G^*$ はloopless planar graphです。五色定理により $G^*$ の頂点を高々五色でproperに塗れます。
$G^*$ の頂点は元graphの面で、dualで隣接する二頂点は元graphで辺を共有する二面です。従ってdual頂点の色を対応する面へ移せば、辺を共有する面が異色となる五色面彩色を得ます。□
&&&
## 本章で得たもの
五色定理は、低次数頂点を削る退化度の方法に、彩色を動かすKempe swapを加えたものです。次数5の頂点で五色が全て塞がれても、
- 1--3 chainがなければ1と3を交換する。
- 1--3 chainがあれば平面分離により2--4 chainはなく、2と4を交換する。
という二分法で必ず一色を空けられます。抽象的な「連結成分で二色を交換する」操作と、平面上の「交互端点を結ぶpathは同時に存在できない」という幾何が組み合わさった証明です。


6-3 平面グラフの五色定理

> **前提知識**：同型・部分グラフ・補グラフ
> 
## 辺に長さ1を与える
交通網で二地点がつながっているかだけでなく、最短で何本の道路を通るかを知りたいことがあります。単純graphの各辺に長さ1を与え、pathの辺数を長さとすれば、最短path長が頂点間の距離になります。
距離を導入すると、「最も遠い頂点まで何歩か」「graph全体で最大何歩か」「最悪距離を最小にする拠点はどこか」を正確に定義できます。
## graph距離
&&&def graph距離とgeodesic [05-def-graph-distance-geodesic]
連結graph $G$ の頂点 $u,v$ に対し、$u$ から $v$ へのpathの長さの最小値を
$$
d_G(u,v)
$$
と書き、[[グラフ距離|graph距離]]という。
長さが $d_G(u,v)$ に等しい $u$–$v$ pathを[[測地路 (グラフ理論)|geodesic]]または[[最短路|最短path]]という。
&&&
有限連結graphでは $u$–$v$ pathが少なくとも一つ存在し、その長さは非負整数です。従って長さの集合には最小値があり、定義は正当です。
同じ頂点にとどまる長さ0のpathを許すので $d_G(u,u)=0$ です。異なる頂点間の距離は少なくとも1です。
&&&thm graph距離はmetric [05-thm-graph-distance-is-metric]
連結graph $G$ で、任意の $u,v,w\in V(G)$ に対して次が成り立つ。
1. $d_G(u,v)\ge0$ であり、$d_G(u,v)=0$ と $u=v$ は同値。
2. $d_G(u,v)=d_G(v,u)$。
3. 三角不等式
   $$
   d_G(u,w)\le d_G(u,v)+d_G(v,w).
   $$
&&&
&&&prf [05-prf-graph-distance-is-metric]
path長は非負整数であり、長さ0のpathは始点と終点が同じ場合に限るので1が従います。
無向graphでは $u$–$v$ pathを逆順にたどれば同じ長さの $v$–$u$ pathになります。最短値を両方向で比較すれば2を得ます。
最短 $u$–$v$ pathと最短 $v$–$w$ pathを続けると、$u$ から $w$ へのwalkが得られ、その長さは
$$
d_G(u,v)+d_G(v,w)
$$
です。このwalkが頂点を繰り返すなら、その間の閉じた部分を削除すると、より短いか同じ長さの $u$–$w$ pathが得られます。最短 $u$–$w$ pathの長さはその長さ以下なので三角不等式が従います。□
&&&
## 同型は距離を保存する
&&&prop graph同型はisometry [05-prop-graph-isomorphism-isometry]
$\varphi:G\to H$ が連結graph間の同型なら
$$
d_H(\varphi(u),\varphi(v))
=d_G(u,v)
$$
がすべての $u,v\in V(G)$ で成り立つ。
&&&
&&&prf [05-prf-graph-isomorphism-isometry]
長さ $k$ の $u$–$v$ pathは、同型により長さ $k$ の $\varphi(u)$–$\varphi(v)$ pathへ移ります。従って
$$
d_H(\varphi(u),\varphi(v))
\le d_G(u,v).
$$
逆同型 $\varphi^{-1}$ に同じ議論を適用すると逆向きの不等式を得るため、等号です。□
&&&
## 離心率・半径・直径・中心
&&&def 離心率・半径・直径 [05-def-eccentricity-radius-diameter]
有限連結graph $G$ の頂点 $v$ の[[離心率 (グラフ理論)|離心率]]を
$$
\operatorname{ecc}_G(v)
=\max_{u\in V(G)}d_G(v,u)
$$
と定める。
$G$ の[[半径 (グラフ理論)|半径]]と[[直径 (グラフ理論)|直径]]を
$$
\operatorname{rad}(G)
=\min_{v\in V(G)}\operatorname{ecc}_G(v),
$$
$$
\operatorname{diam}(G)
=\max_{v\in V(G)}\operatorname{ecc}_G(v)
=\max_{u,v\in V(G)}d_G(u,v)
$$
と定める。
離心率が半径に等しい頂点全体を[[グラフの中心|中心]]、離心率が直径に等しい頂点全体を周辺という。
&&&
有限集合上の最大・最小なので、これらは必ず存在します。
### 基本例
- 完全graph $K_n$、$n\ge2$：すべての相異なる頂点間距離が1なので、半径も直径も1、全頂点が中心。
- path $P_n$：直径は $n-1$。中央の一頂点、または中央の隣接二頂点が中心。
- cycle $C_n$：各頂点の離心率は $\lfloor n/2\rfloor$。従って全頂点が中心で、半径と直径はともに $\lfloor n/2\rfloor$。
- star $K_{1,m}$、$m\ge2$：中心頂点の離心率は1、葉の離心率は2。半径1、直径2。
&&&thm 半径と直径の不等式 [05-thm-radius-diameter-inequality]
有限連結graph $G$ に対して
$$
\operatorname{rad}(G)
\le\operatorname{diam}(G)
\le2\operatorname{rad}(G).
$$
&&&
&&&prf [05-prf-radius-diameter-inequality]
半径は離心率の最小値、直径は最大値なので
$$
\operatorname{rad}(G)\le\operatorname{diam}(G)
$$
です。
中心頂点 $c$ を一つ取り、任意の $u,v$ に三角不等式を使うと
$$
\begin{aligned}
d_G(u,v)
&\le d_G(u,c)+d_G(c,v)\\
&\le\operatorname{ecc}(c)+\operatorname{ecc}(c)\\
&=2\operatorname{rad}(G).
\end{aligned}
$$
すべての $u,v$ について最大を取れば
$$
\operatorname{diam}(G)\le2\operatorname{rad}(G)
$$
を得ます。□
&&&
左の等号は完全graphやcycleで、右の等号はstarや奇数個の頂点をもつpathで起こります。
## 距離層
&&&def 距離層と球 [05-def-distance-layers-balls]
頂点 $s$ と整数 $i\ge0$ に対し
$$
L_i(s)=\{v\in V(G)\mid d_G(s,v)=i\}
$$
を $s$ からの第 $i$ [[距離層]]という。
$$
B_r(s)=\{v\in V(G)\mid d_G(s,v)\le r\}
$$
を半径 $r$ の[[球 (グラフ理論)|閉球]]という。
&&&
&&&prop 辺は距離層を一段より多く飛ばない [05-prop-edges-between-distance-layers]
$uv\in E(G)$ なら
$$
|d_G(s,u)-d_G(s,v)|\le1.
$$
&&&
&&&prf [05-prf-edges-between-distance-layers]
$s$ から $u$ への最短pathの後に辺 $uv$ を加えると、$s$ から $v$ への長さ $d(s,u)+1$ のwalkが得られます。従って
$$
d(s,v)\le d(s,u)+1.
$$
$u,v$ を交換して
$$
d(s,u)\le d(s,v)+1
$$
も得ます。二式を合わせれば主張が従います。□
&&&
従って辺は同じ層の内部、または隣り合う二層の間にしかありません。「幅優先探索と深さ優先探索」のbreadth-first searchは、$L_0,L_1,L_2,\ldots$ を順に発見することで最短距離を計算します。
## 非連結graphの補graph
距離は連結graphで定義しましたが、補graphを取ると非連結性が強い連結性へ変わります。
&&&prop 非連結graphの補graph [05-prop-complement-of-disconnected-connected]
$G$ が二頂点以上をもつ非連結graphなら、$\overline G$ は連結で
$$
\operatorname{diam}(\overline G)\le2.
$$
&&&
&&&prf [05-prf-complement-of-disconnected-connected]
相異なる頂点 $u,v$ を取ります。
$u,v$ が $G$ の異なる連結成分に属するなら、$G$ では隣接しません。従って $\overline G$ では隣接し
$$
d_{\overline G}(u,v)=1.
$$
$u,v$ が同じ成分に属するなら、非連結性から別の成分の頂点 $w$ を取れます。$G$ では $uw,vw$ のどちらも辺でないため、$\overline G$ では
$$
u-w-v
$$
が長さ2のpathです。従って任意の二頂点間距離は高々2で、$\overline G$ は連結かつ直径高々2です。□
&&&
この命題から、$G$ と $\overline G$ が同時に非連結になることはありません。
## 木では最遠点は葉
木の中心構造を調べる準備をします。
&&&lemma 木の最遠点は葉 [05-lem-tree-farthest-vertex-leaf]
二頂点以上をもつ木 $T$ で、頂点 $x$ から最も遠い頂点 $y$ は葉である。
&&&
&&&prf [05-prf-tree-farthest-vertex-leaf]
$x$ から $y$ へのpathは木のpath一意性によりただ一つです。$y$ が葉でないと仮定すると、$y$ にはpath上で $y$ の直前にある頂点以外の隣接頂点 $z$ があります。
木にcycleはないので $z$ は $x$–$y$ path上にはありません。従って一意な $x$–$z$ pathは $x$–$y$ pathへ辺 $yz$ を加えたもので
$$
d_T(x,z)=d_T(x,y)+1.
$$
これは $y$ が最遠であることに矛盾します。ゆえに $y$ は葉です。□
&&&
最長pathの両端も葉です。一方の端から見て、もう一方へさらに延ばせないことからも分かります。
## 葉を同時に剥がす
$T$ の全葉を削除して得る誘導部分graphを $T^\circ$ と書きます。
&&&lemma 葉削除後も木 [05-lem-tree-leaf-pruning]
$T$ が3頂点以上の木なら、$T^\circ$ は空でない木である。
&&&
&&&prf [05-prf-tree-leaf-pruning]
木には少なくとも二つの葉がありますが、3頂点以上ならすべての頂点が葉になることはありません。従って少なくとも一頂点が残ります。
$T^\circ$ は木の部分graphなのでcycleをもちません。残った二頂点 $u,v$ を取ります。$T$ の一意な $u$–$v$ pathの内部頂点は、path上で二つの隣接頂点をもつため $T$ の葉ではありません。端点 $u,v$ も残った頂点です。従ってpath全体が $T^\circ$ に残り、$u,v$ は $T^\circ$ で結ばれます。ゆえに $T^\circ$ は連結で、木です。□
&&&
&&&lemma 葉削除と離心率 [05-lem-tree-pruning-eccentricity]
$T$ が3頂点以上の木で、$x\in V(T^\circ)$ なら
$$
\operatorname{ecc}_T(x)
=\operatorname{ecc}_{T^\circ}(x)+1.
$$
また $T$ の葉は中心ではない。
&&&
&&&prf [05-prf-tree-pruning-eccentricity]
補題により、$x$ から最遠の頂点 $\ell$ は $T$ の葉です。$\ell$ の隣接頂点を $y$ とすると、3頂点以上の木では $y$ は葉でなく $T^\circ$ に残ります。従って
$$
\operatorname{ecc}_T(x)
=d_T(x,\ell)
=d_{T^\circ}(x,y)+1
\le\operatorname{ecc}_{T^\circ}(x)+1.
$$
逆に、$T^\circ$ で $x$ から最遠の頂点 $z$ を取ります。$T^\circ$ が一頂点だけなら、その頂点 $z=x$ は元の木で少なくとも一つの葉と隣接しています。
$T^\circ$ が二頂点以上なら、$T^\circ$ 内で $x$ から最遠の $z$ は $T^\circ$ の葉です。$z$ は $T$ では葉でないため、$T^\circ$ での唯一の隣接頂点以外に、削除された葉 $\ell$ と隣接しています。どちらの場合も
$$
d_T(x,\ell)
=d_{T^\circ}(x,z)+1
=\operatorname{ecc}_{T^\circ}(x)+1.
$$
従って逆向きの不等式も成り立ち、離心率の式を得ます。
最後に $T$ の葉 $\ell$ とその隣接頂点 $y$ を取ります。$\operatorname{ecc}_T(\ell)\ge2$ です。$\ell$ 以外の任意の頂点 $z$ へのpathは $y$ を通るので
$$
d_T(y,z)=d_T(\ell,z)-1.
$$
また $d_T(y,\ell)=1$ です。従って
$$
\operatorname{ecc}_T(y)
=\operatorname{ecc}_T(\ell)-1
<\operatorname{ecc}_T(\ell).
$$
葉は離心率を最小化しないため中心ではありません。□
&&&
## 木の中心定理
&&&thm 木の中心 [05-thm-tree-center]
有限木の中心は、ちょうど一頂点、または互いに隣接する二頂点からなる。
全葉を同時に削除する操作を繰り返すと、最後に残る一頂点または一辺の両端が中心である。
&&&
&&&prf [05-prf-tree-center]
1頂点の木ではその頂点が中心です。2頂点の木では両頂点の離心率が1で、二頂点とも中心です。
3頂点以上の木 $T$ では、直前の補題により葉は中心でありません。従って中心候補はすべて $T^\circ$ にあります。また $x\in T^\circ$ について
$$
\operatorname{ecc}_T(x)
=\operatorname{ecc}_{T^\circ}(x)+1
$$
なので、$T$ で離心率を最小にする頂点と $T^\circ$ で離心率を最小にする頂点は同じです。すなわち
$$
\operatorname{Center}(T)
=\operatorname{Center}(T^\circ).
$$
葉削除のたびに頂点数は減り、残るgraphは木なので、この操作は有限回で1頂点または2頂点になるまで続きます。中心は各段階で変わらないため、最後に残る頂点集合が元の木の中心です。2頂点残る場合、残ったgraphは連結な木なので二頂点は隣接しています。□
&&&
&&&cor 木の直径の中央 [05-cor-tree-diameter-midpoint]
木 $T$ の直径が偶数なら中心は一頂点、奇数なら中心は隣接二頂点である。任意の直径pathの中央が中心である。
&&&
&&&prf [05-prf-tree-diameter-midpoint]
二頂点以上の木で最長pathの両端は葉です。全葉を一度削除すると、最長pathの両端が一つずつ削られ、その内部に長さ $\operatorname{diam}(T)-2$ のpathが $T^\circ$ に残ります。従って
$$
\operatorname{diam}(T^\circ)\ge\operatorname{diam}(T)-2.
$$
$T^\circ$ が一頂点だけなら、$T$ の全頂点はその一頂点またはそれに隣接する葉です。$T$ は3頂点以上なので異なる葉が二つあり、直径は2です。従ってこの場合は
$$
\operatorname{diam}(T^\circ)=0=\operatorname{diam}(T)-2.
$$
$T^\circ$ が二頂点以上なら、その直径pathの両端は $T^\circ$ の葉です。各端点は $T$ では葉でないため、削除された葉と少なくとも一つ隣接しています。両端でその葉を一つずつ付けると、$T$ に長さ $\operatorname{diam}(T^\circ)+2$ のpathが得られます。従って
$$
\operatorname{diam}(T)\ge\operatorname{diam}(T^\circ)+2.
$$
二つの不等式を合わせ、3頂点以上では
$$
\operatorname{diam}(T^\circ)
=\operatorname{diam}(T)-2.
$$
この操作を繰り返すと、直径が偶数なら長さ0の一頂点へ、奇数なら長さ1の一辺へ到達します。木の中心定理により最後に残る頂点が中心であり、元の任意の直径pathから両端を同数ずつ削った中央と一致します。□
&&&
## 演習
&&&exc pathとcycleの距離 [05-exc-distance-path-cycle]
$P_8$ と $C_9$ の半径、直径、中心を求めよ。
&&&
&&&prf 解答 [05-prf-distance-path-cycle-answer]
$P_8$ の端点間距離は7で、これが直径です。中央の二頂点は端点までの最大距離が4で、他の頂点はそれより大きい離心率をもちます。従って
$$
\operatorname{diam}(P_8)=7,\qquad
\operatorname{rad}(P_8)=4,
$$
中心は第4・第5頂点です。
$C_9$ では各頂点から最遠の頂点までの距離は $\lfloor9/2\rfloor=4$ です。従って
$$
\operatorname{rad}(C_9)
=\operatorname{diam}(C_9)=4,
$$
全9頂点が中心です。□
&&&
&&&exc 半径と直径の組 [05-exc-distance-radius-diameter-examples]
次の各組 $(r,d)$ をもつ連結graphを一つずつ与えよ。
1. $(1,1)$
2. $(1,2)$
3. $(2,3)$
4. $(2,4)$
&&&
&&&prf 解答 [05-prf-distance-radius-diameter-examples-answer]
1は $K_2$。半径・直径とも1です。
2は3頂点以上のstar。中心の離心率1、葉どうしの距離2です。
3は $P_4$。中央二頂点の離心率2、端点間距離3です。
4は $P_5$。中央頂点の離心率2、端点間距離4です。□
&&&
&&&exc 距離層の辺 [05-exc-distance-layer-edges]
頂点 $s$ からの距離層を $L_i$ とする。$L_i$ と $L_j$ の間に辺があり得る $i,j$ の条件を求め、$|i-j|\ge2$ なら辺がないことを証明せよ。
&&&
&&&prf 解答 [05-prf-distance-layer-edges-answer]
$u\in L_i$、$v\in L_j$ が隣接するとします。距離層の命題から
$$
|d(s,u)-d(s,v)|=|i-j|\le1.
$$
従って辺があり得るのは $i=j$ または $|i-j|=1$ の場合だけです。特に $|i-j|\ge2$ なら辺は存在しません。□
&&&
&&&exc 非連結graphの補 [05-exc-distance-disconnected-complement]
$G=K_3\cup K_2$ とする。$\overline G$ を同定し、その直径と半径を求めよ。
&&&
&&&prf 解答 [05-prf-distance-disconnected-complement-answer]
元の各成分内では全頂点が隣接するので、補graphでは成分内に辺がありません。異なる二成分間には元の辺がないので、補graphではすべての交差辺があります。従って
$$
\overline G=K_{3,2}.
$$
異なる側の頂点間距離は1、同じ側の相異なる頂点間距離は2です。各側に少なくとも二頂点あるため全頂点の離心率は2で
$$
\operatorname{rad}(\overline G)
=\operatorname{diam}(\overline G)=2.
$$
□
&&&
&&&exc 木の中心を葉削除で求める [05-exc-distance-tree-center-pruning]
頂点集合
$$
\{a,b,c,d,e,f,g\}
$$
と辺
$$
ab,\ bc,\ cd,\ de,\ cf,\ fg
$$
をもつ木の中心、半径、直径を求めよ。
&&&
&&&prf 解答 [05-prf-distance-tree-center-pruning-answer]
最初の葉は $a,e,g$ です。これらを削除すると、残る辺は
$$
bc,\ cd,\ cf
$$
で、中心 $c$ と葉 $b,d,f$ からなるstarです。さらに $b,d,f$ を削除すると $c$ だけが残ります。従って中心は $\{c\}$ です。
$c$ から最遠の葉 $a,e,g$ までの距離はいずれも2なので半径は2です。葉 $a$ から $e$、または $a$ から $g$、$e$ から $g$ の距離は4なので直径は4です。□
&&&
&&&exc 自己同型と中心 [05-exc-distance-automorphism-preserves-center]
連結graph $G$ の自己同型が中心集合を自分自身へ写すことを証明せよ。頂点推移graphでは全頂点が中心であることを導け。
&&&
&&&prf 解答 [05-prf-distance-automorphism-preserves-center-answer]
自己同型 $\varphi$ は距離を保存します。従って
$$
\begin{aligned}
\operatorname{ecc}(\varphi(v))
&=\max_{w\in V(G)}d(\varphi(v),w)\\
&=\max_{u\in V(G)}d(\varphi(v),\varphi(u))\\
&=\max_{u\in V(G)}d(v,u)\\
&=\operatorname{ecc}(v).
\end{aligned}
$$
二行目では $\varphi$ が全単射なので $w=\varphi(u)$ と書けることを使いました。離心率が半径に等しいという性質が保存されるため、中心集合は自分自身へ写ります。
頂点推移graphでは、一つの中心頂点を任意の頂点へ送る自己同型があります。中心性が保存されるので任意の頂点が中心です。□
&&&

1-2 距離・直径・中心

5-3 平面双対

1-3 切断点・橋・ブロック

## 切る数と通る道の数
有限単純グラフの二頂点 $s,t$ が連結とは道で結べること。$s,t$ と異なる頂点集合を除くと両者が非連結になるなら、その集合を頂点切断という。互いに内部頂点を共有しない $s$–$t$ 道の最大本数と、最小頂点切断の大きさは等しい。ただしここでは $s,t$ が非隣接の場合を述べる。
**Mengerの定理の証明経路。** 第4章の整数最大流最小切断を使う。各内部頂点 $v$ を入側・出側へ分け、間の有向辺の容量を1にする。元の各無向辺には両方向に十分大きい整数容量、例えば頂点数 $n$ を与える。$s,t$ は分割しない。非隣接なので他の頂点全てを除けば両者は離れ、容量 $<n$ の切断がある。従って最小切断に大容量の辺は含まれず、その容量は削除すべき内部頂点の個数になる。整数最大流を道へ分解すれば、各内部頂点を一度しか使わない道が同じ本数だけ得られる。逆向きに、$k$ 本の内部頂点素な道を切るには少なくとも $k$ 個の頂点が必要。□
## 例と境界
四角形の向かい合う二頂点の間には内部頂点を共有しない二道があり、二つの中間頂点を除くと切れる。隣接頂点間には内部頂点のない辺があるため、上の頂点切断の表現をそのまま用いない。
**演習。** 長さ3の道 $s-a-b-t$ の $s,t$ 間の頂点切断最小数を求めよ。
**解答。** $a$ または $b$ の一頂点を除けば切れる。最小数は1。


1-4 Mengerの定理

5-4 平面性判定の構造

## 1　グラフと描画を区別する
グラフが**平面的**であるとは、辺を互いに交差しない弧として平面へ描けることをいう。一つの描画を固定したものを**平面グラフ**という。交差する描画が一つあっても、別の描画で交差が消えることがある。例えば $K_4$ は四角形と二本の対角線として描くと交差するが、一頂点を三角形の内部へ置けば平面的である。
本章のEuler計算は、辺を有限本の線分で描き、辺内部同士や辺内部と頂点が交わらない有限単純平面グラフを対象とする。頂点数を $V$、辺数を $E$、補集合の連結成分である面の数を $F$ とし、非有界な外面も数える。グラフの連結成分数は $c$ と書く。
## 2　Euler公式と橋
**定理。** 有限連結単純平面グラフでは
$$V-E+F=2\tag{1}$$
**証明。** 閉路上の辺を一つ消すとグラフは連結のままである。閉路は単純閉折れ線であり、その辺の両側は異なる面に属する。辺を消すとこの二面が合流するので $E,F$ が各1減る。閉路がなくなるまで続けると木になり、その補集合は一つの面である。木では $E=V-1,F=1$ だから式 (1) が成立する。単純閉折れ線の二側が異なる根拠と木の補集合の迂回は、折れ線に対するJordan曲線定理による。□
連結でない場合は $V-E+F=1+c$ となる。異なる二成分を既存の辺に交わらない弧で結ぶと、辺だけが1増えて面数は変わらない。この操作を $c-1$ 回行えば連結になるから、式 (1) から一般式が出る。孤立頂点も一成分として数える。
**橋**は消すと連結成分数が増える辺である。橋を渡った面境界は、同じ辺の両側をたどることがある。面境界で辺が現れた回数を、向きを区別した境界歩道の長さとして数える。連結平面グラフでは各辺の両側の出現を足して
$$\sum_{f}\deg(f)=2E\tag{2}$$
橋を一度しか数えないと式 (2) を誤る。例えば三頂点の道では $V=3,E=2,F=1$ で、唯一の面の境界歩道の長さは4である。
## 3　辺数評価と非平面性
連結な単純平面グラフで $V\ge3$ のとき、各面の境界歩道の長さは少なくとも3である。橋は同じ辺を往復するが、三頂点以上の連結単純グラフでは一面全体の境界歩道が長さ2で終わることはない。従って式 (2) から $3F\le2E$。式 (1) と合わせて
$$E\le3V-6\tag{3}$$
$K_5$ なら $V=5,E=10$ だが右辺は9なので、どの描画も平面埋め込みにはならない。
二部グラフでは三角形の面境界がない。連結な単純二部平面グラフで $V\ge3$ なら各面の境界歩道の長さは少なくとも4であり、$4F\le2E$。よって
$$E\le2V-4\tag{4}$$
$K_{3,3}$ は $V=6,E=9$ で右辺は8だから非平面である。この評価は二部性を使う。$K_5$ に式 (4) を適用してはならない。
これらは非平面性の**十分な証拠**であるが、式 (3)・(4) を満たせば平面的になるという逆向きの判定ではない。辺の分割は $V,E$ を同数ずつ増やしてEuler値を変えず、非平面性を保つこともある。Kuratowski定理の「非平面なら $K_5$ または $K_{3,3}$ の分割を含む」という向きの証明は、「平面性判定の構造」で行う。
## 4　平面双対を作る
連結な平面グラフの各面に双対頂点を一つ置き、元の各辺を横切る双対辺を、その両側の面の双対頂点の間に引く。この**平面双対**では、元の面数が双対の頂点数、元の辺数が双対の辺数になる。元の橋の両側は同じ面なので、対応する双対辺はループになる。双対に平行辺が生じることもあるため、単純グラフに限定して双対を考えてはならない。
例えば一つの三角形の平面描画には内面と外面の二つがあり、双対は二頂点の間に平行な三辺をもつ。元の三角形は $(V,E,F)=(3,3,2)$、双対は $(2,3,3)$ で、いずれもEuler値は2である。
## 5　交互端点の道は同じ側で交差する
有限折れ線に対するJordan曲線定理には、次の直接の帰結がある。単純閉折れ線 $C$ の内側の点と外側の点を結ぶ連続道は $C$ と交わる。もし交わらなければ道の像は $\mathbb R^2\setminus C$ の連結部分集合なのに、その二成分の点をともに含むことになる。
**交互端点定理。** $C$ 上の相異なる四点 $a,c,b,d$ がこの巡回順に並ぶとする。$a$ と $b$ を結ぶ単純折れ線弧 $P$、$c$ と $d$ を結ぶ単純折れ線弧 $Q$ があり、両弧の内部は $C$ と交わらず、かつ $C$ の内側または外側の**同じ**成分に入る。このとき $P\cap Q\ne\varnothing$ である。
**証明。** $C$ の $a$ から $b$ への二つの境界弧のうち $c$ を通る方を $A_1$、$d$ を通る方を $A_2$ とする。$J=P\cup A_1$ は単純閉折れ線である。$P,Q$ の内部が入る $C$ の成分を $U$、他方を $U'$ とする。$J$ は $U'$ と交わらない。折れ線Jordan曲線定理の交差偶奇 $\varepsilon_J$ は連結な $U'$ 上で一定であり、その値を $k$ と書く。
$c$ の小さい近傍では $J$ は $A_1\subset C$ と一致する。境界辺を横切ると交差偶奇が反転するから、$Q$ 上で $c$ に十分近い内部点 $c'$ は $\varepsilon_J(c')=1-k$ を満たす。$c$ が頂点でも、境界頂点の局所扇形内では同じ値になる。一方、$d\notin J$ なので $d$ の十分小さい近傍では $\varepsilon_J$ は両側とも $k$ である。$Q$ 上で $d$ に近い内部点 $d'$ では $\varepsilon_J(d')=k$。もし $Q$ が $J$ を避ければ、連結な $Q$ 上で局所定数な $\varepsilon_J$ は一定になり矛盾する。従って $Q$ は $J$ と交わる。$Q$ の内部は $C$ と交わらず、端点 $c,d$ も $J$ にないから、交点は $A_1$ でなく $P$ 上にある。□
この定理により、平面グラフの一つの閉路 $C$ に四つのattachmentが交互に並ぶ二本の道は、共通頂点や辺の交差なしに**同じ面側**へ置けない。二本の道を内側と外側に分ければ、定理の「同じ側」という仮定は満たされない。
## 6　演習と解答
**演習1。** 立方体のグラフの $V,E,F$ を求めよ。
**解答。** $V=8,E=12$。式 (1) から $F=2-8+12=6$。六つの正方形面を数える結果と一致する。
**演習2。** 四頂点の道と三頂点の道を離して描いたときの $V,E,F,c$ とEuler値を求めよ。
**解答。** $(V,E,F,c)=(7,5,1,2)$ で $V-E+F=3=1+c$。二つの木を離しても外面は一つである。
**演習3。** $K_{3,3}$ に一辺を分割する次数2頂点を一つ加えたグラフが、式 (3) だけでは非平面と判定できないことを確かめよ。
**解答。** 新しいグラフは $V=7,E=10$ で $10\le3\cdot7-6=15$。ただし分割した辺を縮めて元に戻せば $K_{3,3}$ が得られるので、この描画は平面的にならない。式 (3) の逆は成り立たない。
**演習4。** 正方形の境界上に $a,b,c,d$ をこの巡回順に取る。$a$–$b$ と $c$–$d$ を正方形の同じ内側で、交差しない折れ線で結ぶ例を説明せよ。
**解答。** $a$–$b$ をその間の短い境界弧に近い内側の折れ線で結び、$c$–$d$ も離れた境界弧に近い内側の折れ線で結ぶ。二本を十分細く離して選べば交わらない。端点は交互順ではないので定理に反しない。
**演習5。** 平面グラフの閉路 $C$ 上に $a,c,b,d$ がこの順にあり、内部頂点を共有しない二本の道がそれぞれ $a$–$b$ と $c$–$d$ を結ぶ。両道を閉路の同じ側へ描けない理由を述べよ。
**解答。** 同じ側で、かつ各道の内部が $C$ と交わらなければ交互端点定理により二道が交わる。内部頂点を共有しないので交点は辺の内部で起こり、平面描画に反する。従ってそのような同じ側の描画はできない。


5-5 Euler公式と非平面性の判定

頂点と辺だけからなる有限グラフを対象に、同型・部分グラフ・距離といった基本概念から始め、連結性（切断点・橋・ブロック・Mengerの定理）、木と最小全域木、二部グラフのマッチング（Hall・Kőnig）、ネットワーク流と最大流最小切断定理、平面グラフのEuler公式とKuratowskiの定理、グラフ彩色と五色定理、Euler閉路とHamilton閉路、極値問題の入口（Mantelの定理）、幅優先・深さ優先探索を学ぶ。各章は「障害を最小の量で測る」という双対性（最大と最小が一致する定理）を軸にまとめ、証明を省かずに読めるようにした。前提は集合と写像、数学的帰納法、および線形代数の初歩である。