用户工具

站点工具


2020-2021:teams:hotpot:带花树

这是本文档旧的修订版!


带花树

带花树是解决一般图的最大匹配的算法。

增广路

由于涉及到最大匹配,我们这里对增广路进行一个简短的介绍:

1.如果在一个$M$匹配的图G中,有一个点$v$是孤立的指没有与其匹配的点。一条在$G$中的路径如果其边在M中交替出现,则称为交错路($alternating path$)。一条增广路($augmenting path$)$P$是一条开始并结束于不相同的孤立点的交错路。

2.在增广路中不是匹配的边比是匹配的边多,因此增广路的边条数为奇数。

3.一个匹配在增广路上的增广即为异或操作:M1=M xor P。

一般图中增广路与二分图的区别

考虑下我们之前在二分图中找增广的过程:

1.我们寻找增广路的时候,会将路径上的点黑白染色,匹配只存在于黑点白点之间。

2.如果没有环或是只有偶环(二分图中只有偶环),那么每个点的颜色是确定的。

3.但是如果出现了奇环,那么点的颜色不再确定,因为奇环顺时针走一圈和逆时针走一圈的染色结果是不同的。(如下图所示,模拟一次增广的染色,我们可以明显发现进入奇环的那个点的染色结果出现冲突)

花与收缩的定义

在一个$M$匹配的图$G$中,一朵花$B$是一个图$G$中的包含$2k+1$条边的奇环,其中$k$条边在$M$中,并存在从环上任意一个点$v$(花根)到一个孤立点$w$的交错路(花茎)。

如何找到一朵花

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 型点出边)

细节方面的一些问题

问题1

为什么我们仅仅将花根与环外匹配的环称为花?为什么花根与环内匹配不能称为一朵花?

因为带花树缩花的原因是为了防止寻找增广路的时候绕环一圈后重新进入花茎而发生干扰。如果花茎是这样的:

此时o标记的点相邻,因为队列中的点均为o标记点,所以可能会与花茎发生干扰。

如果花茎是这样的:

i标记点相邻,显然不会与花茎发生干扰$<del>(甚至有可能直接增广成功了)<\del>$。虽然该环是个奇环,但显然当前的交错路不会是花茎,当前花茎相连的点也不是花根。

2020-2021/teams/hotpot/带花树.1590138201.txt.gz · 最后更改: 2020/05/22 17:03 由 lotk