k-partiter Graph
Ein <math>k</math>-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 <math>k=2</math> heißen diese Graphen bipartite Graphen.
Definitionen
[Bearbeiten]Eine k-Partition eines Graphen <math>G=(V,E)</math> ist eine Zerlegung der Knotenmenge <math>V</math> in <math>k</math> disjunkte Teilmengen <math>V_1,\ldots,V_k</math>, sodass keine adjazenten Knoten in der gleichen Menge <math>V_i</math> liegen, das heißt
- <math>\forall i\in \{1,\ldots,k\}: v \in V_i \wedge w \in V_i \rightarrow \{v,w\} \not\in E</math>.
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:
- <math>\forall i\neq j\in \{1,\ldots,k\}: v \in V_i \wedge w \in V_j \rightarrow \{v,w\} \in E</math>.
Mit <math>K_{n_1,\ldots,n_k}</math> notiert man einen vollständig k-partiten Graphen, mit <math>|V_i|=n_i</math>.
Beispiel Turán-Graph
[Bearbeiten]Die Turán-Graphen <math>T_m(n)</math> (<math>3\le m < n</math>) sind vollständige <math>m</math>-partite Graphen. Das nebenstehende Beispiel <math>T_3(7)</math> ist 3-partit. Bezeichnet <math>\lfloor\cdot \rfloor</math> die Floor-Funktion, so ist
- <math>T_m(n) = K_{\lfloor \frac{n}{m}\rfloor,\lfloor \frac{n+1}{m}\rfloor,\ldots,\lfloor \frac{n+m-1}{m}\rfloor}</math>.
Für das nebenstehende Beispiel gilt damit
- <math>T_3(7) = K_{2,2,3}</math>.
Eigenschaften
[Bearbeiten]- 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 <math>G</math> ist somit das kleinste <math>k</math>, sodass <math>G</math> 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 <math>K_{n_1,\ldots,n_k}</math> mit <math>n_1 \leq \ldots \leq n_k</math> besitzt immer ein Matching der Größe <math>\min\{\sum_{i=1}^{k-1}n_{i},\lfloor\frac{1}{2}\sum_{i=1}^{k}n_{i}\rfloor\}</math>, welches effizient berechnet werden kann.<ref>D. Sitton: Maximum Matchings in complete multipartite Graphs. In: Electronic Journal of Undergraduate Mathematics. Volume 00, 1996, S. 6–16.</ref>
Literatur
[Bearbeiten]Weblinks
[Bearbeiten]Einzelnachweise
[Bearbeiten]<references />
