K-partiter Graph

Ein k {\displaystyle 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 {\displaystyle k=2} heißen diese Graphen bipartite Graphen.

Eine k-Partition eines Graphen G = ( V , E ) {\displaystyle G=(V,E)} ist eine Zerlegung der Knotenmenge V {\displaystyle V} in k {\displaystyle k} disjunkte Teilmengen V 1 , … , V k {\displaystyle V_{1},\ldots ,V_{k}} , sodass keine adjazenten Knoten in der gleichen Menge V i {\displaystyle V_{i}} liegen, das heißt

∀ i ∈ { 1 , … , k } : v ∈ V i ∧ w ∈ V i → { v , w } ∉ E {\displaystyle \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:

∀ i ≠ j ∈ { 1 , … , k } : v ∈ V i ∧ w ∈ V j → { v , w } ∈ E {\displaystyle \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 , … , n k {\displaystyle K_{n_{1},\ldots ,n_{k}}} notiert man einen vollständig k-partiten Graphen, mit | V i | = n i {\displaystyle |V_{i}|=n_{i}} .

Die Turán-Graphen T m ( n ) {\displaystyle T_{m}(n)} ( 3 ≤ m < n {\displaystyle 3\leq m<n} ) sind vollständige m {\displaystyle m} -partite Graphen. Das nebenstehende Beispiel T 3 ( 7 ) {\displaystyle T_{3}(7)} ist 3-partit. Bezeichnet ⌊ ⋅ ⌋ {\displaystyle \lfloor \cdot \rfloor } die Floor-Funktion, so ist

T m ( n ) = K ⌊ n m ⌋ , ⌊ n + 1 m ⌋ , … , ⌊ n + m − 1 m ⌋ {\displaystyle 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 {\displaystyle T_{3}(7)=K_{2,2,3}} .

• 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 {\displaystyle G} ist somit das kleinste k {\displaystyle k} , sodass G {\displaystyle 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 , … , n k {\displaystyle K_{n_{1},\ldots ,n_{k}}} mit n 1 ≤ … ≤ n k {\displaystyle n_{1}\leq \ldots \leq n_{k}} besitzt immer ein Matching der Größe min { ∑ i = 1 k − 1 n i , ⌊ 1 2 ∑ i = 1 k n i ⌋ } {\displaystyle \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]

• Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (diestel-graph-theory.com). 

• 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)

1. ↑ D. Sitton: Maximum Matchings in complete multipartite Graphs. In: Electronic Journal of Undergraduate Mathematics. Volume 00, 1996, S. 6–16.