算法技术手册（原书第2 版）

220

｜

第

8

章

的最大配对数目。该算法保证不存在更多的匹配数（虽然有可能会有其他匹配方式能够

得到同样多的匹配数目）。

8.3.2 解决方案

我们将二分图匹配问题归约成最大流问题，而并没有重新设计一个新的算法。在二分图

匹配中，从元素集

S

和参与者集合

T

中选择了匹配（

s

i

,

t

j

）之后，

s

i

或者

t

j

就不能被其他

匹配选择。我们使用

n

表示集合

S

的大小，

m

表示集合

T

的大小。为了在流网络图中产

生同样的行为，我们可以按照如下方法来构建图

G

= (

V

,

E

)

：

V

包含

n + m + 2

个顶点

每个元素

s

i

映射为编号为

i

的顶点，每个参与者映射为编号为

n

+

j

的顶点。创建一个

新的源顶点

src

（编号为

0

）和一个新的汇点

tgt

（编号为

n

+

m

+ 1

）。

E

包含

n + m + k

条边

在新的

src

顶点到从

S

映射过来的顶点之间添加

n

条边，并在新的

tgt

顶点到从

T

映

射过来的顶点之间添加

m

条边。对于

k

对匹配中的每一对匹配

p

k

= (

s

i

,

t

j

)

，添加边（

i

,

n

+

j

）。所有边的容量都必须为

1

。

在流网络图

G

中计算出的最大流就是原始二分图匹配问题中的最大匹配集合，这已经过

证明（

Cormen

等，

2009

）。例如，考虑图

8-6a

中两对匹配

(

a

,

z

)

和

(

b

,

y

)

组成的最大匹

配集合，依照上述过程构造的流网络如图

8-6b

所示，其中

1

号顶点对应

a

，

4

号顶点对应

x

，

以此类推。我们可以进一步改善解决方案来选择三对匹配：

(

a

,

z

)

、

(

c

,

y

)

和

(

b

,

x

)

。在找

到一条增广路

<0, 3, 5, 2, 4, 7>

之后，该算法会对流网络进行相应的调整。应用增广路径 ...