Krausz-Partition
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/K13.png/220px-K13.png)
Eine Krausz-Partition, benannt nach dem ungarischen Mathematiker József Krausz († 1944), ist in der Graphentheorie eine Menge von Teilgraphen eines Graphen mit den folgenden Eigenschaften:
- Jedes Element von ist ein vollständiger Graph.
- Jede Kante ist in genau einem Element von enthalten.
- Jeder Knoten ist in höchstens zwei Elementen von enthalten.
Beineke, Krausz, van Rooij und Wilf konnten in den 1960ern zeigen, dass folgende Aussagen äquivalent sind:
- ist Kantengraph zu einem Graphen .
- besitzt eine Krausz-Partition.
Das heißt, es existiert genau dann ein Urbild eines Kantengraphen , wenn Krausz-partitionierbar ist.
Der Graph ist zum Beispiel nicht Krausz-partitionierbar und ist daher auch kein Kantengraph zu einem beliebigen Graphen .
Beispiel
[Bearbeiten | Quelltext bearbeiten]Sei der folgende Graph. Dieser soll wie oben beschrieben in vollständige Teilgraphen mit den gewünschten Eigenschaften partitioniert werden.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/88/Krausz-Partition_1.png/300px-Krausz-Partition_1.png)
Durch Ausprobieren oder mit dem Algorithmus von Roussopoulos findet man die folgende Partitionierung:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/71/Krausz-Partition_2.png/350px-Krausz-Partition_2.png)
Mit der Krausz-Partition lässt sich wie folgt der zugrundeliegende Urgraph konstruieren:
- Die Knotenmenge ergibt sich aus , für die gilt:
- ist die Menge der vollständigen Teilgraphen der eben ermittelten Krausz-Partition, also . In diesem Beispiel ist demnach .
- ist die Menge der Knoten aus , die sich in genau einem der vollständigen Teilgraphen aus befinden. In diesem Beispiel ist . Die Knoten und liegen jeweils in genau zwei der vollständigen Teilgraphen aus und sind damit keine Elemente von .
- Für die Kantenmenge von gilt mit:
- , d. h. zwei verschiedene Elemente aus sind verbunden, wenn sie einen gemeinsamen Knoten in haben. In unserem Beispiel sind alle miteinander verbunden.
- , d. h. ein Knoten aus ist mit einem verbunden, wenn dieser Knoten Teil des vollständigen Teilgraphen ist. In unserem Beispiel führt das zu den Kanten und .
Diese Konstruktion führt zum folgenden Urgraphen:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Krausz-Partition_3.png/350px-Krausz-Partition_3.png)
Literatur
[Bearbeiten | Quelltext bearbeiten]- József Krausz: Démonstration nouvelle d’une théorème de Whitney sur les réseaux. In: Matematikai és Fizikai Lapok. Band 50, 1943, S. 75–85.
- Lutz Volkmann: Fundamente der Graphentheorie. Springer, Wien / New York 1996, ISBN 3-211-82774-9, S. 182–183.
- Nicholas D. Roussopoulos: A max {m,n} algorithm for determining the graph H from its line graph G. S. 108–112, doi:10.1016/0020-0190(73)90029-X ([1]).