Graphentheorie Schachturnier |
05.01.2023, 17:21 | charlene126 | Auf diesen Beitrag antworten » |
Graphentheorie Schachturnier 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. Meine Ideen: 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 {A,B} 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. Zwischen den Knoten AB und BC muss es also eine Kante geben, nicht aber zwischen BC und DE. Kann es auch eine Kante zwischen AB und AC geben, da ja A bei beiden Spiele mitspielt oder Kann es auch eine Kante zwischen BC und BD geben, da ja B bei beiden Spiele mitspielt. Ist es richtig dieses Idee oder habe ich da ein Denkfehler? |
||
05.01.2023, 18:18 | Elvis | Auf diesen Beitrag antworten » |
Bis jetzt stimmt alles. 10 Knoten. Wie viele Kanten ? Darstellung des Graphen ? Weitere Antworten ? |
||
05.01.2023, 19:07 | peter245 | Auf diesen Beitrag antworten » |
Naja die Frage war ob, es Kanten gibt zwischen Ab und Ac bzw. Bc Bd. Ich würde es sagen, laut der Definition der Aufgabe, dass Ab und Ac eine Kante haben bzw. Auch Bc und Bd. Vielleicht weiß es auch Elvis ob, das stimmt mit der Kantenverbindung |
||
05.01.2023, 19:49 | Elvis | Auf diesen Beitrag antworten » |
Da sind wir uns alle einig. Wenn in zwei Knoten XY und XZ ein Spieler X enthalten ist, dann gibt es die Kante XYXZ, wenn nicht, dann nicht. So steht es in der Definition des Graphen. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |