合肥生活安徽新聞合肥交通合肥房產生活服務合肥教育合肥招聘合肥旅游文化藝術合肥美食合肥地圖合肥社保合肥醫院企業服務合肥法律

        MA214編程代做、代寫Python/C++程序語言

        時間:2024-07-12  來源:合肥網hfw.cc  作者:hfw.cc 我要糾錯



        MA214 Algorithms and Data Structures
        Exercises 10

        (Maximum flows and bipartite matching)

        Exercise 10.1. Multiple-source, multiple-sink maximum flow problem                 3 pts

        A maximum-flow problem may have several sources and sinks, rather than just one of each. For example, a company might actually have a set of M factories {s1, . . . ,sM} and a set of N warehouses {t1, . . . , tN}, between which it wants to send goods. A possible such network is shown below.

        (a) Extend the flow properties and definitions to the multiple-source, multiple-sink version of the problem.

        (b) Describe how to solve the multiple-source, multiple sink version of the prob-lem by “reducing” it to the single-source, single-sink problem. That is, describe how to construct a single-source, single-sink flow network from a multiple-source, multiple-sink network so that a maximum flow in the former corresponds to a maximum flow in the latter, and vice versa.

        (c) What is the time complexity of the algorithm proposed in the previous part?

        Exercise 10.2. Maximum flow and bipartite matching 4 pts

        An undirected graph G = (V, E) is bipartite if V can be partitioned into L and R = V ? L such that all edges run between L and R. A matching in G is a subset of edges M ? E such that for all vertices v ∈ V, at most one edge of M is incident with v. A maximum matching is a matching of maximum cardinality among all matchings of G.

        Given a bipartite undirected graph G = (V, E), we can find a maximum matching of G by using flows as follows: We construct a flow network G′ = (V′, E′) with V′ = V ∪ {s, t}, source s and target t,

        E′ = {(s, ?): ? ∈ L} ∪ {(r, t): r ∈ R} ∪ {(?,r): (?,r) ∈ G, ? ∈ L,r ∈ R} ,

        and capacity 1 for each edge in E′. An integer-valued flow in G′ is a flow f such that f(u, v) is an integer for each edge (u, v) of G′. That is, in our scenario here, we have f(u, v) ∈ {0, 1}. A maximum flow f in G′ that is an integer-valued flow then gives a maximum matching M in G by including in M all edges (?,r) with ? ∈ L and r ∈ R such that f(?,r) = 1. We can find such flow by using the Edmonds–Karp algorithm.

        Now, consider the following instance G = (V, E) of the maximum bipartite matching problem. Vertices on the left are in L, vertices on the right are in R = V ? L.

        (a) List all maximum matchings in this instance of the maximum bipartite matching problem.

        (b) Use the construction described above to obtain a flow network for this instance of the matching problem.

        (c) Pick any maximum matching found in (a), and give the corresponding flow in the flow network described in (b).

        (d) Give all minimum cuts in the flow network constructed in (b). What is the capacity of each of these cuts? What does this tell you about the maximum flow in the flow network, and the cardinality of any maximum matching?

        (e) Use the Edmonds–Karp algorithm on the flow network found in (b) to compute a maximum flow. Break ties among equal length augmenting paths lexicographi-cally. So any path that starts with u1 should be preferred over any path that starts with u3. Likewise, any path that starts with u2, v1 should be preferred over any path u2, v4. Re-draw the flow network and the residual network after each up-date.

        Exercise 10.3. Integer-valued flows and maximum matching                 3 pts

        The setup in this exercise is the same as in the previous exercise. We will prove that, as claimed in the previous exercise, there is a one-to-one correspondence between integer-valued flows in the flow network G′ = (V′, E′) and matchings in the undirected bipar-tite graph G = (V, E).

        (a) Show that if there is an integer-valued flow f of value |f| in G′, then there is a matching M in G of cardinality |M| = |f|.

        (b) Show that if there is a matching M in G of cardinality |M|, then there is an integer-valued flow f in G′ of value |f| = |M|.

        請加QQ:99515681  郵箱:99515681@qq.com   WX:codinghelp




         

        掃一掃在手機打開當前頁
      1. 上一篇:美國簽證能入境菲律賓嗎 可以停留多久呢
      2. 下一篇:申請菲律賓電子簽證所需的材料(辦理流程)
      3. 無相關信息
        合肥生活資訊

        合肥圖文信息
        出評 開團工具
        出評 開團工具
        挖掘機濾芯提升發動機性能
        挖掘機濾芯提升發動機性能
        戴納斯帝壁掛爐全國售后服務電話24小時官網400(全國服務熱線)
        戴納斯帝壁掛爐全國售后服務電話24小時官網
        菲斯曼壁掛爐全國統一400售后維修服務電話24小時服務熱線
        菲斯曼壁掛爐全國統一400售后維修服務電話2
        美的熱水器售后服務技術咨詢電話全國24小時客服熱線
        美的熱水器售后服務技術咨詢電話全國24小時
        海信羅馬假日洗衣機亮相AWE  復古美學與現代科技完美結合
        海信羅馬假日洗衣機亮相AWE 復古美學與現代
        合肥機場巴士4號線
        合肥機場巴士4號線
        合肥機場巴士3號線
        合肥機場巴士3號線
      4. 上海廠房出租 短信驗證碼 酒店vi設計

        主站蜘蛛池模板: 人妻内射一区二区在线视频| 久久精品国产一区二区| 国产色情一区二区三区在线播放| 夜夜添无码试看一区二区三区| 亚洲综合无码一区二区痴汉| 一区二区三区免费视频网站| 亚洲AV噜噜一区二区三区| 精品一区二区三区中文字幕 | 色综合视频一区中文字幕| 中文字幕aⅴ人妻一区二区| 视频一区二区精品的福利| 日韩视频免费一区二区三区| 亚洲制服丝袜一区二区三区| 日韩精品乱码AV一区二区| 国产成人一区二区三区视频免费 | 波多野结衣在线观看一区 | 国产肥熟女视频一区二区三区| 国产伦精品一区二区三区视频小说| 亚洲天堂一区二区三区四区| 国产丝袜视频一区二区三区| 久久99精品免费一区二区| 亚洲国产一区二区三区| 激情啪啪精品一区二区| 一区视频免费观看| 高清在线一区二区| 亚洲国产高清在线一区二区三区 | 亚洲色精品VR一区区三区| 无码精品视频一区二区三区| 亚洲AV无码一区二区三区DV| 熟女性饥渴一区二区三区| 亚洲一区二区三区在线观看精品中文| 亚洲国产精品成人一区| 久久亚洲色一区二区三区| 亚洲啪啪综合AV一区| 亚洲av无码一区二区三区不卡| 骚片AV蜜桃精品一区| 视频一区二区三区在线观看| AV怡红院一区二区三区| 色噜噜一区二区三区| 搜日本一区二区三区免费高清视频| 秋霞日韩一区二区三区在线观看|