k-partiter Graph

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Ein 3-partiter Graph. Die hellblauen ovale sind die 3 Partitionsklassen und

Ein -partiter Graph ist in der Graphentheorie ein einfacher Graph, dessen Knotenmenge in k disjunkte Teilmengen zerfällt, sodass die Knoten jeder dieser Teilmengen untereinander nicht benachbart sind. Für heißen diese Graphen bipartite Graphen.

Eine k-Partition eines Graphen ist eine Zerlegung der Knotenmenge in disjunkte Teilmengen , sodass keine adjazenten Knoten in der gleichen Menge liegen, das heißt

.

Man beachte, dass eine solche k-Partition nicht eindeutig ist. Es ist durchaus möglich, dass es mehrere k-Partitionen gibt, die diese Eigenschaft erfüllen. Ein Graph heißt nun k-partit, falls er eine k-Partition besitzt. Man nennt den Graphen vollständig k-partit, falls außerdem jeder Knoten mit allen Knoten aller anderen k-Partitionen verbunden ist, wenn also gilt:

.

Mit notiert man einen vollständig k-partiten Graphen, mit .

Beispiel Turán-Graph

[Bearbeiten | Quelltext bearbeiten]
Der Turán-Graph

Die Turán-Graphen () sind vollständige -partite Graphen. Das nebenstehende Beispiel ist 3-partit. Bezeichnet die Floor-Funktion, so ist

.

Für das nebenstehende Beispiel gilt damit

.
  • Jeder k-partite Graph ist k-knotenfärbbar. Dabei wird jeder Partitionsklasse eine Farbe zugewiesen. Die Frage, ob ein Graph k-partit ist, ist also äquivalent zu der Frage, ob der Graph k-knotenfärbbar ist. Die chromatische Zahl eines Graphen ist somit das kleinste , sodass eine k-Partition besitzt.
  • Jeder k-partite Graph ist auch immer ein k+x-partiter Graph, wobei x eine natürliche Zahl und k+x kleiner als die Knotenzahl ist.
  • Ein vollständig k-partiter Graph mit besitzt immer ein Matching der Größe , welches effizient berechnet werden kann.[1]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. D. Sitton: Maximum Matchings in complete multipartite Graphs. In: Electronic Journal of Undergraduate Mathematics. Volume 00, 1996, S. 6–16.