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.

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.

Definitionen

Ein Graph G=(V,E) heißt k-partit, falls $V_1,\ldots,V_k$ eine Partition von V ist und

$\forall i\in \{1,\ldots,k\}: v \in V_i \wedge w \in V_i \rightarrow \{v,w\} \not\in E$.

Man beachte, dass die Partition nicht eindeutig ist. Es ist durchaus möglich, dass es mehrere Partitionen gibt, die diese Eigenschaft erfüllen.

Man nennt den Graphen dann vollständig k-partit, falls außerdem jeder Knoten mit allen Knoten aller anderen 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₃(7)

Die Turán-Graphen T_m(n) ($3\le m < n$) sind vollständige m-partite Graphen. Das nebenstehende Beispiel T₃(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₃(7) = K_2,2,3.