graphalgorithms-資料下載頁(yè)
2025-07-15 18:50本頁(yè)面
【正文】 be reduced to maximum flow problem. Here give two examples. ? Reduce to work flow with single source and single sink ? Introduce a supersource s which is directly connected to each of the original sources si with a capacity c(s,si)=? ? Introduce a supersink t which is directly connected from each of the original sinks ti with a capacity c(si,s)=? 20 Maximum bipartite matching ? Matching in a undirected graph G=(V,E) – A subset of edges M?E, such that for all vertices v?V, at most one edge of M is incident on v. ? Maximum matching M – For any matching M′, |M|?| M′|. ? Bipartite: V=L?R where L and R are distinct and all the edges go between L and R. ? Practical application of bipartite matching: – Matching a set L of machines with a set R of tasks to be executed simultaneously. – The edge means that a machine can execute a task. 21 Copyright 169。 The McGrawHill Companies, Inc. Permission required for reproduction or display. 22 Finding a maximum bipartite matching ? Construct a flow work G′=(V′,E′,C) from G=(V,E) as follows where =L?R: – V′=V?{s,t}, introducing a source and a sink – E′={(s,u): u?L} ? E ?{(v,t): v?R} – For each edge, its capacity is unit 1. ? As a result, the maximum flow in G′ is a maximum matching in G. 23 Copyright 169。 The McGrawHill Companies, Inc. Permission required for reproduction or display.
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1