Krausz-Partition

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Der Graph K1,3

Eine Krausz-Partition, benannt nach dem ungarischen Mathematiker József Krausz († 1944), ist in der Graphentheorie eine Menge von Teilgraphen eines Graphen mit den folgenden Eigenschaften:

  • Jedes Element von ist ein vollständiger Graph.
  • Jede Kante ist in genau einem Element von enthalten.
  • Jeder Knoten ist in genau zwei Elementen von enthalten.

Beineke, Krausz, van Rooij und Wilf konnten in den 1960ern zeigen, dass folgende Aussagen äquivalent sind:

  • ist Kantengraph zu einem Graphen .
  • besitzt eine Krausz-Partition.

Das heißt, es existiert genau dann ein Urbild eines Kantengraphen , wenn Krausz-partitionierbar ist.

Der Graph ist zum Beispiel nicht Krausz-partitionierbar und ist daher auch kein Kantengraph zu einem beliebigen Graphen .

Literatur[Bearbeiten | Quelltext bearbeiten]

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