Glossar

Wähle eines der Schlüsselwörter auf der linken Seite…

Graphen und NetzwerkeHändeschütteln und Dating

Lesezeit: ~15 min

Du bist zu einer tollen Geburtstagsparty mit deinen Freunden eingeladen worden. Einschließlich dir selbst und dem Gastgeber sind ${hnd} Gäste anwesend.

Als die Gäste sich abends zum Aufbruch bereit machen, schüttelt jeder jedem anderen die Hand. Wie oft werden insgesamt die Hände geschüttelt?

Wir können das Händeschütteln mit einem Graphen darstellen: jeder Gast entspricht , und jedes Händesschütteln entspricht .

Jetzt kann man ganz einfach die Anzahl der Kanten im Graphen zählen. Wir stellen fest, dass bei ${hnd} Gästen ${hnd*(hnd-1)/2} mal die Hände geschüttelt werden.

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 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 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×n12 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?

In diesem Fall besteht der entsprechende Graph aus zwei getrennten Gruppen von Knoten. Jeder Knoten ist mit allen Knoten in der , aber keiner der Knoten mit denen in Gruppe verbunden. Graphen, die diese Anordnung haben, werden bipartite Graphen oder paare Graphen genannt.

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