K-partiter Graph

Ein k-partiter Graph ist in der Graphentheorie ein spezieller Typ von Graph, der eine Verallgemeinerung der bipartiten Graphen darstellt.

Definition

In einem k-partiter 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 $K_{n_{1},..,n_{k}}:=G(E,K)$ heißt k-partitit, falls $E=E_{1}+..+E_{k}$ eine k-Partition ist mit $|E_{i}|=n_{i}(i=1,..,k)$ und $K\subseteq \{ab:a\in E_{i},b\in E_{j},i\neq j\}$.

Ein solcher Graph $K_{n_{1},..,n_{k}}$ heißt vollständig k-partitit, falls für die Menge der Kanten $K=\{ab:a\in E_{i},b\in E_{j},i\neq j\}$ gilt.

Eigenschaften

Anzahl der Knoten und Kanten

Für einen (vollständigen) k-partiten Graphen gilt für die Anzahl der Knoten E : $|E|=\sum _{i=1}^{k}{n_{i}}$. Speziel für vollständig k-partite Graphen gilt für die Anzahl der Kanten K : $|K|=\sum _{i<j}{n_{i}n_{j}}$.

Färbbarkeit

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

Stabile Mengen

Die Teilmengen $E_{1}+..+E_{k}$ der Partition E sind stabile Mengen.

Siehe auch

Bipartiter Graph, Typen von Graphen in der Graphentheorie