Quelltext der Seite Vollständiger Graph

[[Datei:Complete graph example.png|mini|Die vollständigen Graphen <math>K_1</math> bis <math>K_5</math>.]]
Ein '''vollständiger Graph''' ist ein Begriff aus der [[Graphentheorie]] und bezeichnet einen [[Einfacher Graph|einfachen Graphen]], in dem jeder [[Knoten (Graphentheorie)|Knoten]] mit jedem anderen Knoten durch eine [[Kante (Graphentheorie)|Kante]] verbunden ist. Der vollständige Graph mit <math>n</math> Knoten ist (bis auf [[Isomorphie von Graphen|Isomorphie]]) eindeutig bestimmt und wird mit <math>K_n</math> bezeichnet.

Ist <math>V=\{v_1,\dotsc,v_n\}</math> die Knotenmenge des vollständigen Graphen <math>K_n</math>, so ist die Kantenmenge <math>E</math> genau die Menge von Kanten zwischen paarweise verschiedenen Knoten <math>E=\{\{v_i,v_j\}: 1\le i<j\le n\}</math>.

Ein vollständiger Graph ist gleichzeitig seine [[maximale Clique]].

== Eigenschaften ==
Die vollständigen Graphen <math>K_1</math> bis <math>K_4</math> sind [[Planarer Graph|planar]]. Alle anderen vollständigen Graphen sind nach dem [[Satz von Kuratowski]] nicht planar, da sie <math>K_5</math> als Teilgraph enthalten.

Die Anzahl der Kanten des vollständigen Graphen <math>K_n</math> entspricht der [[Dreieckszahl]]
:<math>\Delta_{n-1} = {n \choose 2}=\frac{n(n-1)}{2}</math>.

Der vollständige Graph <math>K_n</math> ist ein <math>(n-1)</math>-[[regulärer Graph]]: jeder Knoten hat <math>n-1</math> [[Nachbarschaft (Graphentheorie)|Nachbarn]]. Aufgrund dessen hat jede [[Färbung (Graphentheorie)|Knotenfärbung]] des Graphen <math>n</math> Farben. Des Weiteren folgt daraus, dass die vollständigen Graphen für ungerade <math>n</math> [[Eulerscher Graph|eulersch]] sind und für gerade <math>n</math> nicht.

Vollständige Graphen sind für <math>n>2</math> [[Hamiltonscher Graph|hamiltonsche Graphen]]. Der vollständige Graph <math>K_n</math> enthält dabei <math>\tfrac{1}{2}(n-1)!</math> verschiedene [[Hamiltonkreis]]e.

== Verallgemeinerung ==
Die Idee des vollständigen Graphen lässt sich auf [[K-partiter Graph|<math>k</math>-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 <math>p</math> Partitionsmengen, welche <math>n_1,\dotsc,n_p</math> Knoten enthalten, bezeichnet man mit <math>K_{n_1, \dotsc, n_p}</math>.

Versieht man einen vollständigen Graphen mit einer Orientierung, so erhält man einen [[Turniergraph]]en.

== Software ==
Mit Hilfe der freien [[Python (Programmiersprache)|Python]]-[[Programmbibliothek|Bibliothek]] [[NetworkX]] lassen sich vollständige Graphen erzeugen. Beispiel:

<syntaxhighlight lang="python">
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()
</syntaxhighlight>

== Literatur ==
* Lutz Volkmann: ''Fundamente der Graphentheorie.'' Springer, Wien 1996, ISBN 3-211-82774-9; neuere Version: [https://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf ''Graphen an allen Ecken und Kanten''] (PDF; 3,5&nbsp;MB)

== Weblinks ==
* {{MathWorld |id=CompleteGraph |title=Complete Graph}}

{{SORTIERUNG:Vollstandiger Graph}}
[[Kategorie:Hamiltonscher Graph]]
[[Kategorie:Regulärer Graph]]