Satz von Petersen

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

Der Satz von Petersen besagt:

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

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ß 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 $3m\leq |U|$, und die Voraussetzung des Satzes von Tutte sind damit erfüllt.

Geschichte

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. 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).

In aktuellen Lehrbüchern wird der Satz von Petersen als eine Anwendung des Satzes von 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.
• 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.
• Ein Dreiecksgitter kann man mit Hilfe des Satzes von Petersen so modifizieren, dass ein Hamiltonpfad im dualen Graphen des Gitters existiert.

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 $n$ Knoten und ohne Brücke eine exponentielle Anzahl (in $n$) von perfekten Paarungen besitzt. Diese Vermutung wurde 1979 für bipartite Graphen von Marc Voorhoeve bewiesen, und 2012 für planare Graphen von Maria Chudnovsky und Paul Seymour. Der allgemeine Fall wurde schließlich 2011 von Lois Esperet u. a. bewiesen. Hier wurde gezeigt, dass jeder kubische Graph ohne Brücken und mit $n$ Knoten mindestens $2^{n/3656}$ perfekte Paarungen besitzt.

Algorithmische Versionen

Von Therese Biedl u. a. wurden effiziente algorithmische Varianten des Satzes von Petersen untersucht. 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. Weitere Verbesserungen führten zu einem $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.