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

网络流算法

｜

219

网络流算法

一个衍生版本又名多重物资流问题，泛化之后就是最大流问题。简单地说，这种问题中

的网络具有多个源顶点和汇点，例如考虑在多个源顶点

s

i

和汇点

t

i

之间运输物资。尽管

边的容量是固定的，但是每对汇点和源顶点的使用需求并不一样。现实中，这种算法被

应用于解决无线网络中的路由问题（

Fragouli

和

Tabet

，

2006

）。

Leighton

和

Rao

曾经写

过一篇被广泛引用的关于多重物资流问题的文章（

1999

）。

最大流的一些简单延伸如下：

顶点容量

如果流网络中的每个顶点

v

都有一个最大容量

k

(

v

)

，那么将会如何呢？我们可以通

过构建一个修改过的图

G

m

来解决问题。为

G

中的每个顶点

v

，构建两个顶点

v

a

和

v

b

，并且创建一条流容量为

k

(

v

)

的边

(

v

a

,

v

b

)

。对于

G

中容量为

c

(

u

,

v

)

的入边

(

u

,

v

)

，

在修改后的图中创建容量为

c

(

u

,

v

)

的新边

(

u

,

v

a

)

。而对于

G

中的输出边

(

v

,

w

)

，在

G

m

中创建容量为

k

(

v

)

的边

(

v

b

,

w

)

。解出

G

m

也就得到了

G

的解。

无向边

如果流网络

G

中有着无向边，该怎么办呢？我们可以构建一个拥有相同顶点集合的

流网络

G

m

。对于

G

中容量为

c

(

u

,

v

)

的边

(

u

,

v

)

，在新图中创建一对边

(

u

,

v

)

和

(

v

,

u

)

，

每条边的容量都为

c

(

u

,

v

)

。解出

G

m

也就得到了

G

的解。

8.3 二分图匹配

匹配问题有多种形式。例如，五个求职者面试五个职位。每个求职者都已经列出了自己

能胜任的职位，现在的任务就是尽可能多地将工作分配给求职者，但是每份工作只能提

供给一位求职者。 ...