最小割与最大流

发表于 更新于 阅读次数： Artalk：

简介：

最大流与最小割问题常用于matching问题、clustering问题等等...

**最小割问题：**在一个带权重的图中找出一个将所有顶点分为两类的分割方法，切分割的边权重合最小（实际上就是一种对于边的cut）。

**最大流问题：**在一个带权有向图中，找出可能的最大流量从 S->T。

最小割问题

一个cut相当于将vertex分为两类，其中会切开一些边，找到最小的切分方法。

最小割问题在研究网络最薄弱环节相关问题上具备广泛应用。而这个问题如今也依旧是一个open problem。

如今主要有这么两类随机算法来解决这一问题：

  1. LAS VEGAS ALGORITHMS：保证正确性，但运行时间有random性（类如quick sort）

  2. MONTE CARLO ALGORITHM：正确性不一定保证，但运行时间efficient

Karger's algorithm

Pick a random edge, contract it, and repeat until you only have 2 vertices left.

正确的概率 >1/(n2)> 1 /\left(\begin{array}{l} n \\ 2 \end{array}\right) 刚好分得的是正确的2 组

最大流问题

对于一个有向图 有起点S、终点T, 计算从S到T的最大流量。

例如这是一种流：

对于给定S和T的图，最大割与最小流相等,证明略

Fold-Fulkerson Algorithm

核心：构建Residual Graph

起始于任意的一个flow

循环

​ 构建residual graph

​ 在redisual graph上寻找可能的更新path，

​ 若不存在augment path证明目前的flow最大，结束。

​ 若存在augment path, 更新flow。

结束

寻找augment path的方式:

  1. Non-full forward edges
  2. Non -empty backward edges