Mathe Genie Lexikon K-partiter Graph Erklärung Bedeutung und Formel

K-partiter Graph

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

Inhaltsverzeichnis

1 Definition

1.1 Formal

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 $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}$ . Speziell für vollständig k-partite Graphen gilt für die Anzahl der Kanten K :

\| K \| =	?	n_in_j
	i < 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

Dieser Artikel ( K-partiter Graph ) stammt aus Wikipedia, der freien Enzyklopädie
und steht unter der GNU Free Documentation Licence.