Graphen und NetzwerkeHändeschütteln und Dating

Anstatt alle Kanten in großen Graphen zu zählen, könnten wir auch versuchen, eine einfache Formel zu finden, die uns das Ergebnis für eine beliebige Anzahl von Gästen angibt.

Jeder der ${n} Gäste auf der Party schüttelt ${n-1} anderen die Hand. Es werden also insgesamt ${n} × ${n-1} = ${n×(n-1)} mal die Hände geschüttelt. Für n Gäste heißt das, dass n×n−1n×n+1n2 mal die Hände geschüttelt werden.

Leider ist diese Antwort nicht ganz richtig. Beachte, dass die ersten beiden Einträge in der obersten Zeile eigentlich identisch sind, nur umgedreht.

Tatsächlich haben wir jedes Händeschütteln zweimaleinmaldreimal gezählt, einmal für jeden der beiden beteiligten Gäste. Das bedeutet, dass die korrekte Anzahl wie oft bei ${n} Gästen einander die Hände geschüttelt werden ${n}×${n-1}2=${n*(n-1)/2} beträgt.

Die Graphen, die das Händeschütteln beschreiben, stellen einen besonderen Fall dar, weil jeder Knoten mit jedem anderen Knoten verbunden ist. Graphen mit dieser Eigenschaft werden vollständige Graphen genannt. Ein vollständiger Graph mit 4 Knoten wird oft als K4 abgekürzt, ein vollständiger Graph mit 5 Knoten wird als K5 bezeichnet, und so weiter.

Wir haben gerade gezeigt, dass ein vollständiger Graph mit n Knoten, also Kn, genau n×n−12 Kanten hat.

An einem anderen Tag bist du zu einem Speed-Dating-Event für ${m} Jungs und ${f} Mädchen eingeladen. Es gibt viele kleine Tische und jeder Junge verbringt 5 Minuten mit jedem der Mädchen. Wie viele einzelne "Dates" ergibt das insgesamt?

Der zweigeteilte Graph mit zwei Gruppen der Größe x und y wird oft als Kx,y geschrieben. Er hat x×yx+y2x−y Kanten, was bedeutet, dass es im obigen Beispiel zu ${m} × ${f} = ${m×f} Dates kommt.