AADS Assignment1 ideas
==

[TOC]

### 26.1-1
方法1：直接证明
- 情况1： 证明 max flow 不包含 G 中的 edge (u, v)，那么 max flow 也不会包含拆分后 G' 中的 edge (u, x) 和 edge (x, v)，因此不会影响 max flow。
- 情况2： 证明 max flow 包含 G 中的 edge (u, v)，那么 max flow 也包含拆分后 G' 中的 edge (u, x) 和 edge (x, v)，然后证明 u$\to$v 的 max flow 等于 u$\to$x$\to$v 的 max flow 即可。

方法2：用cut来证明
- G 变成 G' 后经过 (u, v) 的 capacity 的 cut 变成了两种情况，也就是说假设在图 G 中经过 (u, v) 的 cut 有 n 种，那么在图 G' 中则变为了经过 (u, x) 的有 n 种情况，经过 (x, v) 的也有 n 种情况。又因为 c(u, v) = c(u, x) = c(x, v) 所以最后算出来的 f 也不会变。
>或者说由后面的定理可知：最大流量等于最小割量，如果这个最小割没割到原来的（u，v）边，那（u，v）变不变成“（u，x），（x，v）”对最大流量|f|就没啥影响，就算最小割割到了原来的（u，v）边，在变成“（u，x），（x，v）”后，不论你割的是（u，x）边还是（x，v）边，（u，x）和（x，v）边容量和原来的（u，v）一样，导致最小割量仍然和原来一样，也就是最大流量|f|仍然不变
> [color=red]
> [name=任]

### 26.1-4
用 flow 的定义证明，flow 的定义如下：

- 证明容量限制：
$f_{new} = \alpha f_1 + (1 - \alpha)f_2$
$\forall u, v \in V, f_{new}(u, v) = \alpha f_1(u, v) + (1 - \alpha)f_2(u, v)$
$\because f_1(u, v) \in [0, c(u, v)]$
$f_2(u, v) \in [0, c(u, v)]$
$\alpha \in [0, 1]$
$\therefore 问题变成了一个二元一次方程求极限的问题$
$当f_1(u, v)和f_2(u, v)都取c(u, v)时，f_{new}(u, v) 在定义域上有最大值：$
$\alpha c(u, v) + (1 - \alpha) c(u, v) = c(u, v)$
$同理，当f_1(u, v)和f_2(u, v)都取0时，f_{new}(u, v) 在定义域上有最小值：$
$\alpha \times 0 + (1 - \alpha) \times 0 = 0$
$\therefore 0 \le f_{new}(u, v) \le c(u, v) 得证$

- 证明流量守恒：
$\sum_{v \in V} f_{new}(v, u)$
$= \sum_{v \in V} (\alpha f_1(v, u) + (1 - \alpha)f_2(v, u))$
$= \alpha \sum_{v \in V} f_1(v, u) + (1 - \alpha) \sum_{v \in V} f_2(v, u)$
$\sum_{u \in V} f_{new}(u, v)$
$= \sum_{u \in V} (\alpha f_1(u, v) + (1 - \alpha)f_2(u, v))$
$= \alpha \sum_{u \in V} f_1(u, v) + (1 - \alpha) \sum_{u \in V} f_2(u, v)$
$显然：\alpha \sum_{v \in V} f_1(v, u) = \alpha \sum_{u \in V} f_1(u, v),$
$(1 - \alpha) \sum_{v \in V} f_2(v, u) = (1 - \alpha) \sum_{u \in V} f_2(u, v)$
$\therefore \sum_{v \in V} f_{new}(v, u) = \sum_{u \in V} f_{new}(u, v) 得证$

### 26.1-7
使用如下结构代替原图中的每个节点就可以了：
所以 G' 应该有 2V 个节点, E + V 条边。

### 26.2-2
$f = 11 + 1 + 7 + 4 - 4 = 19$
$c = 16 + 4 + 7 + 4 = 31$

### 26.2-3

解法如图：

### 26.2-4

下图为最小切割：
$c = 12 + 7 + 4 = 23$

\(c\) 抵消了 (a) 中v3到v2的流量 和 (b) 中v2到v1的流量

### 26.3-2
Proof:
Here we use induction to prove the therom 26.10. After the first loop of Ford-Fulkerson, because capacity function c takes on only integral values and all f(u,v) $(u,v) \in E$ in the flow network are initially 0, so the $c_f$ takes on only integral values, so $f_p$ (where p is the augmentation path in residual network) takes on only integral values making $|f|$ and all f(u,v) $(u,v) \in E$ of the flow network after augmentation are both integral values.
Then, we assume that after nth loops $|f|$ and all f(u,v) $(u,v) \in E$ of the flow network are both integral values.
Next, in (n+1)th loop, because after nth loops $|f|$ and all f(u,v) $(u,v) \in E$ of the flow network are both integral values, the capability of each edge in residual network only takes integral values
$(26.2)$
where $c_f(p)=...$, so $|f_p|=c_f(p)$ only takes integral values, and as we assume that after nth loops, $|f|$ and all f(u,v) $(u,v) \in E$ of the flow network are both integral values, so after (n+1)th loop, the value of flow will become $|f \uparrow f_p| = |f|+|f_p|$ and it only takes integral values. Since (equation 26.4), $(f \uparrow f_p)(u,v) (u,v) \in E$ only takes integral values.


### submit

<iframe src="https://www.slideshare.net/slideshow/embed_code/key/e5IUwH2mH6VnZf?hostedIn=slideshare&page=upload" width="800" height="1000" frameborder="0" marginwidth="0" marginheight="0" scrolling="no"></iframe>