K-partiter Graph

Ein $k$ -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 $k = 2$ heißen diese Graphen bipartite Graphen.

Definitionen

Eine k-Partition eines Graphen $G = (V, E)$ ist eine Zerlegung der Knotenmenge $V$ in $k$ disjunkte Teilmengen $V_{1}, \dots, V_{k}$ , sodass keine adjazenten Knoten in der gleichen Menge $V_{i}$ liegen, das heißt

\forall i \in {1, \dots, k} : v \in V_{i} \land w \in V_{i} \to {v, w} \in̸ E

.

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:

\forall i \neq j \in {1, \dots, k} : v \in V_{i} \land w \in V_{j} \to {v, w} \in E

.

Mit $K_{n_{1}, \dots, n_{k}}$ notiert man einen vollständig k-partiten Graphen, mit $| V_{i} | = n_{i}$ .

Beispiel Turán-Graph

Die Turán-Graphen $T_{m} (n)$ ( $3 \leq m < n$ ) sind vollständige $m$ -partite Graphen. Das nebenstehende Beispiel $T_{3} (7)$ ist 3-partit. Bezeichnet $⌊ \cdot ⌋$ die Floor-Funktion, so ist

T_{m} (n) = K_{⌊ \frac{n}{m} ⌋, ⌊ \frac{n + 1}{m} ⌋, \dots, ⌊ \frac{n + m - 1}{m} ⌋}

.

Für das nebenstehende Beispiel gilt damit

T_{3} (7) = K_{2, 2, 3}

.

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 $G$ ist somit das kleinste $k$ , sodass $G$ 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 $K_{n_{1}, \dots, n_{k}}$ mit $n_{1} \leq \dots \leq n_{k}$ besitzt immer ein Matching der Größe $min {\sum_{i = 1}^{k - 1} n_{i}, ⌊ \frac{1}{2} \sum_{i = 1}^{k} n_{i} ⌋}$ , welches effizient berechnet werden kann.

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.

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