图的匹配

图的匹配问题
定义：设M是G的边子集，G是无向简单连通图（下同），M中任意两边不相邻，则称M是G的一个匹配。与M中边关联的点称为M的饱和点，其余为非饱和点。

定义：设M是G的一个匹配。如果对G的任一个匹配\(M'\)都有\(|M|\ge|M'|\)，称M是G的最大匹配。特别的，若G的结点都是饱和点，称M为完美匹配。

定义：给定G的一个匹配M，G中属于M和不属于M的边交替出现的道路称为关于M的交错道路。如果交错道路P的起点和终点都是关于M的非饱和点，称P为可增广道路。

定理1. M是G的最大匹配当且仅当G中不存在关于M的可增广道路。
证明：必要性，若P是M的可增广道路，则\(P\oplus M\)边数比M多1；充分性，取G的最大匹配\(M'\)，令\(G'=M\oplus M'\)，则\(\Delta(G')\le 2\)（因为任一个匹配中的点至多与一边关联），\(G'\)的连通分支只有2种：要么是由M和\(M'\)的边交错形成的偶回路，要么是\(M'\)与\(M\)的边交错形成的道路P。P一定有偶数条边，否则P是M或M'的可增广道路。综上可知\(|M|=|M'|\)。

利用定理1可以给出求解最大匹配的算法：反复寻找可增广道路。

二部图的匹配
定义：设M是二部图\(G=(X,Y,E)\)的匹配，若\(|M|=|X|\)，则称M是G的从X到Y的完全匹配。
引理2. 设M是G的一个匹配，\(x_0\)不是X中的饱和点。令U表示X中所有可通过以\(x_0\)为起点的交错道路到达的结点（含\(x_0\)），V表示Y中所有可通过以\(x_0\)为起点的交错道路到达的点，则有：
1. 存在以\(x_0\)为起点的可增广道路\(\Leftrightarrow\)V中存在M的非饱和点；
2. 不存在以\(x_0\)为起点的M的可增广道路\(\Leftrightarrow\)\(N(U)=|U|-1\)。
证明：结论1是显然的。对于结论2，首先说明U中除了\(x_0\)都是M的饱和点，V中的点也都是M的饱和点。必要性：由于每个V中的饱和点唯一对应一个U中除\(x_0\)外根据M的匹配唯一对应于V的点，所以\(|V|=|U|-1\)且\(N(U)=V\)。充分性：如果\(|N(U)| = |U|-1\)，若存在以\(x_0\)为起点的可增广道路，取\(M'=M\oplus P\)，则U和V的点都是\(M'\)的饱和点，\(|U|=|V|\)，矛盾。

定理3. 在二部图\(G=(X,Y,E)\)中，存在X到Y的完美匹配的充要条件是对X的任意子集\(A\subseteq X\)，恒有\(|N(A)|\ge |A|\)。
证明：必要性，设M是X到Y的完全匹配，因为A中的点一一匹配到\(N(A)\)中的点，所以\(|A|=|N(A)|\)。充分性，任取G的一个最大匹配M，若M不是完全匹配，则存在非饱和点\(x_0\in X\)，不存在以\(x_0\)为起点的M可增广道路，由引理存在\(U\subseteq X\)使得\(N(U)=|U|-1\)，矛盾。

推论4. 设k是正整数，若在二部图\(G=(X,Y,E)\)中，对任意\(x\in X, y\in Y\)都有\(d(x)\ge k, d(y)\le k\)，则存在从X到Y的完美匹配。

定理5. 令\(\epsilon(A) =\max\{|A|-|N(A)|, 0\},\epsilon(G) = \max\limits_{A\subseteq X} \epsilon(A)\)，则\(G=(X,Y,E)\)的最大匹配边数是\(|X|-\epsilon(G)\)。
证明：容易证明G的最大匹配边数不超过\(|X|-\epsilon(G)\)。下面给出构造，断言：若\(\epsilon(A)=\epsilon(G)\)，则导出子图\(G'=(X-A, Y-N(A), E')\)满足\(\epsilon(G')=0\)。否则存在\(X-A\)的子结点集B，使得\(|B| > |N(B)\cap (Y-N(A))|\)，此时计算得\(\epsilon(A\cup B) > \epsilon(G).\)下面对\(\epsilon(G)\)进行归纳。

    所属分类：离散数学     发表于2022-08-25