Krausz-Partition
# Krausz-Partition

Eine Krausz-Partition, benannt nach dem ungarischen Mathematiker József Krausz († 1944), ist in der Graphentheorie eine Menge $K$ von Teilgraphen eines Graphen $G=(V,E)$ mit den folgenden Eigenschaften:
* Jedes Element von $K$ ist ein vollständiger Graph.
* Jede Kante $e\in E$ ist in genau einem Element von $K$ enthalten.
* Jeder Knoten $v\in V$ ist in höchstens zwei Elementen von $K$ enthalten.
Beineke, Krausz, van Rooij und Wilf konnten in den 1960ern zeigen, dass folgende Aussagen äquivalent sind:
* $L(G)$ ist Kantengraph zu einem Graphen $G$.
* $L(G)$ besitzt eine Krausz-Partition.
Das heißt, es existiert genau dann ein Urbild $G$ eines Kantengraphen $L(G)$, wenn $L(G)$ Krausz-partitionierbar ist.
Der Graph $K_{1,3}$ ist zum Beispiel nicht Krausz-partitionierbar und ist daher auch kein Kantengraph $L(G)$ zu einem beliebigen Graphen $G$.

## Beispiel

Sei $L(G)$ der folgende Graph. Dieser soll wie oben beschrieben in vollständige Teilgraphen mit den gewünschten Eigenschaften partitioniert werden.
Durch Ausprobieren oder mit dem Algorithmus von Roussopoulos findet man die folgende Partitionierung:
Mit der Krausz-Partition lässt sich wie folgt der zugrundeliegende Urgraph $G=(V,E)$ konstruieren:
* Die Knotenmenge $V$ ergibt sich aus $S\cup U$, für die gilt:
** $S$ ist die Menge der vollständigen Teilgraphen der eben ermittelten Krausz-Partition, also $S=\left\{S_{1},S_{2},\dots \right\}$. In diesem Beispiel ist demnach $S=\left\{S_{1},S_{2},S_{3}\right\}$.
** $U$ ist die Menge der Knoten aus $L(G)$, die sich in genau einem der vollständigen Teilgraphen aus $S$ befinden. In diesem Beispiel ist $U=\left\{1,3,6\right\}$. Die Knoten $2,4$ und $5$ liegen jeweils in genau zwei der vollständigen Teilgraphen aus $S$ und sind damit keine Elemente von $U$.
* Für die Kantenmenge von $E$ gilt $E=E_{1}\cup E_{2}$ mit:
** $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 $S$ sind verbunden, wenn sie einen gemeinsamen Knoten in $L(G)$ haben. In unserem Beispiel sind alle $S_{i}$ miteinander verbunden.
** $E_{2}=\left\{xS_{i}\mid x\in U{\text{ und }}x\in E(S_{i})\right\}$, d. h. ein Knoten aus $U$ ist mit einem $S_{i}$ verbunden, wenn dieser Knoten Teil des vollständigen Teilgraphen $S_{i}$ ist. In unserem Beispiel führt das zu den Kanten $1S_{2},3S_{1}$ und $6S_{1}$.
Diese Konstruktion führt zum folgenden Urgraphen: