|
Ein k-partiter Graph ist in der Graphentheorie ein
spezieller Typ von Graph, der eine
Verallgemeinerung der bipartiten Graphen darstellt.
| Inhaltsverzeichnis |
|
1 Definition
2 Eigenschaften
2.1 Anzahl der Knoten und Kanten
2.2 Färbbarkeit
2.3 Stabile Mengen
3 Siehe auch
|
Definition
In einem k-partiten Graph bildet die Menge der Knoten eine k-Partition,d.h. sie besteht aus k disjunkten Teilmengen, so dass es keine Kanten gibt, die jeweils zwei Knoten derselben Teilmenge verbinden.
Formal
Ein Graph  heißt
k-partitit, falls E = E1 + .. +
Ek eine k-Partition ist mit | Ei | =
ni(i = 1,..,k) und  .
Ein solcher Graph  heißt
vollständig k-partitit, falls für die Menge der Kanten  gilt.
Eigenschaften
Anzahl der Knoten und Kanten
Für einen (vollständigen) k-partiten Graphen gilt für die Anzahl der Knoten E :  . Speziell für vollständig k-partite
Graphen gilt für die Anzahl der Kanten K :
.
Färbbarkeit
Ein k-partiter Graph ist in jedem Fall k-färbbar.
Stabile Mengen
Die Teilmengen E1 + .. + Ek der Partition E sind
stabile Mengen.
Siehe auch
Bipartiter Graph, Typen von Graphen in der
Graphentheorie
|
Startseite 
Bookmark setzen
Sitemap
Impressum
Lexikon Eintrag Drucken
Dokument als PDF downloaden