Vollständiger Graph

Vollständiger Graph ist ein Begriff aus der Graphentheorie und bezeichnet einen speziellen, besonders wichtigen, Typ von Graph (Graphentheorie).

Inhaltsverzeichnis
1 Definition

1.1 Formal

2 Beispiele
3 Siehe auch

Definition

Ein vollständiger Graph Kn ist ein ungerichteter Graph ohne Mehrfachkanten mit n Knoten und genau {n \choose 2}=\frac{n(n-1)}{2} Kanten. In einem vollständigen Graphen ist jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden.

Formal

K_n := G(E,K) \mbox{ mit } |E|=n ,\ |K|={n \choose 2} ,\ K={E \choose 2}

Beispiele

Die folgende Abbildung zeigt die vollständigen Graphen K1,..,K5. bild:Complete_graph_example.png

Siehe auch

Typen von Graphen in der Graphentheorie, Vollständig k-partiter Graph, Färbung von Graphen, Satz von Kuratowski


Kategorie:Graphentheorie

See also: Vollständiger Graph, Färbung von Graphen, Graph (Graphentheorie), Graph ohne Mehrfachkanten, Graphentheorie, Kante (Graphentheorie), Knoten (Graphentheorie), Satz von Kuratowski, Typen von Graphen in der Graphentheorie, Ungerichteter Graph