图论与网络流理论 3. 匹配理论 1：匹配、最大匹配、完美匹配

匹配与最大匹配

匹配

G

$G$

是一个图，由

G

$G$

中不相邻的边组成的集合

M

$M$

称为

G

$G$

的一个

匹配

（matching）。对于匹配

M

$M$

中的每一条边

=

u

v

e=uv

$e = u v$

，称

u

$u$

和

v

$v$

被匹配

M

$M$

所匹配，是

M

$M$

饱和的

更为确切地说，
$M\subset E(G) M ⊂ E ( G ) ，且对 ∀ e i , e j ∈ M \forall e_i,e_j\in M ∀ e i , e j ∈ M ，若 e i e_i e i 和 e j e_j e j 不相同，则两条边不相邻$
图中的每一个顶点，要么

未被
一个图的匹配一般不唯一。特别地，
平凡图也有匹配（考虑边集为
$\varnothing ∅ ）$

最大匹配

图

G

$G$

中含边数最多的匹配

用
如果
任何图的完美匹配都是最大匹配

交错路、增广路

边在

M

$M$

和

(

G

)

−

M

E(G)-M

$E (G) - M$

中交替出现的路成为

交错路

。如果交错路的起点和终点都是

M

$M$

非饱和

的，则称其为一条

M

$M$

增广路

最大匹配的条件

M

$M$

是最大匹配的充分必要条件是：

G

$G$

中不存在

M

$M$

增广路

证明

必要性：

如果

M

$M$

是最大匹配，还有一条增广路

P

$P$

，就可以把

P

$P$

上所有不属于

M

$M$

的边构成集合

′

M’

$M^{'}$

，显然

′

M’

$M^{'}$

也是

G

$G$

中的一个匹配（边与边之间不相邻），而且比

M

$M$

多一条边。矛盾。

充分性：

如果

G

$G$

中不存在

M

$M$

增广路，设

M

$M$

不是最大匹配，另外存在一个匹配

′

M’

$M^{'}$

，使得

′

∣

|M’|>|M|

$∣ M^{'} ∣ > ∣ M ∣$

，令：

[

⊕

′

]

H=G[M\oplus M’]

$H = G [M \oplus M^{'}]$

其中

⊕

′

∪

′

−

∩

′

M\oplus M’=M\cup M’-M\cap M’

$M \oplus M^{'} = M \cup M^{'} - M \cap M^{'}$

，成为对称差，即在

M

$M$

或

′

M’

$M^{'}$

中却又不同时在两者之中。

H

$H$

即边集合

⊕

′

M\oplus M’

$M \oplus M^{'}$

导出的子图。

H

$H$

中的顶点的度，要么是

1

$1$

要么是

2

$2$

（可能与

M

$M$

或者

′

M’

$M^{'}$

中的一个或者两个关联），所以

H

$H$

的每一个连通分支，一定是

M

$M$

的边和

′

M’

$M^{'}$

的边交替出现的：

一个偶长度圈
一条路

由于

M

$M$

和

′

M’

$M^{'}$

边的数量不一样且有

′

∣

|M’|>|M|

$∣ M^{'} ∣ > ∣ M ∣$

，因此不可能全是偶长度圈，而且也一定存在一条路，这条路两端都是

′

M’

$M^{'}$

中的边。而这条路就是一条

M

$M$

增广路。矛盾。

在这里插入图片描述

完美匹配

奇分支

图

G

$G$

中含有奇数个顶点的连通分支称为

G

$G$

的奇分支。

G

$G$

的奇分支的个数使用

(

G

)

o(G)

$o (G)$

表示

完美匹配的条件

（Tutte定理）图

G

$G$

有完美匹配的充分必要条件是：对

S

⊂

V

(

G

)

\forall S\subset V(G)

$\forall S \subset V (G)$

，

(

G

−

S

)

≤

∣

S

∣

o(G-S)\le |S|

$o (G - S) \leq ∣ S ∣$

（其中

S

∣

|S|

$∣ S ∣$

为

S

$S$

所含顶点的个数）

证明

必要性：

设图

G

$G$

有完美匹配

M

$M$

，对于

⊂

\forall S\subset G

$\forall S \subset G$

，如果

−

G-S

$G - S$

没有奇分支，则结论显然成立。否则设

…

G_1,\dots ,G_k

$G_{1}, \dots, G_{k}$

是

−

G-S

$G - S$

的所有奇分支。

由于

M

$M$

是完美匹配，所以对于每一个奇分支，其中所有的顶点在

G

$G$

中都是饱和的。使其饱和的边可能在奇分支内部，也可能与

S

$S$

中的顶点连接。由于一个奇分支如果两两内部配对，最后至少还会剩下一个顶点必须要和

S

$S$

中的顶点（设为

v_i

$v_{i}$

）通过

M

$M$

中的边饱和。又因为

S

$S$

中的顶点在

M

$M$

下只能与一个顶点进行匹配，最多也就是

∣

|S|

$∣ S ∣$

个，因此就有

(

−

)

∣

{

…

}

∣

≤

∣

o(G-S)=k=|\{v_1\dots v_k\}|\le |S|

$o (G - S) = k = ∣ {v_{1} \dots v_{k}} ∣ \leq ∣ S ∣$

在这里插入图片描述

充分性：

假设图

G

$G$

满足：对于

⊂

(

)

\forall S\subset V(G)

$\forall S \subset V (G)$

，

(

−

)

≤

∣

o(G-S)\le |S|

$o (G - S) \leq ∣ S ∣$

，但是

G

$G$

中不存在完美匹配。

首先取

∅

S=\varnothing

$S = \emptyset$

，则

(

)

o(G)=0

$o (G) = 0$

，所以显然

(

)

V(G)

$V (G)$

是偶数。

之后给

G

$G$

添加边，获得一个边尽可能多的没有完全匹配的图

∗

G^*

$G^{*}$

（称为

边极大图

）。由于

G

$G$

是

∗

G^*

$G^{*}$

的生成子图，所以

⊂

(

)

\forall S\subset V(G)

$\forall S \subset V (G)$

，

−

G-S

$G - S$

是

∗

−

G^*-S

$G^{*} - S$

的生成子图。所以有：

(

∗

−

)

≤

(

−

)

≤

∣

(

∗

)

o(G^*-S)\le o(G-S)\le |S|~~~~~~~~~~~~(*)

$o (G^{*} - S) \leq o (G - S) \leq ∣ S ∣ (*)$

定义：

{

∣

∈

(

∗

)

∗

(

)

−

}

U=\{u\mid u\in V(G^*),d_{G^*}(u)=v-1\}

$U = {u ∣ u \in V (G^{*}), d_{G^{*}} (u) = v - 1}$

如果

(

∗

)

U=V(G^*)

$U = V (G^{*})$

，那么

∗

G^*

$G^{*}$

就是偶数阶完全图，而完全图显然有完美匹配，矛盾。因此有

≠

(

∗

)

U\neq V(G^*)

$U \neq = V (G^{*})$

。可以证明，此时

∗

−

G^*-U

$G^{*} - U$

的每一个连图分支都是完全图（作为命题

\mathrm A

$A$

后面另证）

根据

∗

)

(*)

$(*)$

式，有

(

∗

−

)

≤

∣

o(G^*-U)\le |U|

$o (G^{*} - U) \leq ∣ U ∣$

。可以构造出一个

∗

G^*

$G^{*}$

的完美匹配如下：

$G^*-U G ∗ − U 中的每一个奇分支的一个顶点和 U U U 的一个顶点匹配$
$G^*-U G ∗ − U 中各个分支剩余的顶点（奇分支中剩余的顶点和偶分支的所有顶点）在本分支内进行配对$

在这里插入图片描述

由于

U

$U$

（由于

U

$U$

的定义）和各个分支（根据命题

\mathrm A

$A$

）都是完全图，因此一定可以实现这样的构造。

由此证明出矛盾。

定理

\mathrm A

$A$

的证明：

如果

∗

−

G^*-U

$G^{*} - U$

中某一个连通分支

G_i

$G_{i}$

不是完全图，则显然有

(

)

∣

≥

|V(G_i)|\ge 3

$∣ V (G_{i}) ∣ \geq 3$

，且必然存在

∈

(

)

x,y,z\in V(G_i)

$x, y, z \in V (G_{i})$

，使得

∈

(

)

xy,yz\in E(G_i)

$x y, y z \in E (G_{i})$

，且

∉

(

)

zx\not \in E(G_i)

$z x \neq \in E (G_{i})$

。

在这里插入图片描述

又由于

∉

y\not \in U

$y \neq \in U$

，也就是

∗

(

)

−

d_{G^*}(y)<k-1

$d_{G^{*}} (y) < k - 1$

，也就是在

∗

G^*

$G^{*}$

中一定存在一个点

∈

(

∗

−

)

w\in V(G^*-U)

$w \in V (G^{*} - U)$

与

y

$y$

不相邻，即

∉

(

∗

)

yw\not \in E(G^*)

$y w \neq \in E (G^{*})$

。

现在我们就有了两个不在

(

∗

)

E(G^*)

$E (G^{*})$

中的边：

zx

$z x$

和

yw

$y w$

。由于

∗

G^*

$G^{*}$

是极大的没有完美匹配的图，所以

∗

G^*+xz

$G^{*} + x z$

和

∗

G^*+yw

$G^{*} + y w$

都存在完美匹配。将这两个完美匹配分别记为

M_1

$M_{1}$

（一定含有

xz

$x z$

）和

M_2

$M_{2}$

（一定含有

yw

$y w$

）。

定义

H

$H$

为

∗

∪

{

}

G^*\cup \{xz,yw\}

$G^{*} \cup {x z, y w}$

中由对称差

⊕

M_1\oplus M_2

$M_{1} \oplus M_{2}$

导出的子图，由于两个完美匹配边的数量相等，因此

H

$H$

的所有连通分支都是

偶长度圈

。

考虑两种情况：

z

x

zx

$z x$

和

w

yw

$y w$

在同一个连通分支（也就是同一个偶圈中），不妨设

,

y

,

w

,

z

x,y,w,z

$x, y, w, z$

按照顺时针顺序在这个偶长度圈之中出现。考虑这样的一种构造方法：
- $M_1 M 1 在 y w … z yw\dots z y w … z 段中的边集记为 M 1 ′ M_1′ M 1 ′ $
- $M_2 M 2 在 y w … z yw\dots z y w … z 段中的边集记为 M 2 ′ M_2′ M 2 ′ $
- $M_1’\cup\{yz\}\cup(M_2-M_2′) M 1 ′ ∪ { y z } ∪ ( M 2 − M 2 ′ ) 就以是个不含 z x zx z x 和 y w yw y w 的，满足 G ∗ G^* G ∗ 构造方法的一个完美匹配。与 G ∗ G^* G ∗ 的性质矛盾。（ M 1 ′ M_1′ M 1 ′ 不含 y w yw y w ，使得除了 y y y 和 z z z 以外的所有 y w … z yw\dots z y w … z 中的点都得到了饱和； { y z } \{yz\} { y z } 使得 y y y 和 z z z 得到饱和； ( M 2 − M 2 ′ ) (M_2-M_2′) ( M 2 − M 2 ′ ) 使得除了 y w … z yw\dots z y w … z 之外的所有点都得到饱和）$

在这里插入图片描述

$M_1 M 1 在 C C C 上的边（不含 y w yw y w 使得 C C C 中的所有顶点饱和）和 M 2 M_2 M 2 不在 C C C 上的边（不含 z x zx z x 使得所有 C C C 以外的定点得到了饱和）构成了 G ∗ G^* G ∗ 的一个完美匹配，矛盾。$

在这里插入图片描述

因此

∗

−

G^*-U

$G^{*} - U$

的所有连通分支都是完全图。

推论

推论一

偶数阶

k

−

1

)

(k-1)

$(k - 1)$

边连通的

k

$k$

正则图有完美匹配

证明

当

k=1

$k = 1$

时，结论显然

假定

≤

k\le 2

$k \leq 2$

。任取

⊂

(

)

S\subset V(G)

$S \subset V (G)$

，若有

∅

S=\varnothing

$S = \emptyset$

，则

−

G-S=G

$G - S = G$

，无奇分支，

(

−

)

∣

o(G-S)=|S|=0

$o (G - S) = ∣ S ∣ = 0$

，满足Tutte定理。

否则，定义：

∣

(

)

∣

{

∣

是

和

之

间

的

连

边

}

∣

v_i=|V(G_i)|\\ m_i=|\{e\mid e 是G_i和S之间的连边\}|

$v_{i} = ∣ V (G_{i}) ∣ m_{i} = ∣ {e ∣ e 是 G_{i} 和 S 之间的连边} ∣$

由于

′

(

)

≥

−

\kappa'(G)\ge k-1

$κ^{'} (G) \geq k - 1$

（根据边连通度为

−

k-1

$k - 1$

的条件），所以一定有

≥

−

m_i\ge k-1

$m_{i} \geq k - 1$

。如下图所示：

在这里插入图片描述

如果存在一个

i

$i$

，使得

−

m_i=k-1

$m_{i} = k - 1$

。由于

G

$G$

是正则图，因此有

∈

(

)

(

)

\sum_{v\in V(G_i)}d_{G}(v)=kv_i

$\sum_{v \in V (G_{i})} d_{G} (v) = k v_{i}$

，从而有：

∑

∈

(

)

(

)

−

∑

∈

(

)

(

)

−

(

)

m_i=\sum_{v\in V(G_i)}d_{G}(v)-\sum_{v\in V(G_i)}d_{G_i}(v)=kv_i-2\varepsilon (G_i)

$m_{i} = v \in V (G_{i}) \sum d_{G} (v) - v \in V (G_{i}) \sum d_{G_{i}} (v) = k v_{i} - 2 ε (G_{i})$

这个式子的意思就是，

G_i

$G_{i}$

连到

S

$S$

的边的数量，就是

G

$G$

中所有顶点度之和减去

G_i

$G_{i}$

中所有顶点度之和。其中前者很容易求出（因为是正则图），后面的其实并不需要我们求出具体值，只说明是偶数就可以（边的数量的两倍）

因此就有：

(

)

−

(

−

)

(

−

)

2\varepsilon(G_i)=kv_i-m_i=kv_i-(k-1)=k(v_i-1)+1

$2 ε (G_{i}) = k v_{i} - m_{i} = k v_{i} - (k - 1) = k (v_{i} - 1) + 1$

由于

−

v_i-1

$v_{i} - 1$

是偶数（因为

G_i

$G_{i}$

是奇分支）因此当时的右边就是奇数；而等式左边一定是偶数，因此矛盾。

上面的矛盾说明了，

≥

m_i\ge k

$m_{i} \geq k$

。因此就有

≥

\sum^n_{i=1}m_i\ge kn

$\sum_{i = 1}^{n} m_{i} \geq k n$

。又由正则性可知，

∈

(

)

∣

\sum_{v\in S}d_{G}(v)=k|S|

$\sum_{v \in S} d_{G} (v) = k ∣ S ∣$

，因此就有：

(

−

)

≤

⋅

∑

≤

∑

∈

(

)

∣

o(G-S)=n\le \frac 1k \cdot \sum^n_{i=1}m_i\le \frac 1k \sum_{u\in S}d_{G}(u)=|S|

$o (G - S) = n \leq \frac{1}{k} \cdot i = 1 \sum n m_{i} \leq \frac{1}{k} u \in S \sum d_{G} (u) = ∣ S ∣$

对于

⋅

∑

≤

∑

∈

(

)

\frac 1k \cdot \sum^n_{i=1}m_i\le \frac 1k \sum_{u\in S}d_{G}(u)

$\frac{1}{k} \cdot \sum_{i = 1}^{n} m_{i} \leq \frac{1}{k} \sum_{u \in S} d_{G} (u)$

：

$\frac 1k \cdot \sum^n_{i=1}m_i k 1 ⋅ ∑ i = 1 n m i 是 S S S 与所有奇分支所连接的边的数量$
$\frac 1k \sum_{u\in S}d_{G}(u) k 1 ∑ u ∈ S d G ( u ) 是 S S S 与所有奇偶分支、以及 S S S 内部相互连接的所有边的数量。$

因此显然两者之间有不等关系。

根据Tutte定理就可以得出结论。

推论二

2

$2$

-边连通（无割边）的

3

$3$

-正则图由完美匹配

由于每个顶点的度都是

3

$3$

，而所有顶点的度之和需要是偶数，因此顶点数量就是偶数。根据上面的推论代入之后显然。

推论三

偶数阶完全图

2

n

K_{2n}

$K_{2 n}$

有

n

−

1

2n-1

$2 n - 1$

个边不重的完美匹配

记

K_{2n}

$K_{2 n}$

的顶点集为

…

}

\{v_1,\dots ,v_{2n}\}

${v_{1}, \dots, v_{2 n}}$

，任取

−

2n-1

$2 n - 1$

个顶点（不妨设为

…

−

}

\{v_1,\dots v_{2n-1}\}

${v_{1}, \dots v_{2 n - 1}}$

），构造一个正多边形，并将剩下的那一个顶点（不妨设为

v_{2n}

$v_{2 n}$

）放在正多边形的中心位置。考虑每一个

多边形顶点

v_i

$v_{i}$

和

中心点

v_{2n}

$v_{2 n}$

相连的直线，以及与其

垂直

的直线，记为

M_i

$M_{i}$

。显然每一个

M_i

$M_{i}$

都是原图的匹配，而且每一个

M_i

$M_{i}$

之间没有任何一条重边。

在这里插入图片描述

原文链接：https://blog.csdn.net/Elko_265/article/details/123937445

匹配与最大匹配

匹配

最大匹配

交错路、增广路

最大匹配的条件

证明

完美匹配

奇分支

完美匹配的条件

证明

推论

推论一

证明

推论二

推论三

你可能也喜欢