Satz von Petersen

Satz aus der Graphentheorie

Der Satz von Petersen ist ein mathematischer Satz aus der Graphentheorie. Er besagt, dass jeder kubische Graph ohne Brücke eine perfekte Paarung enthält. Der Satz von Petersen gilt als eines der frühesten Resultate der Graphentheorie. Er ist nach dem dänischen Mathematiker Julius Petersen benannt.

Der Satz von Petersen besagt:[1]

Jeder kubische Graph ohne Brücke enthält eine perfekte Paarung.

Das heißt, wenn in einem Graphen jeder Knoten genau drei benachbarte Kanten hat und jede Kante zu einem Kreis erweitert werden kann, dann gibt es eine Auswahl der Kanten, die jeden Knoten genau einmal berührt.

Man zeigt, dass für jeden kubischen Graphen   ohne Brücken folgendes gilt: Für jede Knotenmenge   ist die Anzahl der Zusammenhangskomponenten im durch   induzierten Graph mit einer ungeraden Anzahl an Knoten, höchstens so groß wie die Anzahl von Knoten in   selbst. Dann folgt nach dem Satz von Tutte, dass   eine perfekte Paarung besitzt.

Sei   eine Zusammenhangskomponente mit einer ungeraden Anzahl von Knoten im durch   induzierten Graph. Weiter seien mit   die Knoten in   und mit   die Anzahl der Kanten im Schnitt von   bezeichnet. Das Aufsummieren der Knoten in   liefert

 ,

wobei   die Kanten in   mit wenigstens einen Knoten in   bezeichnet. Da

 

eine ungerade Zahl ist, und   eine gerade Zahl, folgt, dass   eine ungerade Zahl sein muss. Da   keine Brücke besitzt, muss   gelten.

Sei nun   die Anzahl aller Schnittkanten von   in  . Die Anzahl der Zusammenhangskomponenten mit einer ungeraden Anzahl an Knoten ist nach dem Argument im vorigen Absatz höchstens 3  . Im schlimmsten Fall steuert jede Kante mit einem Knoten in   eine Zusammenhangskomponente mit ungerader Knotenanzahl bei. Daraus folgt, dass  , und die Voraussetzung des Satzes von Tutte sind damit erfüllt.

Geschichte

Bearbeiten

Der Satz wurde zuerst von Julius Petersen formuliert und bewiesen. Es gilt als eines der ersten Resultate auf dem Gebiet der Graphentheorie und wurde 1891 im Aufsatz Die Theorie der regulären graphs veröffentlicht.[1] Nach heutigem Stand gilt der Originalbeweis von Petersen als kompliziert. Eine Reihe von Vereinfachungen führte zu den Beweisen von Orrin Frink (1926) und Dénes König (1936).[2][3]

In aktuellen Lehrbüchern wird der Satz von Petersen als eine Anwendung des Satzes von Tutte behandelt.

Anwendungen

Bearbeiten
  • In einem kubischen Graphen mit perfekter Paarung bilden die Kanten außerhalb der Paarung einen 2-Faktor. Bei einer gewissen Orientierung des 2-Faktors, kann man die Kanten der Paarung um je zwei Kanten zu einem Weg der Länge drei erweitern. Dies zeigt, dass jeder kubische Graph ohne Brücken mit kantendisjunkten Wegen der Länge drei überdeckt werden kann.[4]
  • Mit Hilfe des Satzes von Petersen kann man auch zeigen, dass jeder maximale planare Graph mit kantendisjunkten Wegen der Länge drei überdeckt werden kann. Da der duale Graph eines solchen Graphen kubisch ist und keine Brücken enthält, kann man dort eine perfekte Paarung finden, welches im ursprünglichen Graphen zu zwei Dreiecken gehört, welche sich eine Kante teilen. Diese gemeinsamen Kanten kann man zu Wegen der Länge drei in der Art erweitern, dass keine Kante in mehreren dieser Erweiterungen auftaucht.[5]
  • Ein Dreiecksgitter kann man mit Hilfe des Satzes von Petersen so modifizieren, dass ein Hamiltonpfad im dualen Graphen des Gitters existiert.[6]

Erweiterungen

Bearbeiten

Anzahl der perfekten Paarungen in kubischen Graphen ohne Brücke

Bearbeiten

Von László Lovász und Michael Plummer wurde vermutet, dass jeder kubische Graph mit   Knoten und ohne Brücke eine exponentielle Anzahl (in  ) von perfekten Paarungen besitzt.[7] Diese Vermutung wurde 1979 für bipartite Graphen von Marc Voorhoeve bewiesen,[8] und 2012 für planare Graphen von Maria Chudnovsky und Paul Seymour.[9] Der allgemeine Fall wurde schließlich 2011 von Lois Esperet u. a. bewiesen.[10] Hier wurde gezeigt, dass jeder kubische Graph ohne Brücken und mit   Knoten mindestens   perfekte Paarungen besitzt.

Algorithmische Versionen

Bearbeiten

Von Therese Biedl u. a. wurden effiziente algorithmische Varianten des Satzes von Petersen untersucht.[11] Basierend auf Frinks Beweis entwickelten sie einen   Algorithmus zur Berechnung einer perfekten Paarung in kubischen Graphen ohne Brücken mit   Knoten. Handelt es sich zudem um einen planaren Graphen gibt der gleiche Aufsatz einen   Algorithmus an. Durch nachfolgende Verbesserungen der im Algorithmus verwendeten Datenstrukturen, lässt sich die Laufzeit weiter verbessern.[12] Weitere Verbesserungen führten zu einem   Algorithmus. Bei Benutzung von randomisierten Datenstrukturen lässt such die Laufzeit sogar auf   verbessern.[13]

Einzelnachweise

Bearbeiten
  1. a b Julius Petersen: Die Theorie der regulären graphs. In: Acta Mathematica. Vol. 15, 1891, S. 193–220, doi:10.1007/BF02392606.
  2. Orrin Frink: A proof of Petersen’s theorem. In: Annals of Mathematics. Band 27, Nr. 4, 1926, S. 491–493, doi:10.2307/1967699.
  3. Dénes König: Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkomplexe. Akademische Verlagsgesellschaft, Leipzig 1936.
  4. André Bouchet, Jean-Luc Fouquet: Trois types de décompositions d’un graphe en chaînes. In: P. Camion, D. Bresson, C. Berge, F. Sterboul (Hrsg.): Combinatorial Mathematics: Proceedings of the International Colloquium on Graph Theory and Combinatorics (Marseille-Luminy, 1981) (= North-Holland Mathematics Studies). Band 75. North-Holland, 1983, S. 131–141, doi:10.1016/S0304-0208(08)73380-2.
  5. Roland Häggkvist, Robert Johansson: A note on edge-decompositions of planar graphs. In: Discrete Mathematics. Band 283, Nr. 1–3, 2004, S. 263–266, doi:10.1016/j.disc.2003.11.017.
  6. Gopi Meenakshisundaram, David Eppstein: Single-strip triangulation of manifolds with arbitrary topology. In: Computer Graphics Forum. Band 23, 2004, S. 371–379, doi:10.1111/j.1467-8659.2004.00768.x, arxiv:cs.CG/0405036.
  7. László Lovász, Michael D. Plummer: Matching Theory (= Annals of Discrete Mathematics. Band 29). North-Holland, 1986, ISBN 0-444-87916-1.
  8. Marc Voorhoeve: A lower bound for the permanents of certain (0,1)-matrices. In: Indagationes Mathematicae. Band 82, Nr. 1, 1979, S. 83–86, doi:10.1016/1385-7258(79)90012-X.
  9. Maria Chudnovsky, Paul Seymour: Perfect matchings in planar cubic graphs. In: Combinatorica. Band 32, Nr. 4, 2012, S. 403–424, doi:10.1007/s00493-012-2660-9.
  10. Louis Esperet, František Kardoš, Andrew D. King, Daniel Král’, Serguei Norine: Exponentially many perfect matchings in cubic graphs. In: Advances in Mathematics. Band 227, Nr. 4, 2011, S. 1646–1664, doi:10.1016/j.aim.2011.03.015.
  11. Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, Anna Lubiw: Efficient algorithms for Petersen’s matching theorem. In: Journal of Algorithms. Band 38, Nr. 1, 2001, S. 110–134, doi:10.1006/jagm.2000.1132.
  12. Mikkel Thorup: Near-optimal fully-dynamic graph connectivity. In: Proc. 32nd ACM Symposium on Theory of Computing. 2000, S. 343–350, doi:10.1145/335305.335345.
  13. Krzysztof Diks, Piotr Stanczyk: Perfect matching for biconnected cubic graphs in   time. In: Jan van Leeuwen, Anca Muscholl, David Peleg, Jaroslav Pokorný, Bernhard Rumpe (Hrsg.): Proceedings SOFSEM 2010: 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23-29, 2010 (= Lecture Notes in Computer Science). Band 5901, 2010, S. 321–333, doi:10.1007/978-3-642-11266-9_27.