离散数学复习：二部图与匹配

寄寄寄寄摆摆摆摆

二部图

二部图：定义

可以将顶点集划分为两个不相交的类别、每一条边的两个端点都在不同类别中的图。

完全二部图

来自不同类别的任意两个顶点之间均有边相连。

图中的匹配

• 匹配：一张图中互不相邻的边的集合，记为M。
• M-饱和点：M中各点的端点。

二部图中的完备匹配

定义：设G为二部图且可被二部划分为<V1, V2>, 若G中的匹配M能够饱和V1中所有的顶点，则称M是 V1到V2的 完备匹配`（不是完美匹配！）

注：完备匹配一定是最大匹配，但当且仅当|V1| = |V2|时该匹配才能被称为完美匹配。

注2： 完备匹配不一定是稳定匹配，稳定匹配不一定是完备匹配！

Hall定理

设二部图G = <V1, V2, E>， 则G有从V1到V2的完备匹配当且仅当对于任意A ⊆ V1, 有|N(A)|(A的相邻顶点数) ≥ |A|.

证明：

必要性显然。

充分性：

1. 当|V1| == 1时充分性显然成立。
2. 假设当|V1| ≤ k (k ≥ 1)时充分性成立，现证明当|V1| == k + 1时命题也成立。
   分成两种情况证明。

(1). 对于V1的任意真子集A，|N(A)| > |A|:

从V1中任取一个顶点v, 从M(v)中任取一个顶点w；

则有v ∈ V1, w ∈ V2.

由归纳假设得，此时V1 - {v} 到 V2 - {w}构成一个完备匹配。

可得上述完备匹配加上边(v, w)可以构成从V1到V2的完备匹配。

(2). 存在`V1`的一个**真**子集`A'`，`|N(A')| = |A'|`.

记B' = N(A')。

根据归纳假设，存在从A'到B'的完备匹配。又因为假设，有|V2 - B'| ≥ |V1 - A'|。

即存在从V1 - A'到V2 - B'的一个完备匹配。

将以上两个匹配相合并，即可得到一个V1到V2的完备匹配。

Hall定理：推论

正则图

正则图（regular graph）是指每个顶点都有相同数目的相邻顶点的图(亦即对于任意v∈G, N(v) ≡ k)， 称为k-正则图.

特别的，阶（图中的点数）为K的K-1 - 正则图即为K-完全图。

推论内容

设二部图G是K-正则的(k ≥ 1)， 则G有完美匹配。

证明

设G = <A, B, E>, 则有K|A| = K|B|（每个点所连接的边数相同，但所有边均存在于两组点之间），因此|A|=|B|.

对于任意一集合S ∈ A, S与N(S)之间共有K|S|条边；但与N(S)相关的边共有K|N(S)|条。

因此有K|N(S)| ≥ K|S|（从S连接到N(S)的边包含在与N(S)有关的边之中）。
因此， |N(S)| ≥ |S|.

由霍尔定理得，在G中存在从A到B的完备匹配。又因为|A| = |B|，所以该匹配是完美匹配。

另一个推论（更一般的情况）

二部图G = <V1, V2, E>, 若V1中每个顶点至少关联t条边，而若V2中每个顶点至多关联t条边，则G中存在V1到V2的完备匹配。

---

交错路径与可增广路径

设M是G中的一个匹配。若G的一条路径P中，属于M的边和不属于M的边交替出现，则称P为M-交错路径；

若P的起点和终点都是M-非饱和点，则称P是可增广交错路径。

Berge定理

M是G的最大匹配，当且仅当G中不存在M-可增广交错路径。

证明参见： Proof of Berge's Theorem

稳定匹配问题

偏好集

G上的一个偏好集是一族线性序(≤v), v∈V；其中, ≤v是E(v)上的线性序（对v相连的边进行排序）。

稳定匹配

G上的匹配M是稳定的，当且仅当对于M中任意一条边e, 存在边f ∈ E - M， 满足：

• e和f有公共端点
• e ≤v f.

稳定匹配定理

对于任意给定的一个偏好集，图G有一个稳定的匹配（并不一定是完备匹配）。

Gale-Sharpley算法

Wikipedia - Gale-Sharpley Algorithm

以下的讨论均假设有一二部图G = <V1, V2, E>, 已经形成的匹配名为M。

定义：V1中某点u对匹配的 “满意性”：若存在V2中匹配之外的一点w， 有(u, w) ≤u (u, N(u)).

定义2：V2中某点v是否可以接受与V1中的u匹配: 若满足(u, v) ∈ E - M， 且若存在(u', v) ∈ M， 则有(u', v) <v (u, v).

算法过程

1. 选择V1中的一个尚未配对的顶点u, 在边集{(u, v) | u 可以被 v 接受}中按照线性序≤u找出符合条件的最大元，并将其添加至M中。同时，删除M中以v为端点的边。
2. 循环(1)， 直至对于V1中的任意未配对顶点u，边集{(u, v) | u 可以被 v 接受}为空则结束算法。

正确性分析：当算法结束时，

• V1中所有的未配对顶点均没有可以被接受的对象；
• V1中所有的顶点都对该匹配满意。
• 算法停止时V2的匹配情况比其他匹配情况更优：算法进行过程中，V2中的点只会接受比当前匹配好的匹配（“可被接受”的定义）。
• M是稳定的：

对于任意的e ∈ E - M， 均存在f ∈ M满足：

• e 和 f 有公共端点；
• e <v f.