---
title: Homework XIV
---
# P1
[CLRS 3rd] Exercise 26.1-7
- [ ] [name=民]
## Topic
Suppose that, in addition to edge capacities, a flow network has vertex capacities. That is each vertex $v$ has a limit $l(v)$ on how much flow can pass though $v$. Show how to transform a flow network $G=(V,E)$ with vertex capacities into an equivalent flow network $G′=(V′,E′)$ without vertex capacities, such that a maximum flow in $G′$ has the same value as a maximum flow in $G$. How many vertices and edges does $G'$ have?
## Solution
我們將原來 graph G 裡的vertex 分成兩個 vertex 分別是 v1 和 v2。
在這個情況下，v1 和 v2 之間的 edge 就是 vertex capacity $l(v)$。
因為任何通過原本 graph G 裡 vertex 的 flow 一定會通過新vertex (v1,v2) 的edge。
所以這個新的 flow network $G'$ 就會有 $2|V|$ vertices 以及 $|V|+|E|$ 個 edges。
# P2
[CLRS 3rd] Exercise 26.2-3
- [ ] [name=Joe]
> https://www.youtube.com/watch?v=RppuJYwlcI8 5:00
> [name=昱]
## Topic
Show the execution of the Edmonds-Karp algorithm on the flow network of Figure 26.1(a).
## Solution
road
$\begin{array}{c}
s-v_1-v_3-t=12\\
s-v_2-v_4-t=4\\
s-v_2-v_1-v_3-t=7\\
\end{array}$
所以max flow = 23
# P3
[CLRS 3rd] Exercise 26.2-11
- [ ] 賴
## Topic
The edge connectivity of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is $1$, and the edge connectivity of a cyclic chain of vertices is $2$. Show how to determine the edge connectivity of an undirected graph $G = (V, E)$ by running a maximum-flow algorithm on at most $|V|$ flow networks, each having $O(V)$ vertices and $O(E)$ edges.
## Solution
先將undirected graph轉成directed graph並對此建立flow network，把每條edge的capacity設為1，接著對各個vertex當作source做maximum-flow algorithm找出他們匯向其他點時的maximum flow value，從獲得的這些數字中再找出最小值，此值即為該圖的edge connectivity。
# P4
[CLRS 3rd] Exercise 26.2-12
## Topic
Suppose that you are given a flow network $G$, and $G$ has edges entering the source $s$. Let $f$ be a flow in $G$ in which one of the edges $(v,s)$ entering the source has $f(v,s)=1$. Prove that there must exist another flow $f′$ with $f′(v,s)=0$ such that $∣f∣=∣f′∣$. Give an $O(E)-time$ algorithm to compute $f′$, given $f$, and assuming that all edge capacities are integers.
## Solution
f(v,s)=1代表一定有一條path從source流向v
因此path(s,v)和edge(v,s)會形成一個cycle
而cycle會占用容量但不會增加總流量
每個flow不為0的點一定能從祖先回溯到source
因此,只要把f(v,s)和任一條流量大於0的path(s,v)流量-1
就能形成一個f'(v,s)=1-1=0的Flow == 不流過cycle
找迴圈的方法則是從edge(v,s)開始往回找parent,最後會回到source
每條回溯過的邊做記號能讓時間複雜度從O(E.f)降到O(E)
```pseudo=
DFS(v){
for each u ∈ parent[v] && f(u,v)>0 && edge(u,v) unmarked
f(u,v)-=1;
if(u==s)
return true; //end DFS
else
marked<-edge(u,v);
DFS(u);
}
```
# P5
[CLRS 3rd] Exercise 26.2-13
## Topic
Suppose that you wish to find, among all minimum cuts in a flow network G with integral capacities, one that contains the smallest number of edges. Show how to modify the capacities of $G$ to create a new flow network $G′$ in which any minimum cut in $G′$ is a minimum cut with the smallest number of edges in $G$.
## Solution
假設圖中不只一個min cut, 但是有一個cut的邊數最少, 若對圖中所有邊的capacity加上$\frac{1}{|E|+1}$, 所有原本的min cut的flow會增加邊數乘上$\frac{1}{|E|+1}$(最多增加$\frac{|E|}{|E|+1}$, 小於1), 則原本邊數最小的min cut增加最少flow, 仍為新圖的min cut, 其他min cut增加的flow比較多, 導致在新的圖中的min cut一定為原圖中邊數最少的min cut
# P6
[CLRS 3rd] Exercise 26.3-4
## Topic
A perfect matching is a matching in which every vertex is matched. Let $G=(V,E)$ be an undirected bipartite graph with vertex partition $V=L∪R$, where $|L|=|R|$. For any $X⊆V$, define the neighborhood of $X$ as
N(X)={y∈V:(x,y)∈E for some x∈X}
that is, the set of vertices adjacent to some member of $X$. Prove Hall's theorem: there exists a perfect matching in $G$ if and only if $∣A∣≤∣N(A)∣|A|$ for every subset $A⊆L$.
## Solution
[A$\Leftrightarrow$B] $\Leftrightarrow$ [(B$\rightarrow$A)∧(¬B$\rightarrow$¬A)
==Perfect Matching $\rightarrow$ |A|$\leq$|N(A)|:==
若有一點集合A符合|A|$>$|N(A)|, 則A裡絕對有點無法配對到(僧多粥少), 此圖也不會有perfect matching, 所以一個圖裡若有perfect matching, 則任一點集合A都必須符合|A|$\leq$|N(A)|
==¬Perfect Matching $\rightarrow$ ¬ |A|$\leq$|N(A)|:==
證明若不存在perfect matching, 會有一點集合|A|>|N(A)|:
令n=|L|=|R|
若是G不存在perfect matching 則maximum matching<=n-1
而maximum flow也會<=n-1，同時也會存在一個capacity<=n-1的cut S
令L1=S∩L , L2=L-S , R1=S∩R , R2=R-S
而Capacity(S)=|L2|+|R1|---(1)
因此 n-1>=|L2|+|R1| ---(2)
又|L2|=n-|L1|
=> |L1|>=|R1|+1 ----(3)
|N(L1)|=|R1| ----(4)
最後合併(3),(4) => |L1|>=|N(L1)|+1, 得到|A|>|N(A)|
得到Exist Perfect Matching $\Leftrightarrow$ |A|$\leq$|N(A)|
# P7
- [ ] [name=民]
## Topic
Give There are two extended ways used to find the augmenting path that we have mentioned in class (refers to slides p.14, Unit 10), please design an efficient algorithm with the argument of second method to find the augmenting path. Argue that your algorithm is correct and also analyze the time-complexity.
## Solution
```pesudo=
Max_heap H
H.insert(source)
while(|H|)
u=H.extractMax()
if(u==sink)
/*find bottleneck*/
v=sink
while(v!=source)
u=parent[v]
flow=min(flow,w(u,v))
v=parent[v]
/*reset weights*/
v=sink
while(v!=source)
u=parent[v]
w(u,v)-=flow
w(v,u)+=flow
maxFlow+=flow
H.clear()
H.insert(source)
u=H.extractMax()
for v in N(u)
if(w(u,v)>0)
d[v]=min(d[v],w(u,v))
parent[v]=u
H.insert(v)
```
Time-complexity: $O(|E|logF*|V|log|V|)$
# P8
- [ ] [name=Joe]
## Topic
Show that any comparison-based algorithm needs Ω(n log n) time to solve the following problem: Given n points in the 2D plane, construct a tree of minimum total length whose vertices are the given points and the edge length of an edge is the Euclidean distance between the two end points of the edge.
## Solution
1.sorting then use Kruskal or Prim algorithm
complexity$>=\Omega(nlogn)$
2.Closest pair of points problem
complexity$>=\Omega(nlogn)$
3.brute-force then use Kruskal or Prim algorithm
complexity$>=\Omega(nlogn)$
4.Delaunay triangulation then use Kruskal or Prim algorithm
``` pseudo=
graph g
void MSP(input){
sorting(input) \\soting complexity=nlogn
g = Delaunay(sorted_input) \\use D&C complexity=nlogn
do Kruskal or Prim algorithm\\because E=O(V),so complexity=vlogv=nlogn
}
```
complexity$=\Omega(nlogn)+\Omega(nlogn)+\Omega(nlogn)=\Omega(nlogn)$
Sign in with Wallet
Connect another wallet