imported>Aka: /* Literatur */ https

2021-07-07T10:17:11Z

Literatur: https

Neue Seite

[[Bild:K13.png|mini|Der Graph ''K''<sub>1,3</sub>]]

Eine '''Krausz-Partition''', benannt nach dem ungarischen Mathematiker [[József Krausz]] († 1944), ist in der [[Graphentheorie]] eine [[Menge (Mathematik)|Menge]] <math>K</math> von [[Teilgraph]]en eines [[Graph (Graphentheorie)|Graphen]] <math>G = (V,E)</math> mit den folgenden Eigenschaften:

* Jedes Element von <math>K</math> ist ein [[vollständiger Graph]].
* Jede [[Kante (Graphentheorie)|Kante]] <math>e \in E</math> ist in genau einem Element von <math>K</math> enthalten.
* Jeder [[Knoten (Graphentheorie)|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 [[1960]]ern 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 (Mathematik)|Urbild]] <math>G</math> eines [[Kantengraph]]en <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.

[[Datei:Krausz-Partition 1.png|300px|links|mini|Ein gegebener Kantengraph]]
{{Absatz}}

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

[[Datei:Krausz-Partition 2.png|350px|links|mini|Die vollständigen Teilgraphen der Krausz-Partition.]]
{{Absatz}}

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:

[[Datei:Krausz-Partition 3.png|350px|links|mini|Der zugrundeliegende Urgraph.]]
{{Absatz}}

== Literatur ==
* {{Literatur|Autor=József Krausz|Titel=Démonstration nouvelle d’une théorème de Whitney sur les réseaux|Sammelwerk=Matematikai és Fizikai Lapok|Band=50|Seiten=75–85|Jahr=1943}}
* {{Literatur|Autor=Lutz Volkmann|Titel=Fundamente der Graphentheorie|Verlag=Springer|Ort=Wien / New York|Jahr=1996|ISBN=3-211-82774-9|Seiten=182–183}}
* {{Literatur|Autor=Nicholas D. Roussopoulos|Titel=A max {m,n} algorithm for determining the graph H from its line graph G|Seiten=108-112|DOI=10.1016/0020-0190(73)90029-X|Online=[https://linkinghub.elsevier.com/retrieve/pii/002001907390029X]}}

[[Kategorie:Graphentheorie]]

Krausz-Partition - Versionsgeschichte

imported>Aka: /* Literatur */ https