k-partiter Graph

Graphentheorie, Teilgebiet der Mathematik

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.

Ein 3-partiter Graph. Die hellblauen ovale sind die 3 Partitionsklassen und

DefinitionenBearbeiten

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-GraphBearbeiten

 
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

 .

EigenschaftenBearbeiten

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

LiteraturBearbeiten

WeblinksBearbeiten

EinzelnachweiseBearbeiten

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