Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2024 | Buch

Perfect Matchings Kapitel lesen Erstes Kapitel lesen

Perfect Matchings

A Theory of Matching Covered Graphs

verfasst von: Cláudio L. Lucchesi, U.S.R. Murty

Verlag: Springer Nature Switzerland

Buchreihe : Algorithms and Computation in Mathematics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Beginning with its origins in the pioneering work of W.T. Tutte in 1947, this monograph systematically traces through some of the impressive developments in matching theory.

A graph is matchable if it has a perfect matching. A matching covered graph is a connected graph on at least two vertices in which each edge is covered by some perfect matching. The theory of matching covered graphs, though of relatively recent vintage, has an array of interesting results with elegant proofs, several surprising applications and challenging unsolved problems.

The aim of this book is to present the material in a well-organized manner with plenty of examples and illustrations so as to make it accessible to undergraduates, and also to unify the existing theory and point out new avenues to explore so as to make it attractive to graduate students.

Inhaltsverzeichnis

Frontmatter

Basic Theory

Frontmatter
Chapter 1. Perfect Matchings
Abstract
Perfect matchings in graphs have been of interest ever since Tait showed that the four colour conjecture was equivalent to the statement that every 3-connected cubic planar graph is 3-edge-colourable or, equivalently, that such a graph has three pairwise edge-disjoint perfect matchings (see Bondy and Murty [3]).
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 2. Matching Covered Graphs
Abstract
This book is primarily concerned with matching covered graphs which were briefly introduced at the end of Section 1.3. We begin our exploration of their rich theory with a study of notions and statements applicable to the more general class of matchable graphs.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 3. Canonical Partitions
Abstract
A barrier B in a matchable graph G is maximal if there is no other barrier of G that properly contains B . The barrier B = { u1, u2, u3} in the graph shown in Figure 2.1 is not maximal because there are barriers of the graph which properly contain B. It can be verified that { v1, u1, u2, u3, u4, u5} is a maximal barrier of that graph.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 4. Tight Cuts
Abstract
In Chapter 2 we introduced the operation of splicing which can be used to ‘combine’ two matching covered graphs to obtain another matching covered graph. Here we introduce the related notion of a separating cutwhich leads to away of ‘decomposing’ a matching covered graph into two matching covered graphs. Tight cuts are a special type of separating cuts. They play a pivotal role in many aspects of this theory, including the study of questions concerning the existence of an edge in a matching covered graph whose deletion results in another matching covered graph.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 5. Characterizations of Bricks and Braces
Abstract
Recall that a matching covered graph which is free of nontrivial tight cuts is a brace if it is bipartite, and is a brick if it is nonbipartite. In Chapter 4 we presented a proof of Lovász’s Uniqueness Theorem (4.17) for tight cut decompositions, which is one of the cornerstones of this theory. According to that theorem, every matching covered graph has a unique decomposition into bricks and braces (up to multiple edges). The proof of this fundamental result simply relied on the fact that bricks and braces are free of nontrivial tight cuts. But this fact by itself is inadequate to suggest efficient procedures for recognizing these basic objects. In this chapter, we address these issues by establishing characterizations of bricks and braces which lead to polynomial-time recognition algorithms.We deal with bricks in this section and braces in Section 5.4.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 6. The Perfect Matching Polytope
Abstract
A geometrical object of great interest in the theory of combinatorial optimization is the perfect matching polytope of a graph. It turns out that tight cut decompositions of a matching covered graph, which were described in Chapter 4, are very relevant to understanding the properties of its perfect matching polytope. The purpose of this chapter is to explore some of these connections.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 7. Solid Bricks
Abstract
The fact that bipartite graphs are free of odd cycles often makes the task of analyzing their properties easier, and makes it possible to state assertions concerning them more simply, and prove them more easily, than the corresponding assertions that are valid for all graphs. For example, the description of the perfect matching polytope of a bipartite graph is simpler, and its proof easier, than the one that applies to all graphs (see Exercise 6.1.1). Solidmatching covered graphs defined below havemany properties akin to those of bipartite matching covered graphs.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 8. Dependence Relation and Removable Classes
Abstract
Deletions and contractions of edges are two common inductive tools in graph theory. For example, the famous theorem of Kuratowski states that a graph is nonplanar if and only if it can be reduced to either K5 or to K3,3 by means of deletions and contractions of edges. There are several theorems of similar flavour in the theory of matching covered graphs. But here the deletion and contraction operations used are, of necessity, more restrictive as the deletion of an arbitrary edge from a matching covered graph need not result in a matching covered graph, and the contraction of a single edge does not even preserve the parity of the number of vertices.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 9. Dependence Classes in Bricks
Abstract
We continue our study of dependence classes in matching covered graphs. But here our attention is mainly devoted to bricks.
We have seen that, in general, dependence classes in matching covered graphs can be arbitrarily large (see Figure 8.10), although no removable class can havemore than two edges (Corollary 8.18).
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 10. Removable Classes in Solid Bricks
Abstract
Recall that a matching covered graph is solid if every separating cut in it is a tight cut and, in particular, that a brick is solid if it is free of nontrivial separating cuts.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 11. Ear Decompositions
Abstract
We now return to the topic of ear decompositions of matching covered graphs which was initiated in Chapter 3.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 12. Matching Minors
Abstract
In this final chapter of Part I, we bring together ideas of bicontractions of vertices of degree two and deletions of removable classes described in the preceding chapters to introduce two closely related types of minors that are specific to the theory of matching covered graphs. They play a role in this subject that is similar to that of the familiar type of minors in graph theory.We consider first the more general of these two types of minors which was introduced by Norine and Thomas (2007, [78]).
Cláudio L. Lucchesi, U. S. R. Murty

Brick and Brace Generation

Frontmatter
Chapter 13. A Conjecture of Lovász Concerning Bricks
Abstract
The properties of matching covered graphs with nontrivial tight cuts may often be deduced from those of their bricks and braces. But to deal with bricks and braces themselves, which are free of such cuts, one requires subtler inductive tools. In case of bricks, for example, optimal ear decompositions, that is, ear decompositions with as few double ear additions as possible, turn out to be useful for analyzing their properties.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 14. Robust Cuts in Bricks
Abstract
Let G be a nonsolid brick. By definition,G has nontrivial separating cuts. Consider any nontrivial separating cut D of G, and let M0 be a perfectmatching in such that | M0 ∩ D | > 1.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 15. b-Invariant Edges in Bricks
Abstract
The evolution of the approach to the Conjecture 13.2, as explained in Chapter 13, startedwith the observation that if a removable edge in a brick is not b-invariant, then that brick must have a nontrivial separating cut or, equivalently, that any removable edge in a solid brick is b-invariant. This led to the notion of robust cuts and to the consideration of the use of contractions with respect to a robust cut as an inductive tool. All this has been described in Chapter 13.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 16. The Matching Lattice and Optimal Ear Decompositions
Abstract
The objective of this chapter is to present a characterization of the matching lattice of a matching covered graph. Our approach to this characterization, envisaged by Lovász as explained in Section 13.1, makes essential use of Theorem 15.1. This approach also enables us to answer two related questions; one concerning bases of the matching lattices, and the other concerning optimal ear decompositions of matching covered graphs. In the last section we give a description of the ‘dual’ approach adopted by Lovász [58].
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 17. Thin Edges in Bricks and Braces
Abstract
The notion of a thin edge in a brick was introduced by CLM (2006, [15]). However, the definition of a thin edge e in a brick G given there is in terms of ‘sparsity’ of barriers of G − e; and it was that definition that led to the choice of the adjective ‘thin’.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 18. Strictly Thin Edges in Bricks and Braces
Abstract
A brick is solid if and only if its underlying simple graph is solid. A brick or brace has a specified simple matching covered graph J as a matching minor if and and only if its underlying simple graph has J as a matching minor. As these examples show, the properties of bricks and braces that are of interest to us are mostly those which are enjoyed by simple bricks and braces. This, as explained below, brings into question the efficacy of using thin edges as inductive tools for establishing properties of bricks and braces.
Cláudio L. Lucchesi, U. S. R. Murty

Pfaffian Orientations

Frontmatter
Chapter 19. Pfaffian Orientations
Abstract
This chapter is dedicated mainly to some interesting questions arising from Tutte’s original proof of his theorem, presented in Section 1.5, using Pfaffian identities. For the convenience of the readers, we recall briefly the relevant definitions.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 20. Similarity of Orientations and Characteristic Orientations
Abstract
In this section we introduce an equivalence relation on the set of all orientations of a graph. The study of equivalence classes with respect to this relation turns out to play an important role in developing algorithms for finding Pfaffian orientations of matching graphs which are known to be Pfaffian and in showing that the Pfaffian Recognition Problem (19.1) and the Pfaffian Orientation Problem (19.2) are both in co-NP and are polynomial-time equivalent.
Cláudio L. Lucchesi, U. S. R. Murty
Chapter 21. Excluded-Minor Characterizations of Pfaffian Graphs
Abstract
As noted in Chapter 19, Kasteleyn (1963, [44]) not only pioneered the theory of Pfaffian orientations, but also established the first definitive result in this theory by showing that all planar graphs are Pfaffian.
Cláudio L. Lucchesi, U. S. R. Murty
Backmatter
Metadaten
Titel
Perfect Matchings
verfasst von
Cláudio L. Lucchesi
U.S.R. Murty
Copyright-Jahr
2024
Electronic ISBN
978-3-031-47504-7
Print ISBN
978-3-031-47503-0
DOI
https://doi.org/10.1007/978-3-031-47504-7

Premium Partner

    Bildnachweise