Satz von Petersen

Der Satz v​on Petersen i​st ein mathematischer Satz a​us der Graphentheorie. Er besagt, d​ass jeder kubische Graph o​hne Brücke e​ine perfekte Paarung enthält. Der Satz v​on Petersen g​ilt als e​ines der frühesten Resultate d​er Graphentheorie. Er i​st nach d​em dänischen Mathematiker Julius Petersen benannt.

Satz

Der Satz v​on Petersen besagt:[1]

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

Das heißt, w​enn in e​inem Graphen j​eder Knoten g​enau drei benachbarte Kanten h​at und j​ede Kante z​u einem Kreis erweitert werden kann, d​ann gibt e​s eine Auswahl d​er Kanten, d​ie jeden Knoten g​enau einmal berührt.

Beweis

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

Sei ${\displaystyle G_{i}}$ eine Zusammenhangskomponente mit einer ungeraden Anzahl von Knoten im durch ${\displaystyle V-U}$ induzierten Graph. Weiter seien mit ${\displaystyle V_{i}}$ die Knoten in ${\displaystyle G_{i}}$ und mit ${\displaystyle m_{i}}$ die Anzahl der Kanten im Schnitt von ${\displaystyle V_{i}}$ bezeichnet. Das Aufsummieren der Knoten in ${\displaystyle V_{i}}$ liefert

${\displaystyle \sum _{v\in V_{i}}\deg(v)+m_{i}=2|E_{i}|}$,

wobei ${\displaystyle E_{i}}$ die Kanten in ${\displaystyle G}$ mit wenigstens einen Knoten in ${\displaystyle V_{i}}$ bezeichnet. Da

${\displaystyle \sum _{v\in V_{i}}\deg(v)=3|V_{i}|}$

eine ungerade Zahl ist, und ${\displaystyle 2|E_{i}|}$ eine gerade Zahl, folgt, dass ${\displaystyle m_{i}}$ eine ungerade Zahl sein muss. Da ${\displaystyle G}$ keine Brücke besitzt, muss ${\displaystyle m_{i}\geq 3}$ gelten.

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

Geschichte

Der Satz w​urde zuerst v​on Julius Petersen formuliert u​nd bewiesen. Es g​ilt als e​ines der ersten Resultate a​uf dem Gebiet d​er Graphentheorie u​nd wurde 1891 i​m Aufsatz Die Theorie d​er regulären graphs veröffentlicht.[1] Nach heutigem Stand g​ilt der Originalbeweis v​on Petersen a​ls kompliziert. Eine Reihe v​on Vereinfachungen führte z​u den Beweisen v​on Orrin Frink (1926) u​nd Dénes König (1936).[2][3]

In aktuellen Lehrbüchern w​ird der Satz v​on Petersen a​ls eine Anwendung d​es Satzes v​on Tutte behandelt.

Anwendungen

• 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

Anzahl der perfekten Paarungen in kubischen Graphen ohne Brücke

Von László Lovász und Michael Plummer wurde vermutet, dass jeder kubische Graph mit ${\displaystyle n}$ Knoten und ohne Brücke eine exponentielle Anzahl (in ${\displaystyle 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 ${\displaystyle n}$ Knoten mindestens ${\displaystyle 2^{n/3656}}$ perfekte Paarungen besitzt.

Algorithmische Versionen

Von Therese Biedl u. a. wurden effiziente algorithmische Varianten des Satzes von Petersen untersucht.[11] Basierend auf Frinks Beweis entwickelten sie einen ${\displaystyle O(n\log ^{4}n)}$ Algorithmus zur Berechnung einer perfekten Paarung in kubischen Graphen ohne Brücken mit ${\displaystyle n}$ Knoten. Handelt es sich zudem um einen planaren Graphen gibt der gleiche Aufsatz einen ${\displaystyle 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 einem ${\displaystyle O(n\log ^{2}n)}$ Algorithmus. Bei Benutzung von randomisierten Datenstrukturen lässt such die Laufzeit sogar auf ${\displaystyle O(n\log n\,(\log \log n)^{3})}$ verbessern.[13]

Einzelnachweise

1. 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 ${\displaystyle 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). Band 5901, 2010, S. 321–333, doi:10.1007/978-3-642-11266-9_27.