Vollständiger Graph

Die vollständigen Graphen ${\displaystyle K_{1}}$ bis ${\displaystyle K_{5}}$.

Ein vollständiger Graph ist ein Begriff aus der Graphentheorie und bezeichnet einen einfachen Graphen, in dem jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist. Der vollständige Graph mit ${\displaystyle n}$ Knoten ist (bis auf Isomorphie) eindeutig bestimmt und wird mit ${\displaystyle K_{n}}$ bezeichnet.

Ist ${\displaystyle V=\{v_{1},\dotsc ,v_{n}\}}$ die Knotenmenge des vollständigen Graphen ${\displaystyle K_{n}}$, so ist die Kantenmenge ${\displaystyle E}$ genau die Menge von Kanten zwischen paarweise verschiedenen Knoten ${\displaystyle E=\{\{v_{i},v_{j}\}:1\leq i<j\leq n\}}$.

Ein vollständiger Graph ist gleichzeitig seine maximale Clique.

Eigenschaften

Die vollständigen Graphen ${\displaystyle K_{1}}$ bis ${\displaystyle K_{4}}$ sind planar. Alle anderen vollständigen Graphen sind nach dem Satz von Kuratowski nicht planar, da sie ${\displaystyle K_{5}}$ als Teilgraph enthalten.

Die Anzahl der Kanten des vollständigen Graphen ${\displaystyle K_{n}}$ entspricht der Dreieckszahl

${\displaystyle \Delta _{n-1}={n \choose 2}={\frac {n(n-1)}{2}}}$.

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

Vollständige Graphen sind für ${\displaystyle n>2}$ hamiltonsche Graphen. Der vollständige Graph ${\displaystyle K_{n}}$ enthält dabei ${\displaystyle {\tfrac {1}{2}}(n-1)!}$ verschiedene Hamiltonkreise.

Verallgemeinerung

Die Idee des vollständigen Graphen lässt sich auf ${\displaystyle 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 ${\displaystyle p}$ Partitionsmengen, welche ${\displaystyle n_{1},\dotsc ,n_{p}}$ Knoten enthalten, bezeichnet man mit ${\displaystyle K_{n_{1},\dotsc ,n_{p}}}$.

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

Software

Mit Hilfe der freien Python-Bibliothek NetworkX lassen sich vollständige Graphen erzeugen. Beispiel:

import networkx as nx
import matplotlib.pyplot as plt

G = nx.complete_graph(15)

nx.draw_circular(G, with_labels=True, font_weight='bold')
plt.show()

Literatur

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

Weblinks

• Eric W. Weisstein: Complete Graph. In: MathWorld (englisch).