Graphentheorie II

[ISsToRm]

Folgendes Problem:

Es soll ein Skatturnier veranstaltet werden, je 3 Spieler pro Partie und jeder gegen jeden GENAU 1x

1) Welche Spieleranzahl n ist zulässig wenn niemand aussetzen soll?

Da habe ich mir überlegt, dass Spieler 1 in der ersten Runde gegen 2 Gegner spielt, dann gegen wieder 2 andere usw, also muss n ungerade sein. Damit niemand aussetzen muss, sollte n aber auch ein vielfaches von 3 sein.

Also n = 3 + 6k, seht Ihr das auch so?

2) Wie lässt sich das graphentheoretisch modellieren?

Bei einem normalen Turnier mit je 2 Spieler pro Paarung bekomme ich das hin, dann erhält man den vollständigen Graphen und der ist 1-faktorisierbar falls n gerade ist und somit dauert ein Turnier mit n Spielern dann genau n-1 Runden. Bei 3 Spielern pro Partie bin ich mir unsicher, hat das auch was mit Faktorisierung zu tun (bzw Matching)? Anzahl der Runden ist klar, das sind immer (n-1) / 2

3) Lösungsalgorithmus für n Spieler? bzw eine Idee?

Für n = 3 und n = 9 habe ich eine Lösung gefunden, also für n = 3 natürlich 1 Runde und für n = 9 sind es 4 Runden. Das geht für n = 9 ganz gut geometrisch wenn man die 9 Spieler als Knoten in einem Quadrat anordnet und dann einmal waagerecht, einmal senkrecht, dann diagonal und gegendiagonal spielt. Für den Fall n = 15 (muss ich auch noch machen) fällt mir aber keine vernünftige geometrische Anordnung ein, bzw kein Algorithmus.

mfg

 

[killerchicken_inaktiv]

1) sehe ich auch so.

Bei den anderen Fragen: Sind das wirklich die einzigen Angaben bzw hast du deine Aufgabenstellung exakt wiedergegeben? Wörter wie "Lösungsalgorithmus" sind ein wenig mehrdeutig... Was soll modelliert werden? Hast du eine Vorgabe (zB Spieler immer als Knoten), etc.

 

[ISsToRm]

die Aufgabenstellung zu 2) und 3) sind exakt wiedergegeben, ja

bzw zu 2) ist die exakte Frage, welcher graphentheoretischen Problemstellung das entspricht

und bzgl des Lösungsalgorithmus, damit ist gemeint, wie sich bei einer vorgegebenen (zulässigen) Anzahl von Spielern heuristisch ein Spielplan entwickeln lässt

bei 2 Mannschaften pro Spiel zB gibt es ein Verfahren der geometrischen Anordnung in einem regelmäßigen n-Eck und dann eine Rotation

muss aber nichts geometrisches sein, ist offen gelassen in der Aufgabenstellung

 

[ISsToRm]

http://mathworld.wolfram.com/KirkmansSchoolgirlProblem.html

Man muss nur 6-8 Stunden googlen...wargh

Kann geschlossen werden

 

[killerchicken_inaktiv]

oh, ok. Ich war gerade dabei eine coole Lösung mit 3 Rädern zu entwickeln, die man drehen muss für den Algorithmus... So sieht das ganze aber ein wenig hybscher aus.