Vollständiger Graph

Die vollständigen Graphen $K_1$ bis $K_5$.

Ein vollständiger Graph oder Simplex ist ein Begriff aus der Graphentheorie und bezeichnet einen einfachen Graph, in dem alle Knoten miteinander jeweils über eine Kante verbunden sind. Der vollständige Graph mit $n$ Knoten ist (bis auf Isomorphie) eindeutig bestimmt und wird mit $K_n$ bezeichnet.

Ist $V=\{v_1,...,v_n\}$ die Knotenmenge des $K_n$, so ist die Kantenmenge E genau die Menge von Kanten zwischen paarweise verschiedenen Knoten $E=\{\{v_i,v_j\}: 1\le i<j\le n\}$.

Ein vollständiger Graph ist gleichzeitig seine maximale Clique.

Eigenschaften

Die vollständigen Graphen $K_1$ bis $K_4$ sind planar. Alle anderen vollständigen Graphen sind nach dem Satz von Kuratowski nicht planar, da sie $K_5$ als Teilgraph enthalten.

Die Anzahl der Kanten des vollständigen Graphen $K_n$ entspricht der Dreieckszahl

$\Delta_{n-1} = {n \choose 2}=\frac{n(n-1)}{2}.$

Der vollständige Graph $K_n$ ist ein $(n-1)$-regulärer Graph: jeder Knoten hat $n-1$ Nachbarn. Aufgrund dessen hat jede Knotenfärbung des Graphen $n$ Farben. Des Weiteren folgt daraus, dass die vollständigen Graphen für ungerade $n$ eulersch sind und für gerade $n$ nicht.

Vollständige Graphen sind für $n>2$ hamiltonsche Graphen.

Verallgemeinerung

Die Idee des vollständigen Graphen lässt sich auf $k$-partite Graphen übertragen. Diese sind vollständig, falls jeder Knoten einer Partition mit allen Knoten aller anderen Partitionen verbunden ist.

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie. Springer (Wien) 1996, ISBN 3-211-82774-9 (neuere, elektronische Online-Version "Graphen an allen Ecken und Kanten")

Weblinks

• Eric W. Weisstein: vollständiger Graph. In: MathWorld. (englisch)