Hopcroft Karp Algorithm

hopcroft-karp算法介绍

二分图最大匹配除了匈牙利算法还有一个Hopcroft-Karp算法，匈牙利算法的复杂的为$O(ne)$，而Hopcroft-Karp算法的复杂度为$O(e\sqrt{n})$。本文主要是对hopcroft与karp发表于1972年的二分匹配算法进行翻译，同时对此算法进行理解。

术语及约定

关于二分图的定义:二分图是这样的一个无向图，这个图中的所有的节点可以划分为两个子集，使得这个图中所有的边的两端节点都不可能在同一个子集里面。验证一个图是不是二分图是很简单的，就是一次深度优先遍历。首先任取一个点作为初始点，并给他标号为0，然后进行深度优先遍历。在遍历时，对对于所有经过的节点，如果没有标号的话，就1、0交替的标号；如果遇到已经标过号的点，检查这个节点应该标的号与这个节点已经标的号。如果相同则继续其他的深搜，如果不同则表示有冲突直接退出深搜，表示不可能是二分图。在整个深度优先遍历结束后，则可以断定这个图是二分图。

关于匹配的定义(match):一个匹配就是在图中的一些节点不重复的边的集合，或者说是不相邻的边的集合。一个匹配的大小就是这个匹配的边集的大小。对于任何一个图，他的匹配的大小总是有一个上确界，即最大匹配。二分图的匹配问题就是求给定的二分图的最大匹配问题。

增广路径(augmenting path)：增广路径是在匹配之上定义的。对于图$G=(V,E)$的一个匹配$M$，如果节点$v\in V$且$v$不与$M$中的任何一条边的某个端点相同，则我们把这个$v$成为自由节点。如果在$G$中存在一条路径

$$P=\{ (v_1,v_2),(v_2,v_3),\cdots ,(v_{2k-1},v_{2k})\}$$

，其中$v_1,v_{2k}$为自由节点，而这个路径上的边是交替存在于$E-M$和$M$中的。即

$$P\cap M=\{ (v_2,v_3),(v_4,v_5),\cdots,(v_{2k-2},v_{2k-1})\}$$

，这样的路径$P$就是一条增广路径。

增广路径定理

引理1:如果$M$是一个匹配，且$P$是相对于$M$的一条增广路径，那么$M \oplus P$也是一个匹配，且这个匹配比$M$的大一，即

$$\vert M\oplus P \vert =\vert M \vert +1$$

。

证明非常简单，根据增广路径的定义

\begin{equation}P\cap M=\{(v_2,v_3),(v_4,v_5),\cdots,(v_{2k-2},v_{2k-1})\}\end{equation}

里面只有$k-1$条边 ,因此

\begin{equation}P- (P\cap M) =\{ ( v_1,v_2),(v_3,v_4),\cdots ,(v_{2k-1},v_{2k})\}\end{equation}

,这里有$k$条边。而$M\oplus P$就是从$M$中删除了$P \cap M$，然后加上了$P-(P \cap M)$。由于$v_1,v_{2k}$都是自由节点，所以$P\oplus M$是一条增广路径，且这个增广路径比$M$大一，因为边的数量增加了1。

定理1:如果$M$和$N$都是一个匹配，且$\vert M \vert =r,\vert N \vert =s$，那么$M\oplus N$至少包括$s-r$个节点不交的相对于$M$的增广路径。

证明如下：考虑图$\bar{G}=(V,M\oplus N)$。由于$M$和$N$都是一个匹配，所以$V$中的任何一个节点最多存在于$M$中的一条边，同时也最多存在于$N$的一条边。所以图$\bar{G}$中的所有连通子图可以分为这样的三类。

一个单独的节点。
一个环，其中的边交替出现在$M-N$和$N-M$中。
一个路径，其中的边交替的出现在$M-N$和$N-M$中。

我们假设图$\bar{G}$中的所有连通子图如下$c_1,c_2,\cdots,c_g$,其中$c_i=(V_i,E_i)$。我们定义$\delta (c_i)=\vert E_i \cap N\vert -\vert E_i \cap M \vert$,则根据我们对连通子图的种类的分析，$\delta (c_i)$只有三种取值$\{0,-1,1\}$。当$\delta (c_i)=1$时，$c_i$是一条相对于$M$的增广路径。又因为

\begin{equation}\sum_i {\delta (c_i)}=\vert N-M \vert -\vert M-N \vert=\vert N\vert -\vert M\vert=s-r\end{equation}

，所以我们至少需要$s-r$条增广路径存在才能满足前式。因此，图$\bar{G}$中至少有$s-r$条相对于$M$的增广路径存在。

增广路径定理的推论

推论1：$M$是$G$中的一个匹配当且仅当$G$中没有相对于$M$的增广路径。

这条推论很简单，这里就不需要再去证明了。 推论2:假设$M$是一个匹配且$\vert M\vert =r$，同时最大匹配的大小为$s$，且$s>r$。那么，存在一条相对于$M$的增广路径$p$，使得$\vert p \vert \leq 2*\lfloor \frac{r}{s-r} \rfloor +1$。

证明如下：假设$N$是一个最大匹配，那么$M\oplus N$至少包括$s-r$个点不交的增广路径。同时，这些增广路径中总共有$r$条边来自于$M$，因此这些增广路径中一定会有一条增广路径包含了最多$\lfloor \frac{r}{s-r}\rfloor$条来自于$M$的边，所以这条增广路径的长度一定不大于$2*\lfloor \frac{r}{s-r} \rfloor +1$。QED

。

我们让$P$代表相对于$M$且长度最短的增广路径，我们可以有如下定理。

定理2:设$M$是一个匹配，$P$是相对于$M$的最短增广路径，且$P'$是一个相对于$M\oplus P$的增广路径，则

\begin{equation}\vert P'\vert \geq \vert P\vert +P \cap P'\end{equation}

证明如下：设$N=M\oplus P \oplus P'$，则$N$是一个匹配，且$\vert N\vert =\vert M \vert +2$。因此，$M\oplus N$中包含了两条相对于$M$的增广路径，我们分别称之为$P_1,P_2$。因为$M\oplus N=P\oplus P'$，所以

\begin{equation}\vert P \oplus P'\vert =\vert P_1 \vert +\vert P_2 \vert\end{equation}

但是由于$P$是最短增广路径，所以$P_1\geq P$,同时$P_2\geq P$。所以

\begin{equation}\vert P\oplus P' \vert =\vert P_1 \vert +\vert P_2 \vert \geq 2*\vert P\vert \end{equation}

又因为

\begin{equation}\vert P \oplus P'\vert =\vert P \vert +\vert P'\vert -\vert P\cap P'\vert \end{equation}

，所以

\begin{equation}\vert P'\vert \geq \vert P\vert +P \cap P'\end{equation}

根据上面的定理，我们提出一个算法来计算最大匹配。首先任意指定一个匹配$M_0$，然后按照这个规则来生成下一步的匹配。让$P_i$代表$M_i$中的最短增广路径，则$M_{i+1}=M_i \oplus P_i$。根据之前的定理，我们有如下结论:$\vert P_{i+1}\vert \geq \vert P_i\vert$。，且对于任何的一个$\vert P_{j}\vert = \vert P_i\vert$,$P_{j}$与$P_i$是节点不交的。第一个结论是显然的，我们来证明第二个结论。

证明:这里我们采用反证法。假设存在$i<j$使得$\vert P_j\vert =\vert P_i \vert$且$P_j$与$P_i$有相同的节点。那么存在$k,l$使得$i\leq k<l\leq j$，$P_k$与$P_l$对于所有的$k<m<l$的$P_m$都是节点不交的。则$P_l$是相对于$M_k\oplus P_k$的一条增广路径，因此

但是$\vert P_l \vert =\vert P_k \vert$，所以$\vert P_k \cap P_l\vert =0$。因此$P_k$与$P_l$没有共同的边。但是如果$P_k$与$P_l$之间有相同点的话，则这个点在$M_k \oplus P_k$中关联的边只有一条，且同时存在于$P_k,P_l$，由此引发了冲突。Q.E.D

定理3:假设$s$为最大匹配数，则增广路径序列$\vert P_0\vert ,\vert P_1 \vert ,\cdots$之中包含的不同的整数的个数不超过$2*\lfloor \sqrt{s}\rfloor+2$。

证明:套用推论2，让$r=\lfloor s-\sqrt{s} \rfloor$,此时$\vert M_r\vert =r$。因此

\begin{equation}\vert P_r\vert \leq 2*\frac{\lfloor s-\sqrt{s}\rfloor}{s-\lfloor s-\sqrt{s}\rfloor}+1\leq 2*\lfloor \sqrt{s} \rfloor +1\end{equation}

因此，对于每一个$i<r$，$\vert P_i\vert$是$\lfloor \sqrt{s} \rfloor +1$个不同的不大于$2*\lfloor \sqrt{s} \rfloor +1$的奇数中的一个。同时对于$\vert P_{r+1},\cdots,\vert{P_s}\vert$最多可以提供$s-r=\lceil \sqrt{s} \rceil$个不同的整数，所以总共的不同的整数个数有如下关系。

\begin{equation}\lfloor \sqrt{s} \rfloor +1 +\lceil \sqrt{s} \rceil\leq 2*\lfloor \sqrt{s} \rfloor +2\end{equation}

Q.E.D

算法设计与分析

根据上面的分析，整个算法的执行过程可以分为最多$2*\lfloor \sqrt{s} \rfloor +2$个相，每个相中所找到的所有增广路径都是长度相同且没有公共点的。所以我们可以将整个算法的执行过程归纳如下。

首先$M$为空集
然后寻找所有相对$M$的的且长度都为最短增广路径长度的最大增广路径集合$\{ P_1,\cdots ,P_k\}$
当集合为空时，搜索停止，返回$M$；当集合不为空时,更新$M$为$M\oplus P_1\oplus \cdots \oplus P_k$,并重复上一步。

算法实现

现在的问题有两个：一个是怎么确定最短增广路径的大小，一个是怎么找出最大的不交最短增广路径的集合。

对于第一个问题，是采取带增广路径限制的广度优先遍历，这一点很好懂。通过记录最后的最短层数$distance$及每一个节点在广度优先中出现的最早层数$depth[v_k]$，我们就得到了最短增广路径的长度。这里就不再说明，看模板代码就行。

对于第二个问题，是紧接着第一个问题来的。对于任意一个最短增广路径的末尾端点$v_k$，这个端点一定是属于右边的节点，且之前没有匹配，而且$depth[v_k]=distance$。这样我们就可以利用这个信息来找所有的最短增广路径的集合，方式是带增广路径限制和层数严格递减限制的深度优先遍历。但是我们的目的是为了寻找最大的不交最短增广路径的集合，所以逆向深搜的过程中对于已经存在于某一条最短增广路径中的点不能重复加入，这个是使用$used[]$数组来起作用的。这里我们需要证明在一条增广路径中能够与其他增广路径起冲突时，这些路径都会共享一段子路径，即这些路径之中不管怎么选，只能找一条路径出来。所以路径的搜索顺序就没有关系了，这一段也是看代码自己去理解。