Week 15

Question

Click to Open Question

Answer

Q1

• yee

題目

【解題思路】

將原先的點分為兩個，並且中間加上一條邊表示原先的

$vertexcapacities$，這樣新生成的

$G^{\prime }=(V^{\prime },E^{\prime })$就可以不含

$vertexcapacities$並維持原先的

$maximumflow$。

【圖示】

$$\begin{gathered} |V^{\prime }|\Rightarrow 2|V| \\ |E^{\prime }|\Rightarrow |V|+|E| \end{gathered}$$

Q2

• xian

【題目】

Show the execution of the Edmonds-Karp algorithm on the flow network of Figure26.1(a).

$$

BFS第一輪

$s\to v_1\to v_3\to t$, min capacity = 12, max flow = 12

BFS第二輪

$s\to v_2\to v_4\to t$, min capacity = 4, max flow = 12 + 4

BFS第三輪

$s\to v_2\to v_4\to v_3\to t$, min capacity = 7, max flow = 16 + 7

最後答案 maxflow = 23

${}_{\mathrm{\#}}$

Q3

• chung

題目

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.

【解題思路】

Edge Connectivity定義：給一個graph，至少要去掉多少條邊才能使得該圖變為非連通圖

1. 因為題目要求maximum-flow algorithm，因此需先將無向圖變成有向圖
2. 將所有邊的capacity設為1
3. 固定圖上任意一個節點作為source，並對其他
   $V-1$個點做maximum-flow algorithm，
   $f(u,v)$表示u到v的最大流量，所求edge connectivity為
   $c=mi{n}_{v\ne u}f(u,v)$

因此在flow networks上做

$|V|-1$次的maximum-flow algorithm 即可求出Edge Connectivity

示意圖

【時間複雜度】

Ford – Fulkerson algorithm

$O(E\ast V)$
求 min(max flow) At 
Time Complexity = O(EV) * (V – 1) = O(EV^2)

【Psuedocode】

Find_edgeconnectivity(gragh G, c){
    在 G 中找一個 s
    For u, v in G:
        C(u, v) = 1
    For each t in G -s: // sink
        Ford_Fulkerson_ algorithm(G, s, t, c) // find max flow
Return min(max flow)
}

Q4

• songchiu

題目

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

去年有人寫的，看不懂

網路上的解答，研究中

令

$(S,T)$和

$(X,Y)$為

$G$和

$G^{\prime }$中的兩個

$\text{cut}$
令

$c$、

$c^{\prime }$分別為

$G$、

$G^{\prime }$的

$\text{capacity function}$

給定

$c^{\prime }(u,v)=c(u,v)+i$ (其中

$u,v$為頂點，

$i$為很小的正值)

1. 若
   $c(S,T)=c(X,Y)$且
   $(S,T)$的邊數少於
   $(X,Y)$的邊數，則
   $c^{\prime }(S,T)<c^{\prime }(X,Y)$
   因此
   $i$的值要謹慎挑選才行。
2. 若
   $c(S,T)<c(X,Y)$且
   $(S,T)$的邊數多於
   $(X,Y)$的邊數，仍要讓
   $c^{\prime }(S,T)<c^{\prime }(X,Y)$
   因此可以根據
   $c^{\prime }$的定義得知，
   $G^{\prime }$的
   $\text{minimum cut}$會是
   $G$當中的
   $\text{minimum cut}$，且有最少邊數

此時來挑

$i$，令

$i={\displaystyle \frac{1}{|E|+1}}$
對任意

$c(S,T)$，

$c(S,T)\le c^{\prime }(S,T)\le c(S,T)+|E|\times i$

令

$c(S,T)<c(X,Y)$，證明

$c^{\prime }(S,T)<c^{\prime }(X,Y)$

$\begin{array}{rl}{c}^{\prime }(S,T)& \le c(S,T)+|E|\times i\\ & =c(S,T)+{\displaystyle \frac{|E|}{|E|+1}}\\ & <c(X,Y)(\because c(X,Y)-c(S,T)\ge m)\\ & \le c^{\prime }(X,Y)\end{array}$

由於

$c(S,T)+{\displaystyle \frac{|E|}{|E|+1}}$這個值比起原圖中的

$\text{second smallest value cut}$還要大
因此可以知道，要加一個很小的常數，才有辦法解決掉這件事情
讓新圖的

$\text{minimum cut}$有

$\text{smallest possible number of edges}$

Q5

• null

It's a min cut problem with all edge has 1 as max flow.

• maximum-flow can find the min cut for a s-t cut
• for any point in the graph, there must be at least one point is on the other side of the min s-t cut.
• So choose one vertex in the graph as fixed source, and run every other vertices as target, the minimal flow of all s-t cut is the min cut of the graph
• Algorithm: Run maximum-flow for
  $|V-1|$ time so the time complexity is
  $O(V^2{E}^2)$ if we use Edmonds-Karp that takes
  $O(V{E}^2)$ each time

Edmonds-Karp(G, s, t):
    capacity = 0
    while true:
        path=findShortestAugmentinPath(G, s, t)
        if path!=null:#null means no capacity can be added
        capacity+=path.minimalEdgeCapacity
    return capacity

findConnectivity(G):
    minimal=inf, s=1
    for t in G.V and t!=s:
        minimal=min(minimal,Edmonds-Karp(G, s, t))
    return minimal

Q6

• LXS

【題目】

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.

【Sedgewick’s algorithms】

We can implement this by using a priority queue and slightly modifying our implementation of Dijkstra’s shortest-paths algorithm, choosing edges from the priority queue to give the maximum amount of flow that can be pushed through a forward edge or diverted from a backward edge.

【解題思路】

Residual Networks中，每個有向邊可是視為「可以重新配置水流的方向」。

此時找使 flow 增加最大之 Augmenting Paths，相當於找到從Source到Sink的最長路徑 P 長度為 =

$Mi{n}_{e\in P}w(e)$，並使用類似Prim的方式找到最大flow。

【Psuedocode】

pq = PriorityQueue() # maxheap of flow
def maxflow():
    Initialize all flow[v] to -∞ #增加的flow
    flow[Source] = ∞
    while not pq.empty():
        u = pq.pop()
        if(u is Sink): # flow最大為Sink則break
            break
        else:
            foreach edge (u, v):
                if min(flow[u],residualCapacity[u,v]) > flow[v]: # 可以流入更多flow
                    flow[v] = min(flow[u],residualCapacity[u][v])
                    p[v] = u
                    pq.changePriority(v) to flow[v]

【正確性】

由於每次都從⽬前最⼤Flow的路徑繼續往下找，若該條路徑不再是最⼤的Flow，那再下⼀輪挑⽬前最⼤的點的時候，就不會是該點，因此能確保正確性。

Q7

• xian

【題目】

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.

【分析】
因為s是源頭，所以代表如果f(v,s)存在，則代表G有一個會經過s到v在回到s的迴圈，且因為f(v,s) = 1，所以代表此迴圈上每個edge皆為整數，所以如果把flow都減1，也不會有負數的問題。
而我們知道迴圈在flow裡面就只是原地繞圈，所以如果把迴圈移除的話，|f|也依舊不變，因為他們的差值並沒有改變，所以如果我們把迴圈上的所有邊的值減一，則f'(v,s) = f(v,s) - 1 = 0，因此我們的目的就是要找到迴圈，迴圈即為所要之解答。

【演算法】
1.邊跑 DFS 看有沒有遇到 source，走到底沒有遇到則 pop 該點
2.如果找到迴圈，則將 stack 中的點的邊減 1
3.更改完的 f 即為 f'

//G[v,s]代表v到s所流通的值，f(u,v)代表圖上的flow
dfs(p){
    for v in adj[p]:
        if f(p,v) > 0:
            if v is not visited
                set v as visited
                stack.push(v)
                dfs(v)
                set v as unvisited
                stack.pop
            else if v == source
                t = top = stack.pop()
                while !stack.empty:
                    f(t, stack.top())--
                    t = stack.pop()    
                return true
}    

複雜度:
DFS最多將全部的邊走完，

$V\le E$，所以

$O(V+E)=O(E)$