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,\dots ,V_k$, sodass keine adjazenten Knoten in der gleichen Menge $V_i$ liegen, das heißt

$\mathrm{\forall }i\in \{1,\dots ,k\}:v\in V_i\wedge 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:

$\mathrm{\forall }i\ne j\in \{1,\dots ,k\}:v\in V_i\wedge 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

Der Turán-Graph $T_3(7)$

Die Turán-Graphen $T_m(n)$ ($3\le 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 ,\dots ,\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,\dots ,n_k}$ mit $n_1\le \dots \le 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

• Vorlage:Literatur

Weblinks

• Vorlage:MathWorld
• Vorlage:MathWorld
• Vorlage:PlanetMath