\chapter{匹配问题}
\section{二部图与匹配}

\begin{wrapfigure}[11]{r}{5cm}
    \begin{center}
        \begin{tikzpicture}
            \draw node[circle, draw = black] (a1) at (0,0) {};
            \draw node[circle, draw = black] (a2) at (0,1) {};
            \draw node[circle, draw = black] (a3) at (0,2) {};
            \draw node[circle, draw = black] (a4) at (0,3) {};
            \draw node[circle, draw = black] (a5) at (0,4) {};
            \draw node[circle, draw = black] (a6) at (0,5) {};
            \draw node[circle, draw = black] (b1) at (4,0) {};
            \draw node[circle, draw = black] (b2) at (4,1) {};
            \draw node[circle, draw = black] (b3) at (4,2) {};
            \draw node[circle, draw = black] (b4) at (4,3) {};
            \draw node[circle, draw = black] (b5) at (4,4) {};
            \draw node[circle, draw = black] (b6) at (4,5) {};
            \draw (a1)--(b3);
            \draw[blue!30] (a1)--(b4);
            \draw[blue!30] (a1)--(b5);
            \draw (a2)--(b1);
            \draw[blue!30] (a2)--(b3);
            \draw[blue!30] (a2)--(b5);
            \draw[blue!30] (a3)--(b1);
            \draw (a3)--(b2);
            \draw[blue!30] (a3)--(b4);
            \draw[blue!30] (a4)--(b2);
            \draw[blue!30] (a4)--(b3);
            \draw (a4)--(b6);
            \draw[blue!30] (a5)--(b1);
            \draw (a5)--(b5);
            \draw[blue!30] (a5)--(b6);
            \draw[blue!30] (a6)--(b2);
            \draw (a6)--(b4);
        \end{tikzpicture}
    \end{center}
    \caption{一个二部图与它的一个完美匹配}
\end{wrapfigure}

我们先来看几个定义：

\begin{definition}[二部图]
    称一张图为二部图，若它可以划分为两个部分$A, B$，使得图中的每一条边都连接两部分中的某一对顶点。
\end{definition}

\begin{definition}[匹配]
    若一个边的集合中的任意两个边无公共顶点，则这个集合称为一个\newnoun{匹配}{matching}。一个覆盖了所有点的匹配称为\newnoun{完美匹配}{perfect matching}。
\end{definition}

\begin{theorem}[König's Theorem]
    一切度不为零的正则二部图一定有完美匹配。
\end{theorem}

\begin{definition}
    对图$G = (V,E), v \in V$，记$v$的临域为$N_G(v)$。对点集$S \subset V$，定义$S$的临域为$N_G(S) := \bigcup_{v \in S}N_G(v)$。
\end{definition}

\section{主定理}
\begin{theorem}[The Marriage Theorem婚姻定理]
    二部图含有完美匹配当且仅当$\vert A \vert = \vert B \vert$且对$A$的任意子集$S \subset A, \vert S \vert \leq \vert N(S)\vert$。
\end{theorem}

\begin{remark}
    如果将定理中的$A,B$互换，定理应该仍旧成立，特别是其中的不等式对$B$也成立。因此两个不等式其一应该可以推倒出另一个。
\end{remark}

\begin{proposition}
    对一个二部图若$\forall S \subset A$有$\vert S \vert \leq \vert N(S) \vert$，则$\forall T \subset B$有$\vert T \vert \leq \vert N(T) \vert$。
\end{proposition}

\begin{figure}[!htpb]
    \begin{center}
        \begin{tikzpicture}[scale=0.85]
            \draw (-2,0) ellipse (1 and 3);
            \draw (2,0) ellipse (1 and 3);
            \draw (-2,1.5) ellipse (0.7 and 1);
            \draw (2,1.5) circle (0.7);
            \draw (-2,2.5)--(2,2.2);
            \draw (-2,0.5)--(2,0.8);
            \node (A) at (-3.5, 0) {$A$};
            \node (B) at (3.5, 0) {$B$};
            \node at (-2,1.5) {$N(T)$};
            \node at (2,1.5) {$T$};
        \end{tikzpicture}
    \end{center}
    \caption{$T$与它的临域$N(T)$}
    \label{婚姻定理引理}
\end{figure}

\begin{proof}
    对于$T \subset B$（如图\ref{婚姻定理引理}），有
    \[N(A \setminus N(T)) \subset B \setminus T\]
    那么
    \begin{align*}
        \vert A \vert - \vert N(T) \vert & = \vert A \setminus N(T) \vert\\
        & \leq \vert N(A\setminus N(T)) \vert\\
        & \leq \vert B \setminus T\vert\\
        & = \vert B \vert - \vert T \vert
    \end{align*}
    综合起来即
    \[\vert A \vert - \vert N(T) \vert \leq \vert B \vert - \vert T \vert\]
    得到$\vert N(T) \vert \geq \vert T\vert$。
\end{proof}
\begin{wrapfigure}{r}{6cm}
    \begin{center}
        \begin{tikzpicture}[scale=0.7]
            \draw (-2,0) ellipse (1 and 3);
            \draw (2,0) ellipse (1 and 3);
            \draw (-2,0) circle (0.7);
            \draw (2,0) circle (0.7);
            \draw (-2,0.7)--(2,0.7);
            \draw (-2,-0.7)--(2,-0.7);
            \draw (-2,2)--(2,2);
            \node[draw=black, fill=black, circle] at (-2,2) {};
            \node[draw=black, fill=black, circle] at (2,2) {};
            \node (A) at (-3.5, 0) {$A$};
            \node (B) at (3.5, 0) {$B$};
            \node at (-2,0) {$S$};
            \node at (2,0) {$R$};
            \node[above] at (-2,2.2) {$a$};
            \node[above] at (2,2.2) {$b$};
        \end{tikzpicture}
    \end{center}
    \caption{图$G$}
    \label{婚姻定理证明}
\end{wrapfigure}
下面我们来证明婚姻定理：

\begin{proof}
    必要性是显然的。现在来证明充分性：
    对图的顶点数使用数学归纳法。$\vert A \vert = \vert B \vert = 1$时，结论显然成立。
    
    设$\vert A \vert = \vert B \vert \leq k$时，结论成立。当$\vert A \vert = \vert B \vert = k + 1$时，在$A$中找一点$a$，那么
    \[\vert N(a) \vert \geq \vert \{a\} \vert = 1\]
    这意味着一定存在$b \in B$且$b \in N(a)$，即$a$与$b$可配对。

    现在，令$H := G - a - b$，即将$G$中的$a, b$及所有某个端点为$a$或$b$的边都删除后得到的图。

    \begin{enumerate}[label=(\arabic{*})]
        \item 若$\forall S \subseteq A \setminus \{a\}$与$R = N_H(S)$，有
        \[\vert S \vert \leq \vert R \vert\]
        那么由归纳假设，$H$有完美匹配，再加上$a,b$的配对，可以得到$G$有完美匹配，得证；
        \item 若$\exists S \subset A \setminus \{a\}$满足$\vert S \vert > \vert R \vert$，注意到$\vert S \vert < \vert N_G(S)$而$\vert S \vert \leq \vert N_H(S) \vert$，这意味着$b \in N_G(S)$。可设$T = R \cup \{b\}$。那么我们有$T = N_G(S)$且$\vert S \vert = \vert T \vert$。
        
        设两个子图：$G_1 := G(S \cup T), G_2 := G[(A \setminus S) \cup (B \setminus T)]$，即对$G_1 = (V_1, E_1)$，其中$V_1 \subset S \cup T$且$E_1 = \{e \in E \mid e \cap S \neq \varnothing, e \cap T \neq \varnothing\}$。$G_2$也类似定义。

        注意到$G_1$是二部图而且$\vert S \vert = \vert T \vert$，而且在$G$中$S$的临域就是$T$，这意味着$\forall X \subset S$，$N_G(X) = N_{G_1}(X) \subseteq T$。那么我们由题目条件知道$ \vert X \vert \leq \vert N_G(X) \vert = \vert N_{G_1}(X)\vert$由归纳假设，$G_1$中有完美匹配；类似地，$G_2$也有完美匹配。

        再加上$a,b$也是匹配的，因此将$ab, G_1, G_2$组合起来就得到了$G$的完美匹配。
    \end{enumerate}
    综上，$G$有完美匹配，$\vert A \vert = \vert B \vert = k + 1$时结论也成立。
\end{proof}

通过类似的证明方法，我们还能得到一个婚姻定理的推广：
\begin{theorem}\label{婚姻定理推广}
    在若一个二部图满足对$A$的任意子集$X \subset A$都有$\vert X \vert \leq \vert N(X) \vert$（$A$与$B$的元素数不一定相等），那么一定存在一个匹配包括$A$中所有的点（但$B$中可能有点没有与$A$中的点匹配）。
\end{theorem}

\section{如何找到完美匹配}
\begin{figure}[H]
    \centering
    \subfloat[贪心算法]{
        \begin{tikzpicture}
            \draw node[circle, draw = black] (a1) at (0,0) {};
            \draw node[circle, draw = black] (a2) at (0,1) {};
            \draw node[circle, draw = black] (a3) at (0,2) {};
            \draw node[circle, draw = black] (a4) at (0,3) {};
            \draw node[circle, draw = black] (a5) at (0,4) {};
            \draw node[circle, draw = black] (a6) at (0,5) {};
            \draw node[circle, draw = black] (b1) at (4,0) {};
            \draw node[circle, draw = black] (b2) at (4,1) {};
            \draw node[circle, draw = black] (b3) at (4,2) {};
            \draw node[circle, draw = black] (b4) at (4,3) {};
            \draw node[circle, draw = black] (b5) at (4,4) {};
            \draw node[circle, draw = black] (b6) at (4,5) {};
            \draw (a1)--(b3);
            \draw[blue!30] (a1)--(b4);
            \draw[blue!30] (a1)--(b5);
            \draw (a2)--(b1);
            \draw[blue!30] (a2)--(b3);
            \draw[blue!30] (a2)--(b5);
            \draw[blue!30] (a3)--(b1);
            \draw[blue!30] (a3)--(b2);
            \draw (a3)--(b4);
            \draw (a4)--(b2);
            \draw[blue!30] (a4)--(b3);
            \draw[blue!30] (a4)--(b6);
            \draw[blue!30] (a5)--(b1);
            \draw (a5)--(b5);
            \draw[blue!30] (a5)--(b6);
            \draw[blue!30] (a6)--(b2);
            \draw[blue!30] (a6)--(b4);
        \end{tikzpicture}
    }
    \hspace{2cm}
    \subfloat[寻找可扩路]{
        \begin{tikzpicture}
            \draw node[circle, draw = black] (a1) at (0,0) {};
            \draw node[circle, draw = black] (a2) at (0,1) {};
            \draw node[circle, draw = black] (a3) at (0,2) {};
            \draw node[circle, draw = black] (a4) at (0,3) {};
            \draw node[circle, draw = black] (a5) at (0,4) {};
            \draw node[circle, draw = black] (a6) at (0,5) {};
            \draw node[circle, draw = black] (b1) at (4,0) {};
            \draw node[circle, draw = black] (b2) at (4,1) {};
            \draw node[circle, draw = black] (b3) at (4,2) {};
            \draw node[circle, draw = black] (b4) at (4,3) {};
            \draw node[circle, draw = black] (b5) at (4,4) {};
            \draw node[circle, draw = black] (b6) at (4,5) {};
            \draw (a1)--(b3);
            \draw[blue!30] (a1)--(b4);
            \draw[blue!30] (a1)--(b5);
            \draw (a2)--(b1);
            \draw[blue!30] (a2)--(b3);
            \draw[blue!30] (a2)--(b5);
            \draw[blue!30] (a3)--(b1);
            \draw[red] (a3)--(b2);
            \draw (a3)--(b4);
            \draw[blue, line width=2pt, dashed] (a3)--(b4);
            \draw (a4)--(b2);
            \draw[blue, line width=2pt, dashed] (a4)--(b2);
            \draw[blue!30] (a4)--(b3);
            \draw[red] (a4)--(b6);
            \draw[blue!30] (a5)--(b1);
            \draw (a5)--(b5);
            \draw[blue!30] (a5)--(b6);
            \draw[blue!30] (a6)--(b2);
            \draw[red] (a6)--(b4);
            \node at (-0.5, 5) {$u$};
            \node at (4.5, 5) {$v$};
            \node at (-1, 2.5) {$A$};
            \node at (5, 2.5) {$B$};
        \end{tikzpicture}
    }
\end{figure}

\subsection{思路}
\begin{enumerate}
    \item 首先贪心地尽可能多地配对，直到$A$中剩下的点都不能配对（在本土中只有$u$一个）为止。这时对应的$B$中应该也有同样多的不能配对的点。
    \item 在图中寻找一条从$u$开始的、未选的（红色）和已选的（黑色，蓝虚线）交替连接的、$v$为终点的路（path），称为一条\newnoun{可扩路}{augmenting path}。
    \item 把这条路上红色的变为选中的路，蓝色的变为没有选中的路，匹配的点又多了一对。
\end{enumerate}

\subsection{方法正确性的证明}
\begin{figure}[H]
    \begin{center}
        \begin{tikzpicture}[scale=0.85]
            \draw node[circle, draw = black] (a1) at (0,0) {};
            \draw node[circle, draw = black] (a2) at (0,1) {};
            \draw node[circle, draw = black] (a3) at (0,2) {};
            \draw node[circle, draw = black, fill=black] (a4) at (0,3) {};
            \draw node[circle, draw = black, fill=black] (a5) at (0,4) {};
            \draw node[circle, draw = black, fill=black] (a6) at (0,5) {};
            \draw node[circle, draw = black, fill=black] (a7) at (0,6) {};
            \draw node[circle, draw = blue, fill=blue!30] (a8) at (0,7) {};
            \draw node[circle, draw = blue, fill=blue!30] (a9) at (0,8) {};
            \draw node[circle, draw = black] (b1) at (3,0) {};
            \draw node[circle, draw = black] (b2) at (3,1) {};
            \draw node[circle, draw = black] (b3) at (3,2) {};
            \draw node[circle, draw = black, fill=black] (b4) at (3,3) {};
            \draw node[circle, draw = black, fill=black] (b5) at (3,4) {};
            \draw node[circle, draw = black, fill=black] (b6) at (3,5) {};
            \draw node[circle, draw = black, fill=black] (b7) at (3,6) {};
            \draw node[circle, draw = blue, fill=blue!30] (b8) at (3,7) {};
            \draw node[circle, draw = blue, fill=blue!30] (b9) at (3,8) {};
            \draw (a1)--(b1);
            \draw (a2)--(b2);
            \draw (a3)--(b3);
            \draw (a4)--(b4);
            \draw (a5)--(b5);
            \draw (a6)--(b6);
            \draw (a7)--(b7);
            \draw[red] (a8)--(b6);
            \draw[red] (a6)--(b5);
            \draw[green] (a5)--(b9);
            \draw[blue] (a5)--(b3);
            \draw[rounded corners] (-1,6.5) rectangle (0.5,8.5);
            \draw[rounded corners] (2.5,6.6) rectangle (4,8.5);
            \draw[rounded corners] (-1.2,2.5) rectangle (0.7,8.7);
            \draw[rounded corners] (2.5,2.5) rectangle (4,6.4);
            \node at (-0.6, 7.5) {$U$};
            \node at (3.6, 7.5) {$W$};
            \node at (-0.6, 4.5) {$S$};
            \node at (3.6, 4.5) {$T$};
            \node at (-0.5,4) {$s$};
            \node at (-0.5,7) {$u$};
            \node at (-0.5,2) {$q$};
            \node at (3.5,8) {$r$};
            \node at(3.5,2) {$r$};
        \end{tikzpicture}
    \end{center}
    \caption{寻找可扩路的过程中可能遇到的几种情况}
\end{figure}
设在贪心配对之后，$U$为未配对的$A$中的点的集合，$W$为未配对的$B$中的点的集合。

若一条路是以$U$中的某个点为起点、被选中的和没被选中的边交替、终点在$A$中的路，则称它是一条\newnoun{几乎可扩路}{almost augmenting path}。

先令$S = U$。之后每次新找到一个可以由几乎可扩路达到的$A$中的点，都把这个点加入$S$中。设$T$是$B$中与$S$中的点配对的点。那么时刻有$\vert S \vert = \vert T \vert + \vert U \vert$。

设$M$是已经配对的点和将它们配对的边组成的集合。我们不断重复下面的操作：如果我们能在$S$中找到$s \in S$，满足$\exists r \in B \setminus T, sr \in E \setminus M$，即有一个从$S$中连接至$T$之外的点的边，就考虑：设$Q$是从$u \in U$开始，$s$结束的几乎可扩路（图中红色）。我们找到的$sr$有两种可能的情况：

\begin{enumerate}
    \item $r$是未配对的（$r \in W$，图中的绿色线），那么$Q-sr$组成了一个可扩路，将红色部分加入、黑色部分删去，就增加了一对配对的点，即我们成功地将$s, r$扩充进了$M$；
    \item $r$是已经配对的（图中的蓝色线），那么我们可以设它与$q$配对，那么$Q-sr-rq$形成了一个新的几乎可扩路，这意味着$q$可以被添加进$S$，$r$应该被添加到$T$中。
\end{enumerate}
不论我们执行了哪个动作，我们要么扩充了$M$，要么扩充了$S$。等我们检查了$S$中所有的点之后，我们要么得到$M$是一个完美匹配，要么是$M$不是完美匹配，而所有$U$内点出发的所有可扩路都结束在$S$内，且$S$内所有点都不与$T$之外的点相连，这意味着$T = N(S)$，然而$\vert T \vert = \vert S \vert - \vert U \vert < \vert S \vert$。我们找到了$A$的一个子集$S$满足$\vert S \vert > \vert N(S)\vert$。根据婚姻定理，这个二部图不存在完美匹配。