Krausz-Partition
Eine Krausz-Partition, benannt nach dem ungarischen Mathematiker József Krausz († 1944), ist in der Graphentheorie eine Menge <math>K</math> von Teilgraphen eines Graphen <math>G = (V,E)</math> mit den folgenden Eigenschaften:
- Jedes Element von <math>K</math> ist ein vollständiger Graph.
- Jede Kante <math>e \in E</math> ist in genau einem Element von <math>K</math> enthalten.
- Jeder Knoten <math>v \in V</math> ist in höchstens zwei Elementen von <math>K</math> enthalten.
Beineke, Krausz, van Rooij und Wilf konnten in den 1960ern zeigen, dass folgende Aussagen äquivalent sind:
- <math>L(G)</math> ist Kantengraph zu einem Graphen <math>G</math>.
- <math>L(G)</math> besitzt eine Krausz-Partition.
Das heißt, es existiert genau dann ein Urbild <math>G</math> eines Kantengraphen <math>L(G)</math>, wenn <math>L(G)</math> Krausz-partitionierbar ist.
Der Graph <math>K_{1,3}</math> ist zum Beispiel nicht Krausz-partitionierbar und ist daher auch kein Kantengraph <math>L(G)</math> zu einem beliebigen Graphen <math>G</math>.
Beispiel
Sei <math>L(G)</math> 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 <math>G = (V, E)</math> konstruieren:
- Die Knotenmenge <math>V</math> ergibt sich aus <math>S \cup U</math>, für die gilt:
- <math>S</math> ist die Menge der vollständigen Teilgraphen der eben ermittelten Krausz-Partition, also <math>S = \left\{S_1, S_2, \dots \right\}</math>. In diesem Beispiel ist demnach <math>S = \left\{S_1, S_2, S_3\right\}</math>.
- <math>U</math> ist die Menge der Knoten aus <math>L(G)</math>, die sich in genau einem der vollständigen Teilgraphen aus <math>S</math> befinden. In diesem Beispiel ist <math>U = \left\{1,3,6\right\}</math>. Die Knoten <math>2, 4</math> und <math>5</math> liegen jeweils in genau zwei der vollständigen Teilgraphen aus <math>S</math> und sind damit keine Elemente von <math>U</math>.
- Für die Kantenmenge von <math>E</math> gilt <math>E = E_1 \cup E_2</math> mit:
- <math>E_1 = \left\{S_i S_j \mid E(S_i) \cap E(S_j) \neq \emptyset, i \neq j\right\}</math>, d. h. zwei verschiedene Elemente aus <math>S</math> sind verbunden, wenn sie einen gemeinsamen Knoten in <math>L(G)</math> haben. In unserem Beispiel sind alle <math>S_i</math> miteinander verbunden.
- <math>E_2 = \left\{x S_i \mid x \in U \text{ und } x \in E(S_i)\right\}</math>, d. h. ein Knoten aus <math>U</math> ist mit einem <math>S_i</math> verbunden, wenn dieser Knoten Teil des vollständigen Teilgraphen <math>S_i</math> ist. In unserem Beispiel führt das zu den Kanten <math>1S_2, 3S_1</math> und <math>6S_1</math>.
Diese Konstruktion führt zum folgenden Urgraphen:
Literatur
- {{#invoke:Vorlage:Literatur|f}}
- {{#invoke:Vorlage:Literatur|f}}
- {{#invoke:Vorlage:Literatur|f}}