Weighted Matchings
In Chap. 13 , we studied matchings of maximal cardinality. The present chapter discusses the more general case of weighted matchings, that is, the problem of finding a matching of maximal weight (with respect to a given weight function on the edges). In
- PDF / 888,926 Bytes
- 39 Pages / 439.37 x 666.142 pts Page_size
- 15 Downloads / 193 Views
Weighted Matchings
What we know as fate is two neuroses knowing that they’re a perfect match. J. Arch, N. Ephron & D.S. Ward
In the previous chapter, we studied matchings of maximal cardinality (the cardinality matching problem). The present chapter is devoted to weighted matchings, in particular to the problem of finding a matching of maximal weight in a network (G, w) (the weighted matching problem). In the bipartite case, this problem is equivalent to the assignment problem introduced in Example 10.1.4, so that the methods discussed in Chap. 10 apply. Nevertheless, we will give a further algorithm for the bipartite case, the Hungarian algorithm, which is one of the best known and most important combinatorial algorithms. We proceed by explaining the connection between matching problems and the theory of linear programming, even though we generally avoid linear programs in this book. We need this to see the deeper reason why the approach used in the Hungarian algorithm works: its success is due to the particularly simple structure of the corresponding polytope, and ultimately to the total unimodularity of the incidence matrix of a bipartite graph. In this context, the significance of blossoms will become much clearer, as will the reason why the determination of maximal matchings (weighted or not) is considerably more difficult for arbitrary graphs than for bipartite ones. It would make little sense to describe an algorithm for the weighted matching problem in general graphs without using more of the theory of linear programming; for this reason, no such algorithm is presented in this book. Nevertheless, we will include three interesting applications of weighted matchings: the Chinese postman problem (featuring a postman who wants an optimal route for delivering his mail); the determination of shortest paths for the case where edges of negative weight occur; and the decoding of graphical codes. We shall conclude with a few remarks about matching problems with certain additional restrictions—a situation which occurs quite often in practice; we will see that such problems are inherently more difficult. D. Jungnickel, Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics 5, DOI 10.1007/978-3-642-32278-5 14, © Springer-Verlag Berlin Heidelberg 2013
441
442
14
Weighted Matchings
14.1 The Bipartite Case Let G = (V, E) be a bipartite graph with weight function w : E → R. As usual, the weight w(M ) of a matching M of G is defined by w(e). w(M ) = e∈M
A matching M is called a maximal weighted matching if w(M ) ≥ w(M ) holds for every matching M of G. Obviously, a maximal weighted matching cannot contain any edges of negative weight. Thus such edges are irrelevant in our context, so that we will usually assume w to be nonnegative; but even under this assumption, a maximal weighted matching is not necessarily also a matching of maximal cardinality. Therefore we extend G to a complete bipartite graph by adding all missing edges e with weight w(e) = 0; then we may assume that a matching of maximal w
Data Loading...
