“Tutte–Berge formula”的意思、由来-开放百科全书

词条

Tutte–Berge formula

释义

Statement
Explanation
Relation to Tutte's theorem
See also
References

In the mathematical discipline of graph theory the Tutte–Berge formula is a characterization of the size of a maximum matching in a graph. It is a generalization of Tutte's theorem on perfect matchings, and is named after W. T. Tutte (who proved Tutte's theorem) and Claude Berge (who proved its generalization).

Statement

The theorem states that the size of a maximum matching of a graph equals

where counts how many of the connected components of the graph have an odd number of vertices.

Explanation

Intuitively, for any subset U of the vertices, the only way to completely cover an odd component of G − U by a matching is for one of the matched edges covering the component to be incident to U. If, instead, some odd component had no matched edge connecting it to U, then the part of the matching that covered the component would cover its vertices in pairs, but since the component has an odd number of vertices it would necessarily include at least one leftover and unmatched vertex. Therefore, if some choice of U has few vertices but its removal creates a large number of odd components, then there will be many unmatched vertices, implying that the matching itself will be small. This reasoning can be made precise by stating that the size of a maximum matching is at most equal to the value given by the Tutte–Berge formula.

The characterization of Tutte and Berge proves that this is the only obstacle to creating a large matching: the size of the optimal matching will be determined by the subset U with the biggest difference between its numbers of odd components outside U and vertices inside U. That is, there always exists a subset U such that deleting U creates the correct number of odd components needed to make the formula true. One way to find such a set U is to choose any maximum matching M, and to let X be the set of vertices that are either unmatched in M, or that can be reached from an unmatched vertex by an alternating path that ends with a matched edge. Then, let U be the set of vertices that are matched by M to vertices in X. No two vertices in X can be adjacent, for if they were then their alternating paths could be concatenated to give a path by which the matching could be increased, contradicting the maximality of M. Every neighbor of a vertex x in X must belong to U, for otherwise we could extend an alternating path to x by one more pair of edges, through the neighbor, causing the neighbor to become part of U. Therefore, in G − U, every vertex of X forms a single-vertex component, which is odd. There can be no other odd components, because all other vertices remain matched after deleting U. So with this construction the size of U and the number of odd components created by deleting U are what they need to be to make the formula be true.

Relation to Tutte's theorem

Tutte's theorem characterizes the graphs with perfect matchings as being the ones for which deleting any subset U of vertices creates at most |U| odd components. (A subset U that creates at least |U| odd components can always be found in the empty set.) In this case, by the Tutte–Berge formula, the size of the matching is |V|/2; that is, the maximum matching is a perfect matching. Thus, Tutte's theorem can be derived as a corollary of the Tutte–Berge formula, and the formula can be seen as a generalization of Tutte's theorem.

References

{{cite journal|first=C.|last=Berge|authorlink=Claude Berge|title=Sur le couplage maximum d'un graphe|journal=Comptes rendus hebdomadaires des séances de l'Académie des sciences|volume=247|year=1958|pages=258–259}}
{{cite book|first=C.|last=Berge|authorlink=Claude Berge|title=The Theory of Graphs|publisher=Methuen|year=1962|at=Theorem 5, p. 181}} Reprinted by Dover Publications, 2001.
{{cite book|last1=Bondy|first1=J. A.|author1-link=John Adrian Bondy|last2=Murty|first2=U. S. R.|author2-link=U. S. R. Murty| title=Graph theory: an advanced course | series=Graduate Texts in Mathematics | publisher=Springer-Verlag | year=2007 | isbn=1-84628-969-6 | page=428 }}
{{cite book|last1=Bondy|first1=J. A.|author1-link=John Adrian Bondy|last2=Murty|first2=U. S. R.|author2-link=U. S. R. Murty|title=Graph Theory with Applications|location=New York|publisher=North Holland|year=1976|isbn=0-444-19451-7|url=http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html|at=Exercise 5.3.4, p. 80|deadurl=yes|archiveurl=https://web.archive.org/web/20100413104345/http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html|archivedate=2010-04-13|df=}}
{{cite book | last=Brualdi | first=Richard A. | title=Combinatorial matrix classes | series=Encyclopedia of Mathematics and Its Applications | volume=108 | location=Cambridge | publisher=Cambridge University Press | year=2006 | isbn=0-521-86565-4 | zbl=1106.05001 | page=360 }}
{{Cite book

| last=Lovász | first=László | authorlink=László Lovász
| last2=Plummer | first2=M. D. | author2-link = Michael D. Plummer
| title=Matching theory | year=1986 | publisher=North-Holland | location=Amsterdam | isbn=0-444-87916-1
| pages=90–91}}

{{cite book | last=Schrijver | first = Alexander | authorlink=Alexander Schrijver | title=Combinatorial optimization: polyhedra and efficiency | publisher=Springer-Verlag | year=2003 | isbn=3-540-44389-4 | page=413 }}
{{cite journal|first=W. T.|last=Tutte|authorlink=W. T. Tutte|title=The factorization of linear graphs|journal=Journal of the London Mathematical Society |series=Series 1|volume=22|issue=2|doi=10.1112/jlms/s1-22.2.107|year=1947|pages=107–111}}

2 : Matching|Theorems in discrete mathematics

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Statement

Explanation

Relation to Tutte's theorem

See also

References