今天给同学们讲解fm network中cuts的定义，计算cut的capacity, 三种不同的二分图和如何运用二分图和Hungarian algorithm的方法计算出耗时/耗材最少的方法。

如上图 根据定义 图一为cut 第二不是一个cut

如何计算cut的capacity：

只计算从source向sink方向的 从sink到source方向的忽略不计 

Bipartite graph：二分图

Directed bipartite graph: 带有方向的二分图

Complete weighted bipartite graph: 完整的加权二分图 左边的全部连接到右边

The Hungarian algorithm可以用来计算在上面完全加权二分图中最有效率，最节省时间的方法 。

具体过程如下：图下的table叫coat matrix

• 第一步：将每一横行的数字减去这一行的最小数字 得到以下table

• 第二步：将有数字0的竖行画一条线 如果只得到三条线则跳到第三步 如果得到四条线跳到第五步

• 第三步：找到没有数字0的竖行并将此竖行的每个数字减去此行的最小值

• 第四步：如果还是（最少）三条线就能覆盖图中所有的数字0则继续第五步 如果得到四条线跳到第五步

• 第五步a：找出没有被线覆盖的数字中的最小值 加到三条线的交点上 并在没有被线覆盖的六个数中减去最小值 得到下图

• 第五步b：重复第四步 用最少的线把所有的0盖住 得到下图

• 第六步：根据上图的table画出二分图 table中为零的数则代表耗时最少/耗材最少

• 第七步：计算最少时间

Minimum time taken to finish the work is 20+30+50+30=130 minutes

责任编辑/转载：猫叔徐超

* 更多视频关注公众号“曙光VCE”或小红书“墨尔本曙光VCE”