Krausz-Partition

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.

Der Graph K_1,3

Beineke, Krausz, v​an Rooij u​nd Wilf konnten i​n den 1960ern zeigen, d​ass 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 o​der mit d​em Algorithmus v​on Roussopoulos findet m​an 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 z​um folgenden Urgraphen:

Der zugrundeliegende Urgraph.

Literatur

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