Satz von Petersen

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Satz[Bearbeiten]

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.

Beweis[Bearbeiten]

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

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

\sum_{v\in V_i} \deg(v)+ m_i = 2|E_i|,

wobei E_i die Kanten in G mit wenigstens einen Knoten in V_i bezeichnet. Da

\sum_{v\in V_i} \deg(v)= 3 |V_i|

eine ungerade Zahl ist, und 2|E_i| eine gerade Zahl, folgt, dass m_i eine ungerade Zahl sein muss. Da G keine Brücke besitzt, muss m_i \geq 3 gelten.

Sei nun m die Anzahl aller Schnittkanten von U in G. Die Anzahl der Zusammenhangskomponenten mit einer ungeraden Anzahl an Knoten ist nach dem Argument im vorigen Absatz höchstens 3 m. Im schlimmsten Fall steuert jede Kante mit einem Knoten in U eine Zusammenhangskomponente mit ungerader Knotenanzahl bei. Daraus folgt, dass 3 m \le |U|, 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 n Knoten und ohne Brücke eine exponentielle Anzahl (in n) 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 n Knoten mindesten 2^{n/3656} 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 O(n \log^4 n) Algorithmus zur Berechnung einer perfekten Paarung in kubischen Graphen ohne Brücken mit n Knoten. Handelt es sich zudem um einen planaren Graphen gibt der gleiche Aufsatz einen O(n) Algorithmus an. Durch nachfolgende Verbesserungen der im Algorithmus verwendeten Datenstrukturen, lässt sich die Laufzeit weiter verbessern.[12] Weitere Verbesserungen führten zu einen O(n \log^2 n) Algorithmus. Bei Benutzung von randomisierten Datenstrukturen lässt such die Laufzeit sogar auf O(n \log n \, (\log \log n)^3) verbessern.[13]

Einzelnachweise[Bearbeiten]

  1. a b Julius Petersen: Die Theorie der regulären graphs. In: Acta Mathematica. 15, 1891, S. 193–220. doi:10.1007/BF02392606.
  2.  Orrin Frink: A proof of Petersen’s theorem. In: Annals of Mathematics. 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. 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. 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. 23, 2004, S. 371–379, arXiv:cs.CG/0405036, doi:10.1111/j.1467-8659.2004.00768.x.
  7.  László Lovász, Michael D. Plummer: Matching Theory (= Annals of Discrete Mathematics. 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. 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. 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. 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. 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 \scriptstyle O(n \log^2 n) 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. 5901). 2010, S. 321–333, doi:10.1007/978-3-642-11266-9_27.