Graphentheorie: Stellen Sie die Situation durch einen Graphen dar

Question

Aufgabe:

Bei einem lokalen Schachturnier treten 5 Personen mit Namen A, B, C, D und E gegen-
einander an. Jede Person spielt einmal gegen jede der anderen Personen. Es darf jedoch
niemand zwei Spiele an einem Tag bestreiten.
Stellen Sie die Situation durch einen Graphen dar, dessen Knoten die Spiele sind und der
zwischen zwei Knoten genau dann eine Kante besitzt, wenn es eine Person gibt, die bei
beiden Spielen mitspielt. Geben Sie ein Diagramm dieses Graphen an.
Untersuchen Sie, wie viele Farben nötig sind, um die Knoten des Graphen so zu färben, dass
keine zwei benachbarten Knoten dieselbe Farbe haben. Geben Sie eine solche Knotenfärbung
in einem Diagramm des Graphen an.
Verwenden Sie Ihr Ergebnis, um die Anzahl der Spieltage zu bestimmen, so dass die obigen
Turnierbedingungen erfüllt sind.

Problem/Ansatz:

Kann mir jemand erklären wie ich das das Diagramm zeichnen soll, die anderen Aufgaben verstehe ich, aber nicht wie ich es zeichnen soll

Answer 1

Stellen Sie die Situation durch einen Graphen dar

Ein Graph besteht aus einer Menge E (genannt "Ecken") und einer Menge von zweielementigen Teilmengen von E (genannt "Kanten").

Geben Sie ein Diagramm dieses Graphen an.

Ein Diagramm besteht aus Punkten (genannt "Ecken") in der Ebene und Strecken (genannt "Kanten") die diese Punkte verbinden.

Answer 2

Ich versuche es mal mit einem Tipp:

Jede Person spielt einmal gegen jede der anderen Personen. (...) Stellen Sie die Situation durch einen Graphen dar, dessen Knoten die Spiele sind...

Ein "Spiel" lässt sich hier immer als "Paar von Personen" beschreiben. Da nur einmal gespielt wird, kommt es bei den Paarungen nicht auf die Reihenfolge an, daher lässt sich ein "Spiel" durch eine zweielementige Menge von beteiligten Personen charakterisieren, also etwa \(\left\{A,B\right\}\) für das Spiel \(A\) gegen \(B\). Das lässt sich natürlich auch kurz als \(AB\) notieren. Diese insgesamt zehn Paare bilden die Knoten des Graphen.

...und der zwischen zwei Knoten genau dann eine Kante besitzt, wenn es eine Person gibt, die bei beiden Spielen mitspielt.

Zwischen den Knoten \(AB\) und \(BC\) muss es also eine Kante geben, nicht aber zwischen \(BC\) und \(DE\).

Comments

Also mit deinem Tipp hab ich versucht die Aufgabe zu lösen:

{AB,AC,AD,AE}

{AB,BC,BD,BE}

{AC,BC,CD,CE}

{AD,BD,CD,DE}

{AE,BE,CE,DE}

Also zwischen den Knoten gebe es eine Kante. Also ich habe 24 Kanten. Ist das richtig

---

Nun, ich verstehe nicht so recht, was du da gemacht hast. Eine Kante besteht aus genau zwei Knoten, die hier zudem noch voneinander verschieden sein müssen.

---

Ich habe was versucht, weiß auch nicht mehr was ich dort gemacht habe.

Eine ganz wichtige Frage: Kann es eine Kante zwischen AB und AC geben oder bei BC und BD?