Kantenzahl des vollständigen Graphen

Kantenzahl des vollständigen Graphen

Oberstufe
∣E(Kn)∣=n(n−1)2=(n2)|E(K_n)| = \frac{n(n-1)}{2} = \binom{n}{2}

Voraussetzung: n∈Nn \in \mathbb{N}

KnK_n
vollständiger Graph mit n Knoten, jeder Knoten ist mit jedem anderen verbunden
nn
Anzahl der Knoten
∣E(Kn)∣|E(K_n)|
Anzahl der Kanten von Kₙ
(n2)\binom{n}{2}
Binomialkoeffizient „n über 2“, Anzahl der Paare aus n Elementen

Der vollständige Graph mit n Knoten hat n(n−1)/2 Kanten, so viele, wie es Paare aus n Elementen gibt.

Vollständiger Graph K₅ mit 5 Knoten und 10 Kanten

Erklärung

Im vollständigen Graphen KnK_n ist jeder der nn Knoten mit jedem anderen durch genau eine Kante verbunden. Die Formel zählt, wie viele Kanten das sind, also wie viele Paare man aus nn Elementen bilden kann.

Begründung durch Abzählen: Jeder Knoten hat n−1n - 1 Nachbarn, das ergibt n(n−1)n(n-1) Kantenenden. Jede Kante hat aber zwei Enden und wurde deshalb doppelt gezählt. Also ist die Kantenzahl n(n−1)2\frac{n(n-1)}{2}.

Alternativ zählt man nacheinander: Der erste Knoten bekommt n−1n - 1 neue Kanten, der zweite noch n−2n - 2, und so weiter. Das ist die Summe 1+2+…+(n−1)=n(n−1)21 + 2 + \ldots + (n-1) = \frac{n(n-1)}{2}.

Die gleiche Rechnung steckt in vielen Alltagsaufgaben: Alle stoßen mit allen an, alle geben sich die Hand, jede Mannschaft spielt einmal gegen jede andere. n(n−1)2\frac{n(n-1)}{2} ist auch die größtmögliche Kantenzahl eines einfachen Graphen mit nn Knoten (ohne Schleifen und Mehrfachkanten).

Beispiele

Anstoßen: 88 Personen stoßen jeweils einmal miteinander an. Das sind

8⋅72=28\frac{8 \cdot 7}{2} = 28

Klänge der Gläser.

Turnier: In einer Liga mit 1818 Mannschaften spielt in der Hinrunde jede einmal gegen jede andere: 18⋅172=153\frac{18 \cdot 17}{2} = 153 Spiele. Mit Rückrunde sind es 2⋅153=3062 \cdot 153 = 306.

Diagonalen im Vieleck: Die Ecken eines Sechsecks bilden 6⋅52=15\frac{6 \cdot 5}{2} = 15 Paare. Davon sind 66 Seiten, es bleiben 15−6=915 - 6 = 9 Diagonalen. Allgemein hat ein nn-Eck n(n−3)2\frac{n(n-3)}{2} Diagonalen.

Rückwärts: Bei einem Treffen gab es 4545 Händedrücke, jeder mit jedem. Aus n(n−1)2=45\frac{n(n-1)}{2} = 45 folgt n(n−1)=90n(n-1) = 90, also n=10n = 10 Personen.

Typische Fehler

  • Nicht durch 2 teilen. 8⋅7=568 \cdot 7 = 56 zählt jedes Anstoßen doppelt, einmal von jeder Seite.
  • n2n^2 oder n22\frac{n^2}{2} rechnen. Niemand stößt mit sich selbst an; jeder hat nur n−1n - 1 Partner.
  • Hin- und Rückspiel vergessen. Spielt jeder zweimal gegen jeden, sind es n(n−1)n(n-1) Spiele, ohne Division durch 2.

Verwandte Formeln