这是本文档旧的修订版!
带花树是解决一般图的最大匹配的算法。
由于涉及到最大匹配,我们这里对增广路进行一个简短的介绍:
1.如果在一个$M$匹配的图G中,有一个点$v$是孤立的指没有与其匹配的点。一条在$G$中的路径如果其边在M中交替出现,则称为交错路($alternating path$)。一条增广路($augmenting path$)$P$是一条开始并结束于不相同的孤立点的交错路。
2.在增广路中不是匹配的边比是匹配的边多,因此增广路的边条数为奇数。
3.一个匹配在增广路上的增广即为异或操作:M1=M xor P。
考虑下我们之前在二分图中找增广的过程:
1.我们寻找增广路的时候,会将路径上的点黑白染色,匹配只存在于黑点白点之间。
2.如果没有环或是只有偶环(二分图中只有偶环),那么每个点的颜色是确定的。
3.但是如果出现了奇环,那么点的颜色不再确定,因为奇环顺时针走一圈和逆时针走一圈的染色结果是不同的。(如下图所示,模拟一次增广的染色,我们可以明显发现进入奇环的那个点的染色结果出现冲突)
1.从一个孤立的点$w$开始遍历图。
2.从孤立点$w$开始遍历,标记$w$为$o$型点($out of M$)。
3.交替地用$i$和$o$标记结点,保证无两个相邻节点有标记。
4.如果找到两个相邻结点含有标记$o$,那么我们就找到了一个奇环和一朵花。
定义收缩图$G'$是图$G$将所有花$B$缩为点后的图。
定义收缩匹配$M'$是在$G'$中的匹配$M$。
$G'$含有$M'$的增广路当且仅当$G$含有$M$的增广路,且任何$M'$在图$G'$的增广路$P'$都可以通过展开收缩的花还原$G$中的匹配$M$。因此如果存在任意一条增广路$P'$通过收缩的花$V_B$,都可以找到合适的增广路通过花$B$。因此我们可以将一朵花缩成一个点。
如以下几图所示,如果$P'$在图$G'$中经过$u \rightarrow V_B \rightarrow w$,这条增广路可以在$G$中配替换为$u \rightarrow (u'\rightarrow \ldots\rightarrow w') \rightarrow w,$其中$u'$与$w'$在花B中。路径$u' \rightarrow w'$的选择需保证构成的新增广路仍然是交替的。(其中$u'$即在花$B$中也在匹配$M$中(花根),$w' \rightarrow w$是一条增广路)
若$P'$在$V_B$结束,这条增广路可以在$G$中被替换为$u \rightarrow (u' \rightarrow \ldots \rightarrow v')$,其中$u'$与$v'$在花$B$中。路径$u' \rightarrow v'$的选择需保证构成的新增广路仍然是交替的。(其中$v'$是孤立的(花根),$u \rightarrow u'$是一条增广路)
继续观察可以发现,整个奇环的匹配状态只与顶点的匹配状态有关,如果在后来的某一次寻找时奇环上的匹配被改变了,那么顶点的颜色唯一决定了整个环的匹配边是如何走的。(花上的任意一个点都可作为o 型点出边)