Krausz-Partition

Der Graph K_1,3

Eine Krausz-Partition, benannt nach dem ungarischen Mathematiker József Krausz († 1944), ist in der Graphentheorie eine Menge ${\displaystyle K}$ von Teilgraphen eines Graphen ${\displaystyle G=(V,E)}$ mit den folgenden Eigenschaften:

• Jedes Element von ${\displaystyle K}$ ist ein vollständiger Graph.
• Jede Kante ${\displaystyle e\in E}$ ist in genau einem Element von ${\displaystyle K}$ enthalten.
• Jeder Knoten ${\displaystyle v\in V}$ ist in höchstens zwei Elementen von ${\displaystyle K}$ enthalten.

Beineke, Krausz, van Rooij und Wilf konnten in den 1960ern zeigen, dass folgende Aussagen äquivalent sind:

• ${\displaystyle L(G)}$ ist Kantengraph zu einem Graphen ${\displaystyle G}$.
• ${\displaystyle L(G)}$ besitzt eine Krausz-Partition.

Das heißt, es existiert genau dann ein Urbild ${\displaystyle G}$ eines Kantengraphen ${\displaystyle L(G)}$, wenn ${\displaystyle L(G)}$ Krausz-partitionierbar ist.

Der Graph ${\displaystyle K_{1,3}}$ ist zum Beispiel nicht Krausz-partitionierbar und ist daher auch kein Kantengraph ${\displaystyle L(G)}$ zu einem beliebigen Graphen ${\displaystyle G}$.

Beispiel

Sei ${\displaystyle L(G)}$ der folgende Graph. Dieser soll wie oben beschrieben in vollständige Teilgraphen mit den gewünschten Eigenschaften partitioniert werden.

Ein gegebener Kantengraph

Durch Ausprobieren oder mit dem Algorithmus von Roussopoulos findet man die folgende Partitionierung:

Die vollständigen Teilgraphen der Krausz-Partition.

Mit der Krausz-Partition lässt sich wie folgt der zugrundeliegende Urgraph ${\displaystyle G=(V,E)}$ konstruieren:

• Die Knotenmenge ${\displaystyle V}$ ergibt sich aus ${\displaystyle S\cup U}$, für die gilt:
  • ${\displaystyle S}$ ist die Menge der vollständigen Teilgraphen der eben ermittelten Krausz-Partition, also ${\displaystyle S=\left\{S_{1},S_{2},\dots \right\}}$. In diesem Beispiel ist demnach ${\displaystyle S=\left\{S_{1},S_{2},S_{3}\right\}}$.
  • ${\displaystyle U}$ ist die Menge der Knoten aus ${\displaystyle L(G)}$, die sich in genau einem der vollständigen Teilgraphen aus ${\displaystyle S}$ befinden. In diesem Beispiel ist ${\displaystyle U=\left\{1,3,6\right\}}$. Die Knoten ${\displaystyle 2,4}$ und ${\displaystyle 5}$ liegen jeweils in genau zwei der vollständigen Teilgraphen aus ${\displaystyle S}$ und sind damit keine Elemente von ${\displaystyle U}$.
• Für die Kantenmenge von ${\displaystyle E}$ gilt ${\displaystyle E=E_{1}\cup E_{2}}$ mit:
  • ${\displaystyle E_{1}=\left\{S_{i}S_{j}\mid E(S_{i})\cap E(S_{j})\neq \emptyset ,i\neq j\right\}}$, d. h. zwei verschiedene Elemente aus ${\displaystyle S}$ sind verbunden, wenn sie einen gemeinsamen Knoten in ${\displaystyle L(G)}$ haben. In unserem Beispiel sind alle ${\displaystyle S_{i}}$ miteinander verbunden.
  • ${\displaystyle E_{2}=\left\{xS_{i}\mid x\in U{\text{ und }}x\in E(S_{i})\right\}}$, d. h. ein Knoten aus ${\displaystyle U}$ ist mit einem ${\displaystyle S_{i}}$ verbunden, wenn dieser Knoten Teil des vollständigen Teilgraphen ${\displaystyle S_{i}}$ ist. In unserem Beispiel führt das zu den Kanten ${\displaystyle 1S_{2},3S_{1}}$ und ${\displaystyle 6S_{1}}$.

Diese Konstruktion führt zum folgenden Urgraphen:

Der zugrundeliegende Urgraph.

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie. Springer, Wien / New York 1996, ISBN 3-211-82774-9, S. 182–183. 
• 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. 
• 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]).