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

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

        時間:2024-07-12  來源:合肥網(wǎng)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. 無相關信息
        合肥生活資訊

        合肥圖文信息
        急尋熱仿真分析?代做熱仿真服務+熱設計優(yōu)化
        急尋熱仿真分析?代做熱仿真服務+熱設計優(yōu)化
        出評 開團工具
        出評 開團工具
        挖掘機濾芯提升發(fā)動機性能
        挖掘機濾芯提升發(fā)動機性能
        海信羅馬假日洗衣機亮相AWE  復古美學與現(xiàn)代科技完美結合
        海信羅馬假日洗衣機亮相AWE 復古美學與現(xiàn)代
        合肥機場巴士4號線
        合肥機場巴士4號線
        合肥機場巴士3號線
        合肥機場巴士3號線
        合肥機場巴士2號線
        合肥機場巴士2號線
        合肥機場巴士1號線
        合肥機場巴士1號線
      4. 短信驗證碼 酒店vi設計 NBA直播 幣安下載

        關于我們 | 打賞支持 | 廣告服務 | 聯(lián)系我們 | 網(wǎng)站地圖 | 免責聲明 | 幫助中心 | 友情鏈接 |

        Copyright © 2025 hfw.cc Inc. All Rights Reserved. 合肥網(wǎng) 版權所有
        ICP備06013414號-3 公安備 42010502001045

        主站蜘蛛池模板: 中文字幕乱码人妻一区二区三区| 国产一区二区电影在线观看| 人妻精品无码一区二区三区| 国产av福利一区二区三巨| 日本在线视频一区二区| 日韩欧国产精品一区综合无码| 国产产一区二区三区久久毛片国语 | 日本一区二区免费看| 国产视频一区在线播放| 亚洲影视一区二区| 无码精品人妻一区二区三区人妻斩| 一区二区三区视频网站| 国产在线观看一区二区三区四区 | 欧洲精品无码一区二区三区在线播放 | 亚洲一区二区三区国产精品无码| 亚洲综合无码AV一区二区 | 日韩免费观看一区| 精品乱人伦一区二区三区| 99久久精品国产免看国产一区 | 国产一区二区三区播放心情潘金莲| 少妇精品久久久一区二区三区| 自慰无码一区二区三区| 美女一区二区三区| 亚洲av无码不卡一区二区三区| 国产在线无码视频一区二区三区 | 免费视频精品一区二区| 国产天堂在线一区二区三区| 日本一区中文字幕日本一二三区视频 | 国产午夜精品片一区二区三区| 亚洲天堂一区在线| 亚洲字幕AV一区二区三区四区| 中文字幕精品一区二区2021年| 无码精品一区二区三区| 国产综合精品一区二区| 一区二区三区www| 国产成人一区二区三区在线| 日本不卡免费新一区二区三区| 无码精品黑人一区二区三区 | 亚洲午夜精品一区二区公牛电影院 | 国产精品美女一区二区三区 | 爆乳熟妇一区二区三区|