Matching Theory (eBook)

L. Lovasz, M.D. Plummer (Autoren)

eBook Download: PDF

1986 | 1. Auflage
543 Seiten
Elsevier Science (Verlag)
978-0-08-087232-2 (ISBN)

Infos

This study of matching theory deals with bipartite matching, network flows, and presents fundamental results for the non-bipartite case. It goes on to study elementary bipartite graphs and elementary graphs in general. Further discussed are 2-matchings, general matching problems as linear programs, the Edmonds Matching Algorithm (and other algorithmic approaches), f-factors and vertex packing.

Inhalt

Front Cover 1
Matching Theory 4
Copyright Page 5
Table of Contents 6
Preface 12
Basic Terminology 34
Chapter 1. Matchings in bipartite graphs 40
1.0. Introduction 40
1.1. The Theorems of Konig, P. Hall and Frobenius 43
1.2. A bipartite matching algorithm: the Hungarian Method 51
1.3. Deficiency, surplus and a glimpse of matroid theory 56
1.4. Some consequences of bipartite matching theorems 68
Chapter 2. Flow theory 80
2.0. Introduction 80
2.1. The Max-Flow Min-Cut Theorem 81
2.2. Flow algorithms 85
2.3. Flow-equivalent trees 100
2.4. Applications of flow theory to matching theory 107
2.5. Matchings, flows and measures 113
Chapter 3. Size and structure of maximum matchings 122
3.0. Introduction 122
3.1. Tutte’s theorem, Gallai’s lemma and Berge’s formula 123
3.2. The Gallai-Edmonds Structure Theorem 132
3.3. Toward a calculus of barriers 141
3.4. Sufficient conditions for matchings of a given size 149
Chapter 4. Bipartite graphs with perfect matchings 160
4.0. Introduction 160
4.1. Elementary graphs and their ear structure 161
4.2. Minimal elementary bipartite graphs 166
4.3. Decomposition into elementary bipartite graphs 176
Chapter 5. General graphs with perfect matchings 182
5.0. Introduction 182
5.1. Elementary graphs: elementary properties 184
5.2. The canonical partition P(G) 189
5.3. Saturated graphs and cathedrals 198
5.4. Ear structure of 1-extendable graphs 213
5.5. More about factor-critical and bicritical graphs 234
Chapter 6. Some graph-theoretical problems related to matchings 252
6.0. Introduction 252
6.1. 2-matchings and 2-covers 252
6.2. 2-bicritical and regularizable graphs 256
6.3. Matchings, 2-matchings and the Konig Property 259
6.4. Hamilton cycles and 2-matchings 267
6.5. The Chinese Postman Problem 270
6.6. Optimum paths, cycles, joins and cuts 282
Chapter 7. Matching and linear programming 294
7.0. Introduction 294
7.1. Linear programming and matching in bigraphs 305
7.2. Matchings and fractional matchings 312
7.3. The matching polytope 313
7.4. Chromatic index 324
7.5. Fractional matching polytopes and cover polyhedra 330
7.6. The dimension of the perfect matching polytope 331
Chapter 8. Determinants and matchings 346
8.0. Introduction 346
8.1. Permanents 348
8.2. The method of variables 354
8.3. The Pfaffian and the number of perfect matchings 357
8.4. Probabilistic enumeration of perfect matchings 369
8.5. Matching polynomials 372
8.6. More on the number of perfect matchings 384
8.7. Two applications to physical science 388
Chapter 9. Matching algorithms 396
9.0. Introduction 396
9.1. The Edmonds Matching Algorithm 397
9.2. Weighted matching 408
9.3. An algorithm based upon the Gallai-Edmonds Theorem 415
9.4. A linear programming algorithm for matching 418
Chapter 10. The f-factor problem 422
10.0. Introduction 422
10.1. Reduction principles 424
10.2. A structure theory for f -factors 427
10.3. Realization of degree sequences 443
Chapter 11. Matroid matching 448
11.0. Introduction 448
11.1. Formulations of the Matroid Matching Problem 448
11.2. The main theorem of polymatroid matching 465
11.3. Matching in special polymatroids 472
Chapter 12. Vertex packing and covering 482
12.0. Introduction 482
12.1. Critical graphs 484
12.2. Vertex packing polytopes 495
12.3. Hypergraph matching 505
12.4. Vertex packing in claw-free graphs 510
References 522
Index of Terms 566
Index of Symbols 578

Produkt-Details

• Erscheint lt. Verlag: 1.6.1986
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Finanz- / Wirtschaftsmathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• Themenwelt: Technik
• ISBN-10: 0-08-087232-8 / 0080872328
• ISBN-13: 978-0-08-087232-2 / 9780080872322