imported>Aka: /* Literatur */ https

2023-12-11T18:27:30Z

Literatur: https

Neue Seite

{{SEITENTITEL:''k''-partiter Graph}}
[[Datei:3partitegraphn.png|mini|Ein 3-partiter Graph. Die hellblauen ovale sind die 3 Partitionsklassen <math> K_1, K_2 </math> und <math> K_3 </math>]]
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 [[Bipartiter Graph|bipartite Graphen]].

== Definitionen ==
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 [[Nachbarschaft (Graphentheorie)|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 ==
[[Datei:TuranGraph T 3 7.PNG|mini|200px|Der Turán-Graph <math>T_3(7)</math>]]

Die [[Satz von Turán|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 ==
* Jeder k-partite Graph ist [[Färbung (Graphentheorie)|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 (Graphentheorie)|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 [[P (Komplexitätsklasse)|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 ==
* {{Literatur |Autor=[[Reinhard Diestel]] |Titel=Graphentheorie |Auflage=4. |Verlag=Springer |Ort=Berlin |Datum=2010 |ISBN=978-3-642-14911-5 |Online=https://diestel-graph-theory.com/}}

== Weblinks ==
* {{MathWorld
| id = k-PartiteGraph
| title = k-Partite Graph
| author =Eric W. Weisstein
}}
* {{MathWorld
| id = Completek-PartiteGraph
| title = Complete k-Partite Graph
| author = Eric W. Weisstein
}}
* {{PlanetMath
| id = KPartiteGraph
| title = k-partite graph
| author = Boris Bukh, Kevin Ferguson
}}

== Einzelnachweise ==
<references />
[[Kategorie:Graphenklasse]]

K-partiter Graph - Versionsgeschichte

imported>Aka: /* Literatur */ https