Kantenzahl des vollständigen Graphen
Voraussetzung:
- vollständiger Graph mit n Knoten, jeder Knoten ist mit jedem anderen verbunden
- Anzahl der Knoten
- Anzahl der Kanten von Kₙ
- 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.
Erklärung
Im vollständigen Graphen ist jeder der Knoten mit jedem anderen durch genau eine Kante verbunden. Die Formel zählt, wie viele Kanten das sind, also wie viele Paare man aus Elementen bilden kann.
Begründung durch Abzählen: Jeder Knoten hat Nachbarn, das ergibt Kantenenden. Jede Kante hat aber zwei Enden und wurde deshalb doppelt gezählt. Also ist die Kantenzahl .
Alternativ zählt man nacheinander: Der erste Knoten bekommt neue Kanten, der zweite noch , und so weiter. Das ist die Summe .
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. ist auch die größtmögliche Kantenzahl eines einfachen Graphen mit Knoten (ohne Schleifen und Mehrfachkanten).
Beispiele
Anstoßen: Personen stoßen jeweils einmal miteinander an. Das sind
Klänge der Gläser.
Turnier: In einer Liga mit Mannschaften spielt in der Hinrunde jede einmal gegen jede andere: Spiele. Mit Rückrunde sind es .
Diagonalen im Vieleck: Die Ecken eines Sechsecks bilden Paare. Davon sind Seiten, es bleiben Diagonalen. Allgemein hat ein -Eck Diagonalen.
Rückwärts: Bei einem Treffen gab es Händedrücke, jeder mit jedem. Aus folgt , also Personen.
Typische Fehler
- Nicht durch 2 teilen. zählt jedes Anstoßen doppelt, einmal von jeder Seite.
- oder rechnen. Niemand stößt mit sich selbst an; jeder hat nur Partner.
- Hin- und Rückspiel vergessen. Spielt jeder zweimal gegen jeden, sind es Spiele, ohne Division durch 2.