K-partiter Graph - de.LinkFang.org

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.

Inhaltsverzeichnis

Definitionen


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

{\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:

{\displaystyle \forall i\neq j\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{j}\rightarrow \{v,w\}\in E}.

Mit {\displaystyle K_{n_{1},\ldots ,n_{k}}} notiert man einen vollständig k-partiten Graphen, mit {\displaystyle |V_{i}|=n_{i}}.

Beispiel Turán-Graph


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

{\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

{\displaystyle T_{3}(7)=K_{2,2,3}}.

Eigenschaften


Literatur


Weblinks


Einzelnachweise


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



Kategorien: Graphenklasse


Quelle: Wikipedia - https://de.wikipedia.org/wiki/K-partiter Graph (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.


Stand der Informationen: 19.10.2019 10:22:58 CEST - Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.