试题详情
简答题 用Ford-Fulkerson的标号算法求下图中所示各容量网络中从vs到vt的最大流，并标出其最小割集。图中各弧旁数字为容量cij，括弧中为流量fij。
  • 对上有向图进行2F标号得到

    由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得

    由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK相交的弧的集合，即为

  • 关注下方微信公众号，在线模考后查看

热门试题