Vollständiger Graph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Die vollständigen Graphen K_1 bis K_5.

Ein vollständiger Graph ist ein Begriff aus der Graphentheorie und bezeichnet einen einfachen Graph, in dem alle Knotenpaare durch 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[Bearbeiten]

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. Der vollständige Graph K_n enthält dabei (n-1)!/2 verschiedene Hamiltonkreise.

Verallgemeinerung[Bearbeiten]

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. Den vollständigen multipartiten Graphen mit p Partitionsmengen, welche n_1,...,n_p Knoten enthalten, bezeichnet man mit K_{n_1, \ldots, n_p}.

Versieht man einen vollständigen Graphen mit einer Orientierung, so erhält man einen Turniergraphen.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]