K-partiter Graph - LinkFang.de





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

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

Die Turán-Graphen [math]T_m(n)[/math] ([math]3\le m \lt 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 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.

Weblinks

Literatur


Kategorien: Graphenklasse

Quelle: Wikipedia - http://de.wikipedia.org/wiki/K-partiter Graph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.