Answer of assignment 5 r 3 Minimum cut: Vs={s, V1}, Vt = {v2, v3, v4, v5, t} r 7
Download 155.28 Kb.
|
- Navigate this page:
- R-8.12 Step1: length=2
- Step2: length=3
- Step3: length=3
- Step4: length=3
| Answer of assignment 5
R-8.3 Minimum cut: Vs={s, V1}, Vt = {v2, v3, v4, v5, t} R-8.7 Build a residual graph as follows, The residual graph has the same nodes as the flow network For each directed edge (u,v) of the network, If the residue capacity of the edge from u to v is >0, then add an directed edge from u to v in the residue graph If the residue capacity of the edge from v to u is >0, then add an directed edge from v to u in the residue graph Then the number of edges residual graph is at most 2m. Do a BFS on the residual graph starting at node s. If a node is reachable from s by BFS, then put it in set Vs, otherwise put it in set Vt. The two sets will form a minimum cut. Constructing the residual graph take O(n+m) time, where n is the number of nodes and m is the number edges. The running time of BFS is O(n+m). Since the flow network is connected. Thus m>=n-1. Thus O(n+m)=O(m). R-8.9 Let X ={x1; x2;… ; xn} and Y ={y1; y2; … yn}. We can count all possible matchings inductively. There are n ways to match x1 with vertices in Y. Given this match, there are still n−1 ways to match x2 with vertices in Y. Given the previous matches, there are still n−2 ways to match x3 with vertices in Y, and so on. Ultimately, given previous matches, there will be n−(n−1) =1 way to match xn. Thus, there are n! possible matches. R-8.12 Step1: length=2 
Step2: length=3 
Step3: length=3 
Step4: length=3 
Download 155.28 Kb. Share with your friends:
|