Set of mountains

In graph theory , one of the branches of mathematics , Berge's theorem is one of several theorems that go back to the French mathematician Claude Berge (1926–2002). Berge published the theorem in 1957 and thus gave a characterization of the largest possible matchings in finite graphs . In this publication, Berge also gave an algorithm for determining such a matching.

Formulation of the sentence

The sentence can be stated as follows:

A matching in a finite graph is of maximum power (and thus consists of exactly edges ) if and only if there is no -extending path .

{\ displaystyle M}

{\ displaystyle G}

{\ displaystyle \ nu (G)}

{\ displaystyle G}

{\ displaystyle M}

Explanations

In a finite graph , a matching is of maximum power if and only if there is no other matching with . The power of such a largest possible matching is called the matching number of and denotes it with . ${\ displaystyle G}$ ${\ displaystyle M \ subseteq E (G)}$ ${\ displaystyle G}$ ${\ displaystyle M ^ {*}}$ ${\ displaystyle | M ^ {*} |> | M |}$ ${\ displaystyle G}$ ${\ displaystyle \ nu (G)}$

Is a path in given, is as -alternierend designated if in to alternately occurring edges to and include. ${\ displaystyle G}$ ${\ displaystyle W}$ ${\ displaystyle M}$ ${\ displaystyle W}$ ${\ displaystyle M}$ ${\ displaystyle E (G) \ setminus M}$

Incising by a -alternierenden path associated with none of the end node in occurring edges, it is as -erweiternd (or as -zunehmend hereinafter). ${\ displaystyle M}$ ${\ displaystyle W}$ ${\ displaystyle M}$ ${\ displaystyle W}$ ${\ displaystyle M}$ ${\ displaystyle M}$

Remarks

In the English-language graph theory literature one speaks of an augmenting path. This is why Berge's theorem is also known here as the augmenting path theorem .

The sentence already appears in the pioneering work The Theory of Regular Graphs by the Danish mathematician Julius Petersen from 1891.

Often (as in the Bronstein, for example ) a matching of maximum power is also briefly called a maximum matching , although this designation does not correspond to the otherwise usual concept of maximality, which comes from order theory .

Web links

Wikiversity: A Proof of the Theorem in a Discrete Mathematics Course - Course Materials

literature

Claude Berge: Two theorems in graph theory . In: Proceedings of the National Academy of Sciences . tape 43 , 1957, pp. 842-844 ( MR0094811 ).
Claude Berge: Graphs and Hypergraphs . Translated [from the French] by Edward Minieka (= North-Holland Mathematical Library . Volume 6 ). North-Holland Publishing Company , Amsterdam, London 1973 ( MR0357172 ).
IN Bronstein , KA Semendjajew , G. Musiol , H. Mühlig (Hrsg.): Taschenbuch der Mathematik . 10th, revised edition. Europa-Lehrmittel, Haan-Gruiten 2016, ISBN 978-3-8085-5790-7 .
John Clark , Derek Allan Holton : Graph Theory . Basics and Applications. Spectrum Academic Publishing House , Heidelberg, Berlin, Oxford 1994, ISBN 3-86025-331-X .
Jonathan L. Gross , Jay Yellen (Eds.): Handbook of Graph Theory (= Discrete Mathematics and its Applications ). CRC Press, Boca Raton et al. a. 2004, ISBN 1-58488-090-2 .
Dieter Jungnickel : Graphs, Networks and Algorithms . With 209 Figures and 9 Tables (= Algorithms and Computation in Mathematics . Volume 5 ). 3. Edition. Springer Verlag, Berlin / Heidelberg / New York 2008, ISBN 978-3-540-72779-8 ( MR2363884 ).
Julius Petersen: The theory of the regular graph . In: Acta Mathematica . tape 15 , 1891, p. 193-220 ( PDF ).
Lutz Volkmann : Foundations of the graph theory . Springer Verlag , Vienna / New York 1996, ISBN 3-211-82774-9 ( MR1392955 ).

Individual evidence

↑ Claude Berge: Graphs and Hypergraphs. 1973, p. 124.
↑ John Clark, Derek Allan Holton: Graph Theory. 1994, p. 137.
^ Lutz Volkmann: Foundations of the graph theory. 1996, p. 117.
^ ^A ^b I. N. Bronstein, KA Semendjajev and others: Pocket book of mathematics. 2016, p. 420.
^ Dieter Jungnickel: Graphs, Networks and Algorithms. 2008, p. 390 ff.
↑ ^a ^b Jonathan L. Gross, Jay Yellen (Ed.): Handbook of Graph Theory. 2004, p. 1105.

[CB-01-1] Claude Berge: Graphs and Hypergraphs. 1973, p. 124.

[JC-DAH-01-2] John Clark, Derek Allan Holton: Graph Theory. 1994, p. 137.

[LV-01-3] Lutz Volkmann: Foundations of the graph theory. 1996, p. 117.

[BRON-SEM-01-4] A ^b I. N. Bronstein, KA Semendjajev and others: Pocket book of mathematics. 2016, p. 420.

[DJ-01-5] Dieter Jungnickel: Graphs, Networks and Algorithms. 2008, p. 390 ff.

[HBG-6] Jonathan L. Gross, Jay Yellen (Ed.): Handbook of Graph Theory. 2004, p. 1105.