《第08章网络流和匹配习题答案.docx》由会员分享，可在线阅读，更多相关《第08章网络流和匹配习题答案.docx（4页珍藏版）》请在三一文库上搜索。
1、第08章网络流和匹配习题答案第08章网络流和匹配习题答案CS600 homework8 answerXiang Xu 10388813R-8.2R-8.2 Answer the following questions on the flow network N and flow / 比国Figure 8.6a：国，.- Whai are the forward edges of augmenting path Tt? What are the bacedges? How many augmenting paths are there with respect to flow /?琏 such
2、pathT list die sequence of vertices of the path and the residual & of the path, What if the value of a maximum flow in V?Answer:a) forward edges: (s, v2), (v2, v3), (v1, v4), (v4, t) back edges: (v3, v1)b) Six.1. s, v1, v3, v4, t32. s, v1, v4, t23. s, v2, v3, v1, v4, t24. s, v2, v3, v4, t35. s, v3,
3、v1, v4, t,16. s, v3, v4, t1 c) 15C-8.3C-8.3 Let N be & flow network with n vertices and m edges. Show how to compute an augmenting path with the largest residual capacity in O(n+/H)logn) time. Answer:1) Generate residual graph Rf, and the let theA f(u,v) be the weight of each directed edge(u ,v).2)
4、Use the modification of Prim-Jarnik (Dijkstra) Algorithm to generate a minimum spanning tree T with directed edges:a) initialize a cluster C containing only s; add all the vertices of N into T.b) find the directed edge(u, v) with the possiblelargest weight such that (u G C) but (v not G C); add edge(u, v) into T and v into C.c) repeat step-b until all the vertices are inside C.3) (For every vertex v in T, there is only one edge destined at v.) Starting from t, add t and edge(u, t) to result path, then repeat to do the same things to u, until s is reached.