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.
Definitionen
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
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
- .
Eigenschaften
- 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]
Literatur
- Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (diestel-graph-theory.com).
Weblinks
- Eric W. Weisstein: k-Partite Graph. In: MathWorld (englisch).
- Eric W. Weisstein: Complete k-Partite Graph. In: MathWorld (englisch).
- Boris Bukh, Kevin Ferguson: k-partite graph. In: PlanetMath. (englisch)
Einzelnachweise
- ↑ D. Sitton: Maximum Matchings in complete multipartite Graphs. In: Electronic Journal of Undergraduate Mathematics. Volume 00, 1996, S. 6–16.