k-partiter Graph

Ein 3-partiter Graph. Die hellblauen ovale sind die 3 Partitionsklassen $K_{1},K_{2}$ und $K_{3}$

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},\ldots ,V_{k}$, sodass keine adjazenten Knoten in der gleichen Menge $V_{i}$ liegen, das heißt

$\forall i\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{i}\rightarrow \{v,w\}\not \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,\ldots ,k\}:v\in V_{i}\wedge w\in V_{j}\rightarrow \{v,w\}\in E$.

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

Beispiel Turán-Graph

Der Turán-Graph $T_{3}(7)$

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 $\lfloor \cdot \rfloor$ die Floor-Funktion, so ist

$T_{m}(n)=K_{\lfloor {\frac {n}{m}}\rfloor ,\lfloor {\frac {n+1}{m}}\rfloor ,\ldots ,\lfloor {\frac {n+m-1}{m}}\rfloor }$.

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},\ldots ,n_{k}}$ mit $n_{1}\leq \ldots \leq n_{k}$ besitzt immer ein Matching der Größe $\min\{\sum _{i=1}^{k-1}n_{i},\lfloor {\frac {1}{2}}\sum _{i=1}^{k}n_{i}\rfloor \}$, 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)