Vollständig k-partiter Graph

k-partiter Graph

Beispiele:

Bipartite Graphen

Ein k-partiter Graph ist in der Graphentheorie ein einfacher Graph, dessen Knotenmenge in k disjunkte Teilmengen zerfällt, so dass die Knoten jeder dieser Teilmengen untereinander nicht benachbart sind. Insofern stellt dies eine Verallgemeinerung der bipartiten Graphen dar, für die k=2 verlangt wird.

Jeder k-partite Graph ist auch immer ein k+x-partiter Graph, wobei x eine natürliche Zahl und k+x kleiner als die Knotenzahl ist.

Definitionen

Ein Graph G=(V,E) heißt k-partit, falls $V_1,\ldots,V_k$ eine Partition von V ist und

$\forall i\in \{1,\ldots,k\}: v \in V_i \wedge w \in V_i \rightarrow \{v,w\} \not\in E$.

Man beachte, dass die Partition nicht eindeutig ist. Es ist durchaus möglich, dass es mehrere Partitionen gibt, die diese Eigenschaft erfüllen.

Man nennt den Graphen dann vollständig k-partit, falls außerdem jeder Knoten mit allen Knoten aller anderen Partitionen verbunden ist, wenn also gilt:

$\forall i\neq j\in \{1,\ldots,k\}: v \in V_i \wedge w \in V_j \rightarrow \{v,w\} \in E$.

Mit $K_{n_1,\ldots,n_k}$ notiert man einen vollständig k-partiten Graphen, mit | V_i | = n_i.