Benutzer:Hutchison de/Krausz-Partition

Beispiel

Sei $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 $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:

Der zugrundeliegende Urgraph.