Kőnig–Egerváryの定理

同義語:König–Egerváryの定理Kőnig–Egerváry theoremKönig–Egerváry theoremKönigの定理(グラフ理論)

概要

Kőnig–Egerváryの定理(Kőnig–Egerváry theorem)とは、有限二部グラフにおいて最大マッチングの大きさが最小頂点被覆の大きさに等しいという定理である。0-1 行列では独立な 1 の最大個数が 1 を覆う行と列の最小本数に等しいという形になり、非負整数の行列では置換に沿った成分の和の最大値が、行と列の非負整数の重みで成分を上から押さえるときの重みの和の最小値に等しい(Egerváry の形)。最大マッチングから交互道で最小頂点被覆を作ることで証明でき、Frobenius–König の定理や Hall の結婚定理が系として従う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 二部グラフ, マッチング(グラフ理論)

Kőnig–Egerváry の定理(Kőnig–Egerváry theorem)は、有限二部グラフにおいて、端点を共有しない辺の最大本数(最大マッチングの大きさ)が、すべての辺に触れる頂点の最小個数(最小頂点被覆の大きさ)に等しいという定理である。0 と 1 を成分とする行列の言葉では、「どの 2 つも同じ行・同じ列にない 1 の最大個数は、すべての 1 を覆う行と列の最小本数に等しい」となる。さらに成分が非負整数の行列では、置換に沿った成分の和の最大値が、行と列に付けた非負整数の重みで成分を上から押さえるときの重みの和の最小値に等しい(Egerváry の形)。
「マッチングは被覆より大きくなれない」という不等式は自明であり、定理の中身は等号が必ず達成されることにある。等号を与える被覆は、最大マッチングが本当に最大であることの証明書になる。この型の「最大の詰め込み=最小の障害」は、Hallの結婚定理、最大流最小カット定理、Mengerの定理、Dilworthの定理、線形計画法の双対定理と同じ系列に属する。
この記事では、最大マッチングから交互道をたどって最小頂点被覆を作る構成的な証明を述べ、行列の形と Egerváry の重み付きの形を証明する。重み付きの形は、グラフの形から「重みを 1 ずつ下げる」議論で導く。応用として、行列のどの置換の項も 0 になる条件(Frobenius–König の定理)と Hall の条件を導き、二部性などの仮定を外すと等号が成り立たない例を挙げる。

名前と分担

「König の定理」とよばれる結果は複数ある。基数の和と積の不等式(無限基数 $\kappa$ について $\kappa< \kappa^{\operatorname{cf}\kappa}$ を導く)は Königの定理、無限の木に無限の道があるという主張は Königの補題、二部グラフの辺彩色数が最大次数に等しいという主張は Königの辺彩色定理 である。この記事の主題はそれらと別の、二部グラフの最小最大定理である。なお KP17 は行列の形を「König's lemma」とよんでいる(Lemma 3.2.5、p. 62)が、Königの補題 とは別の主張である。
同じ等式 $\nu=\tau$ は、マッチング(グラフ理論) の記事で Hall の条件から、最大流最小カット定理 の記事で最大流の整数性から証明されている。この記事の証明はそれらと独立で、最大マッチングが与えられれば最小頂点被覆を直接書き下せる。

定義

以下、$G=(V,E)$ を有限二部グラフとし、二部分割を $(A,B)$ とする(各辺は $A$ の頂点と $B$ の頂点を結ぶ)。$A$ の頂点を $a,a'$、$B$ の頂点を $b,b'$ のように書く。

マッチングと頂点被覆
  1. 辺の集合 $M\subseteq E$ で、どの 2 辺も端点を共有しないものを マッチング という。その最大の大きさを $\nu(G)$ と書く。
  2. 頂点の集合 $U\subseteq V$ で、すべての辺が少なくとも 1 つの端点を $U$ にもつものを 頂点被覆 という。その最小の大きさを $\tau(G)$ と書く。
  3. マッチング $M$ について、$A$ の頂点 $a$ で $M$ のどの辺の端点でもないものから出発し、$M$ に属さない辺と $M$ に属する辺を交互にたどる道を $M$ 交互道 という。長さ $0$ の道(出発点だけ)も含める。

$M$ 交互道は $A$ から出発するので、$B$ の頂点へは $M$ に属さない辺で入り、$A$ の頂点へは $M$ に属する辺で入る。

0-1 行列の独立な 1 と線による被覆

$m\times n$ 行列 $H=(h_{ij})$ の成分がすべて $0$ か $1$ とする。行と列をまとめて 線 という。成分が $1$ の位置の集合で、どの 2 つも同じ線にないものを 独立な 1 の集合という。線の集合で、成分が $1$ のすべての位置がそのどれかの線に含まれるものを 線による被覆 という。

主定理

弱い不等式

任意のマッチング $M$ と任意の頂点被覆 $U$ について $|M|\le|U|$ である。とくに $\nu(G)\le\tau(G)$ である。

証明を開く

$M$ の各辺は $U$ に端点をもつ。各辺にその端点のうち $U$ に属するものを 1 つ対応させると、$M$ の辺は端点を共有しないので、この対応は単射である。$\square$

Kőnig–Egerváry の定理

有限二部グラフ $G$ について $\nu(G)=\tau(G)$ である。さらに、最大マッチング $M$ が与えられると、次の集合 $U$ は大きさ $|M|$ の頂点被覆である:$M$ の各辺 $ab$($a\in A$、$b\in B$)について、ある $M$ 交互道が $b$ で終わるなら $b$ を、そうでなければ $a$ を選んで集めたもの。

交互道で届く側を選ぶ

$M$ を最大マッチングとし、$U$ を主張のとおりに作る。$M$ の各辺から 1 頂点ずつ選んだので $|U|=|M|$ である。lem-ke-weak により、$U$ が頂点被覆であることを示せば $\tau(G)\le|M|=\nu(G)\le\tau(G)$ となり、定理が従う。
まず、$M$ 交互道が $B$ の頂点 $b$ で終わるなら、$b$ は $M$ のある辺の端点であり、その辺について $U$ は $b$ を選んでいることを示す。$b$ が $M$ のどの辺の端点でもないとすると、その交互道 $P$ は $M$ に属さない辺で始まり $M$ に属さない辺で終わり、両端がどちらも $M$ の辺の端点でない。$M$ と $P$ の辺の集合の対称差 $M'$ をとると、$P$ の内部の頂点では $M$ の辺と $P$ のもう 1 本の辺が入れ替わるだけで、両端では $P$ の辺が 1 本加わるだけなので、$M'$ はマッチングである。$P$ の辺は $M$ に属さないものが 1 本多いので $|M'|=|M|+1$ となり、$M$ の最大性に反する。よって $b$ は $M$ のある辺 $a_0b$ の端点で、$b$ で終わる交互道があるので、$U$ の作り方により $b\in U$ である。
次に、任意の辺 $ab\in E$($a\in A$、$b\in B$)が $U$ に端点をもつことを示す。$a\in U$ ならよいので $a\notin U$ とする。上で示したことから、$b$ で終わる $M$ 交互道を作れば $b\in U$ が従う。

  • $a$ が $M$ のどの辺の端点でもないとき:$a$ から辺 $ab$ をたどる道は $M$ 交互道で、$b$ で終わる($ab\notin M$ である)。
  • $a$ が $M$ の辺 $ab'$ の端点であるとき:$b'=b$ なら、$U$ はこの辺から $a$ か $b$ を選んでおり、$a\notin U$ なので $b\in U$ である。$b'\ne b$ とする。$a\notin U$ なので、$U$ は辺 $ab'$ から $b'$ を選んでおり、$b'$ で終わる $M$ 交互道 $P$ がある。$P$ が $b$ を通るなら、$P$ を $b$ で切った道が $b$ で終わる交互道である。$P$ が $b$ を通らないとき、$P$ に続けて $M$ の辺 $b'a$ と辺 $ab$ をたどる。$a$ は $P$ に現れない。実際、$P$ の出発点は $M$ の辺の端点でない頂点なので $a$ ではなく、$P$ の途中で $A$ の頂点には $M$ の辺で入るので、$a$ に入るなら $b'$ から入るが、$b'$ は $P$ の最後の頂点である。よってこの道は $M$ 交互道で、$b$ で終わる。
    いずれの場合も $b\in U$ であり、$U$ は頂点被覆である。$\square$
証明の所在と由来

この証明は Die25 Theorem 2.1.1(p. 39)の証明を、細部を補って書き直したものである。同書は定理を König(1931)に帰し、章末の注(pp. 59–60)で、König の定理が Menger の定理の二部グラフの場合にあたることを述べている。

被覆の作り方

$A=\{a_1,a_2,a_3,a_4\}$、$B=\{b_1,b_2,b_3,b_4\}$ で、辺が $a_1b_1,a_1b_2,a_2b_1,a_3b_2,a_3b_3,a_3b_4,a_4b_2$ の二部グラフを考える。$a_1,a_2,a_4$ の隣接する頂点は合わせて $b_1,b_2$ の 2 つだけなので、この 3 頂点すべてを同時にマッチングの端点にはできず、$M=\{a_2b_1,a_3b_3,a_4b_2\}$ が最大マッチングで $\nu=3$ である。
$M$ の辺の端点でない $A$ の頂点は $a_1$ だけである。$a_1$ からの交互道は $a_1b_1a_2$ と $a_1b_2a_4$ で、$a_2,a_4$ からは $M$ に属さない辺が出ていないので、交互道が終わる $B$ の頂点は $b_1,b_2$ である。よって $U$ は、辺 $a_2b_1$ から $b_1$、辺 $a_4b_2$ から $b_2$、辺 $a_3b_3$ から $a_3$ を選んだ $\{b_1,b_2,a_3\}$ で、確かにすべての辺を覆い、大きさは $3=\nu$ である。

行列の形

0-1 行列の形

成分が $0$ か $1$ の $m\times n$ 行列 $H$ について、独立な 1 の最大個数は、線による被覆の最小本数に等しい。

行の集合 $A=\{r_1,\dots,r_m\}$ と列の集合 $B=\{c_1,\dots,c_n\}$ を頂点とし、$h_{ij}=1$ のとき $r_i$ と $c_j$ を辺で結ぶ二部グラフ $G_H$ を作る。成分が $1$ の位置の集合が独立であることは、対応する辺の集合が端点を共有しないこと、すなわちマッチングであることと同じである。線の集合が成分 $1$ の位置をすべて含むことは、対応する頂点の集合がすべての辺に触れること、すなわち頂点被覆であることと同じである。よって thm-ke-main から主張が従う。$\square$

ex-ke-construct のグラフの行列は、行を $a_1,\dots,a_4$、列を $b_1,\dots,b_4$ として
$$ H=\begin{pmatrix}1&1&0&0\\1&0&0&0\\0&1&1&1\\0&1&0&0\end{pmatrix} $$
である。$(2,1),(3,3),(4,2)$ 成分の 3 つの 1 は独立で、第 1 列・第 2 列・第 3 行の 3 本の線がすべての 1 を覆う。

Egerváry の重み付きの形

成分が非負の $n\times n$ 行列 $W=(w_{ij})$ と置換 $\sigma\in S_n$ について、$w(\sigma):=\sum_iw_{i\sigma(i)}$ を $\sigma$ の重みという。行と列の重みの組 $(u,v)$($u,v\in\mathbb Z^n$)が $W$ の 被覆 であるとは、すべての $i,j$ で $u_i+v_j\ge w_{ij}$ となることをいう。

Egerváry の定理(整数の場合)

$W$ を成分が非負整数の $n\times n$ 行列とする。このとき
$$ \max_{\sigma\in S_n}w(\sigma)=\min\Bigl\{\sum_iu_i+\sum_jv_j\Bigm|(u,v)\text{ は }W\text{ の被覆で }u,v\in\mathbb Z_{\ge0}^n\Bigr\} $$
であり、右辺の最小値は存在する。

重みを 1 ずつ下げる

被覆 $(u,v)$ と置換 $\sigma$ について $w(\sigma)\le\sum_i(u_i+v_{\sigma(i)})=\sum u+\sum v$ なので、左辺は右辺以下である。
符号を問わない整数の被覆を考える。$u_i:=\max_jw_{ij}$、$v:=0$ は被覆なので被覆は存在し、どの被覆の和も $\max_\sigma w(\sigma)$ 以上の整数なので、和が最小の整数の被覆 $(u,v)$ がとれる。$u_i+v_j=w_{ij}$ となる $(i,j)$ だけを辺とする、行と列の二部グラフ $T$ を考える。
$T$ が完全マッチング、すなわち置換 $\sigma$ で $u_i+v_{\sigma(i)}=w_{i\sigma(i)}$(すべての $i$)となるものをもたないと仮定する。thm-ke-main により $T$ は大きさ $\nu(T)< n$ の頂点被覆 $K$ をもつ。$K$ に含まれる行の集合を $R$、列の集合を $C$ とし、
$$ u'_i:=\begin{cases}u_i&(i\in R)\\u_i-1&(i\notin R)\end{cases},\qquad v'_j:=\begin{cases}v_j+1&(j\in C)\\v_j&(j\notin C)\end{cases} $$
とおく。$(u',v')$ は被覆である。実際、$i\in R$ なら $u'_i+v'_j\ge u_i+v_j$ であり、$i\notin R$、$j\in C$ なら $u'_i+v'_j=u_i+v_j$ である。$i\notin R$、$j\notin C$ なら、$K$ は $T$ の頂点被覆なので $(i,j)$ は $T$ の辺でなく、$u_i+v_j\ge w_{ij}+1$(整数)であり、$u'_i+v'_j=u_i+v_j-1\ge w_{ij}$ である。和は $|C|-(n-|R|)=|K|-n< 0$ だけ変わるので、$(u,v)$ の最小性に反する。
したがって $T$ は完全マッチング $\sigma$ をもち、$w(\sigma)=\sum u+\sum v$ である。最後に符号を直す。$c:=\min_iu_i$ をとる番号を $i_0$ とし、$u'':=u-c$、$v'':=v+c$ とおくと、和は変わらず被覆のままで、$u''\ge0$ であり、$v''_j=v_j+u_{i_0}\ge w_{i_0j}\ge0$ である。よって非負整数の被覆で和が $w(\sigma)$ のものがあり、左辺は右辺以上である。$\square$

成分がすべて $0$ か $1$ で $u,v$ も $0$ か $1$ に限ると、被覆は線による被覆にあたる。成分が非負の実数の行列と実数の被覆についても同じ等式が成り立ち、KP17 Theorem 17.1.1(p. 299)はその形を述べて証明している。同書の注(p. 309)は、この定理が Egerváry(1931)によって証明され、Kuhn の割当問題の算法(ハンガリー法)につながったと述べている。費用を最小にする形の同じ双対定理とハンガリー法は 割当問題 の記事にある。

降下の 1 段

$$ W=\begin{pmatrix}3&1&2\\2&2&0\\1&3&2\end{pmatrix} $$
とする。各行の最大値をとった $u=(3,2,3)$、$v=(0,0,0)$ は和 $8$ の被覆である。等号の成り立つ位置は $(1,1),(2,1),(2,2),(3,2)$ で、第 1 列と第 2 列の 2 本ですべて覆えるので、完全マッチングはない。prf-ke-egervary の操作で $R=\emptyset$、$C=\{1,2\}$ として、$u=(2,1,2)$、$v=(1,1,0)$、和 $7$ を得る。今度は等号の位置に $(1,1),(2,2),(3,3)$ があり、恒等置換の重みは $3+2+2=7$ である。よって最大値は $7$ である(置換 $1\mapsto3,2\mapsto1,3\mapsto2$ の重み $2+2+3$ も $7$)。

成分が $0,1,2$ の $3\times3$ 行列 $3^9=19683$ 個すべてについて、置換の最大値、非負整数の被覆の最小値、上の降下の手順で得た値の 3 つが一致することを計算機で確かめた。

系

Frobenius–König の定理

成分が $0$ か $1$ の $n\times n$ 行列 $H$ について、次は同値である。

  1. どの置換 $\sigma$ についても、$h_{1\sigma(1)},\dots,h_{n\sigma(n)}$ のどれかが $0$ である。
  2. $H$ は、$r+s=n+1$ となる $r$ 個の行と $s$ 個の列が交わる位置の成分がすべて $0$ の小行列($r\times s$ の零小行列)をもつ。
証明を開く

2 ⇒ 1:零小行列の行の集合を $R$、列の集合を $C$ とする。置換 $\sigma$ は $R$ の $r$ 個の行を相異なる列へ送るが、$C$ の外の列は $n-s=r-1$ 個しかないので、ある $i\in R$ で $\sigma(i)\in C$ となり、$h_{i\sigma(i)}=0$ である。

1 ⇒ 2:1 は独立な 1 が $n$ 個ないことと同じである。thm-ke-matrix により、$p$ 個の行と $q$ 個の列で $p+q\le n-1$ のものがすべての 1 を覆う。残りの $n-p$ 個の行と $n-q$ 個の列が交わる位置はどの線にも含まれないので、成分はすべて $0$ である。$r:=n-p\ge1$、$s:=n+1-r=p+1$ とおくと、$p+q\le n-1$ より $s\le n-q$ なので、残りの列から $s$ 個を選べば $r\times s$ の零小行列が得られる。$\square$

1 は、$H$ の permanent(行列式の符号をすべて $+$ にしたもの。行和による上界は Bregmanの定理)が $0$ であることと同じである。ex-ke-construct の行列 $H$ では、被覆に使わない第 1・2・4 行と第 3・4 列が $3\times2$ の零小行列をなし、$3+2=5=n+1$ である。

Hall の条件の十分性

すべての $S\subseteq A$ について $|N(S)|\ge|S|$($N(S)$ は $S$ の頂点に隣接する頂点の集合)なら、$A$ のすべての頂点を端点にもつマッチングが存在する。

証明を開く

最小頂点被覆 $K$ をとり、$S:=A\setminus K$ とおく。$S$ の頂点から出る辺は $K$ に端点をもつので、その $B$ 側の端点は $K\cap B$ に属し、$N(S)\subseteq K\cap B$ である。よって $\tau(G)=|K\cap A|+|K\cap B|\ge(|A|-|S|)+|N(S)|\ge|A|$ である。thm-ke-main から $\nu(G)\ge|A|$ で、マッチングの辺はそれぞれ $A$ の頂点を 1 つずつ含むので、大きさ $|A|$ のマッチングは $A$ のすべての頂点を端点にもつ。$\square$

ほかにも、孤立点のない二部グラフで最大独立集合の大きさが最小の辺被覆の本数に等しいこと(独立集合 の記事)、二重確率行列が置換行列の凸結合であること(Birkhoff–von Neumann の定理、Hallの結婚定理 の記事)が、同じ最小最大の構造から出てくる。

計算の手順

thm-ke-main の証明は、最大マッチングと最小頂点被覆を同時に求める手順を与える。

  1. 空のマッチング $M$ から始める。
  2. $M$ の辺の端点でない $A$ の頂点すべてから、$M$ 交互道を幅優先にたどる($B$ の頂点へは $M$ に属さない辺で、$A$ の頂点へは $M$ の辺で進む)。
  3. $M$ の辺の端点でない $B$ の頂点に着いたら、その道で $M$ を入れ替えて 1 本増やし、2 に戻る。
  4. 着かなければ $M$ は最大である。証明のとおり、$M$ の各辺から「交互道で届く $B$ の頂点」か、届かなければ $A$ の頂点を選ぶと、最小頂点被覆が得られる。
    入れ替えは高々 $\min(|A|,|B|)$ 回で、各回の探索は辺の本数に比例する時間で済む。部集合の大きさ $(a,b)$ が $a,b\le3$ のすべての二部グラフと、$3\times4$・$4\times4$ のすべての二部グラフ(合わせて 70314 個)について、この手順の被覆が大きさ $\nu$ の頂点被覆になること、$a,b\le3$ では全数で求めた $\tau$ とも一致することを確かめた。

反例の表

外す条件例成り立たなくなること
グラフが二部グラフ三角形 $K_3$$\nu=\tau$($\nu=1$、$\tau=2$)
辺が 2 頂点を結ぶ(グラフ)3 部 3 一様ハイパーグラフ $\{a_1b_1c_1,a_1b_2c_2,a_2b_1c_2,a_2b_2c_1\}$$\nu=\tau$($\nu=1$、$\tau=2$)
成分が整数(Egerváry の形)$1\times1$ 行列 $(1/2)$整数の被覆で等号(最大 $1/2$、整数の被覆の最小 $1$)
零小行列の大きさ $r+s=n+1$$2\times2$ 単位行列の $1\times1$ の零小行列($r+s=2$)「零小行列があれば置換の項はすべて 0」
反例の確認

1 行目:$K_3$ のどの 2 辺も端点を共有するので $\nu=1$ である。1 頂点はその頂点に接する 2 辺しか覆わないので $\tau=2$ である。この例は辺が 2 頂点を結ぶグラフなので、外れている条件は二部性だけである。
2 行目:ハイパーグラフの辺(3 頂点の集合)のマッチングを「どの 2 辺も交わらない辺の集合」、頂点被覆を「すべての辺と交わる頂点の集合」と定める。4 つの辺はどの 2 つも 1 頂点を共有する(たとえば $a_1b_1c_1$ と $a_2b_2c_1$ は $c_1$ を共有する)ので $\nu=1$ である。各頂点はちょうど 2 つの辺に含まれるので、1 頂点では 4 辺を覆えず $\tau=2$ である。頂点は $a,b,c$ の 3 部に分かれ、各辺は各部から 1 頂点ずつとるので、二部グラフの「部に分かれる」性質は保っている。
3 行目:置換は 1 つで重みは $1/2$ である。整数の被覆 $u_1+v_1\ge1/2$ の和は $1$ 以上だが、実数の被覆 $u_1=1/2$、$v_1=0$ なら和は $1/2$ で等号が成り立つ。整数性は、和が最小の被覆を 1 ずつ動かす議論に使っている。
4 行目:単位行列は $(1,2)$ 成分が $0$ の $1\times1$ 零小行列をもつが、恒等置換の項はすべて $1$ である。cor-ke-frobenius の 2 ⇒ 1 の証明は、$C$ の外の列が $r-1$ 個しかないことに $r+s=n+1$ を使っている。

成分が $0,1$ の $n\times n$ 行列すべて($n=2,3,4$)について、cor-ke-frobenius の 2 つの条件が一致することを計算機で確かめた。

関連項目

参考文献

[1]
[2]
Anna R. Karlin; Yuval Peres, Game Theory, Alive, 著者公開版(2016 年 12 月 13 日), American Mathematical Society, 2017, 著者公開版(2016 年 12 月 13 日)の番号と頁:Lemma 3.2.5(p. 62)、Theorem 17.1.1(p. 299)、Chapter 17 の Notes(p. 309)

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