9 参照上述解除交叉法来解除一个匹配并连接另一个匹配.男性先与自己更偏好的女性匹配,但如果女性相对于这个匹配有更偏好的单身男性可选,那么就会选择自己更偏好的匹配;而失去匹配的男性就要重复进行这一操作,选择自己当下最偏好的女性继续尝试匹配.因此,女性每次都可以和自己更偏好的男性匹配,而男性每次重新确定的匹配都是比与原配更差的选择. -  - 译者注
9.5 Ford-Fulkerson 最大流算法
应用
寻找飞机乘客疏散路线中的瓶颈或者电网中的电阻,很多问题都可以用图的最大流问题来建模.
定义
给定一个有向图 G(V, A),并在弧上标注容量
c
:A->R
+
,选择两个独立顶点:一个源点
s
∈V 和一个汇点
t
∈V.为