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 jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist. Der vollständige Graph mit n Knoten ist (bis auf Isomorphie) eindeutig bestimmt und wird mit K_n bezeichnet.

Ist V=\{v_1,\dotsc,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 \tfrac{1}{2}(n-1)! 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,\dotsc,n_p Knoten enthalten, bezeichnet man mit K_{n_1, \dotsc, n_p}.

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

Literatur[Bearbeiten]

Weblinks[Bearbeiten]