二分图中的最大匹配

Question

我陷入了二分图问题中的最大匹配.问题是这样的:

给定一个带有圆形孔的板并给出一组n个圆盘.孔编号为h ₁,...,h _m,圆盘编号为d ₁,...,d _n.

我们有一个m行和n列的矩阵A. A [i] [j] = 1如果h _我可以适合d _Ĵ(即,h的直径_我 ≥直径d的_Ĵ),否则为0.

鉴于任何孔最多只能包含一个圆盘的条件,我需要找到最大孔的配置.

我已经读过这个问题可以建模到网络流量问题,但不能完全遵循如何.有人可以解释如何做到这一点？另外,有没有我可以看到的C代码？

Answer 1

从二分匹配到最大流量的减少实际上非常漂亮.当您获得二分图时,您可以将图形视为由第一列到第二列的边连接的两列节点:

  A ----- 1
  B --\   2
  C    \- 3
 ...     ...
  Z       n

要将问题减少到最大流量,首先要将所有边缘从第一列引导到第二列,以便流程只能从左列移动到右侧.执行此操作后,您将引入两个新节点s和t作为源节点和终端节点.定位s使其连接到左侧的所有节点和t,以便右侧的每个节点都连接到它.例如:

     A ----- 1
 /   B --\   2   \
s-   C    \- 3   - t
 \  ...     ...  /
     Z       n

这里的想法是,你可以从s到t的任何路径都必须输入左列中的一个节点,然后将一些边缘交叉到右边的列,然后从那里到t.因此,匹配和st路径中的边缘有一个简单的一对一映射:只需从s到边缘的源路径,然后跟随边缘,然后沿着边缘从端点到节点吨.此时,我们的目标是找到最大化从s到t的节点不相交路径数量的方法.我们可以使用如下的最大流量来实现这一点.首先,将每个边缘的容量设置为s,这样可以确保最多一个流量单位进入第一列中的每个节点.类似地,将穿过两列的每条边的容量设置为1,确保我们选择边缘或不选择边缘,而不是可能选择具有多重性的边缘.最后,将离开第二列的边的容量设置为t也是一.这确保了右侧的每个节点只匹配一次,因为我们不能通过它推动多个流量单位.

构建流网络后,使用任何标准算法计算最大流量. Ford-Fulkerson是一种在这里表现良好的简单算法,因为图中的最大流量等于节点数量.它的最差情况是O(mn).或者,高度优化的Hopcroft-Karp算法可以在O(m√n)时间内完成此操作,这可能会更好.

至于C实现,快速Google搜索Ford-Fulkerson步骤就出现了这个链接.在将流程网络传递给此代码之前,您需要构建流程网络,但构造并不太复杂,我认为您不应该遇到太多麻烦.

希望这可以帮助!