课程主页:

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频:

https://www.bilibili.com/video/BV1wK411g7ck

这次回顾Section 7。

1. Job Assignment

(a)

优化的变量是第$i$个人在第$j$个工作上分配的时间$x_{ij}$。

(b)

约束:

(c)

优化目标为

2. Understanding convex polytopes

(a)

任取$x,y \in \Omega$,那么

$\forall \lambda\in [0,1]$,我们有

因此

即$\Omega$是凸集。

(b)

注意$g(\lambda)$关于$\lambda$是线性函数,并且$\lambda\in [0,1]$,所以最大值在$\lambda = 0$或$\lambda =1$处取到。

(c)

如果全局最大值$x$不是顶点,那么$x$在端点是$y,z$的线段上,根据(b)可得

3. Residual in graphs

(a)

略。

(b)

最大流为$11$,分别为:

  • $4:S\to A\to C\to T$
  • $3: S\to A\to B\to T$
  • $4:S\to B\to T$

最小割为:

  • $\{S,A,B\}, \{C,T\}$

4. Verifying a max-flow

只要验证删除最大流后的剩余网络$G^f$不存在$S$至$T$的路径即可,利用DFS即可解决,时间复杂度为$O(|V|+|E|)$。