K-partiter Graph

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

{\displaystyle K_{1},K_{2}} — 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

{\displaystyle T_{3}(7)} — 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.^[1]