Vollständiger Graph

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.