Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 25. Mai 2019 

K-partiter Graph


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Ein k-partiter Graph ist in der Graphentheorie ein spezieller Typ von Graph der eine Verallgemeinerung der bipartiten Graphen darstellt.

Inhaltsverzeichnis

Definition

In einem k-partiten Graph bildet die Menge der Knoten eine d.h. sie besteht aus k disjunkten Teilmengen so dass es keine Kanten gibt jeweils zwei Knoten derselben Teilmenge verbinden.

Formal

Ein Graph <math>K_{n_1 .. n_k} := K)</math> heißt k-partitit falls <math>E = E_1 + .. E_k</math> eine k-Partition ist mit <math>|E_i|=n_i (i=1 k)</math> und <math>K \subseteq \{ab : a E_i b \in E_j i \neq j\}</math>.

Ein solcher Graph <math>K_{n_1 .. n_k}</math> vollständig k-partitit falls für die Menge der Kanten = \{ab : a \in E_i b E_j i \neq j\}</math> gilt.

Eigenschaften

Anzahl der Knoten und Kanten

Für einen (vollständigen) k-partiten Graphen gilt die Anzahl der Knoten E : <math>|E| \sum_{i=1}^k{n_i}</math>. Speziel für vollständig k-partite Graphen gilt für die Anzahl der Kanten : <math>|K| = \sum_{i<j}{n_in_j}</math>.

Färbbarkeit

Ein k-partiter Graph ist in jedem k- färbbar .

Stabile Mengen

Die Teilmengen <math>E_1 + .. + der Partition E sind stabile Mengen .

Siehe auch

Bipartiter Graph Typen von Graphen in der Graphentheorie



Bücher zum Thema K-partiter Graph

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/K-partiter_Graph.html">K-partiter Graph </a>