 |
 |
 |
 |
 |
 |
Startseite » Forum » Schere-Stein-Papier Erweiterung
Schere-Stein-Papier Erweiterung
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie, Kantenfärbung, Knotenfärbung, Scheresteinpapier
 
|
  |
|---|
|
Hallo zusammen, ich komme aktuell bei einer Schere-Stein-Papier Aufgabe nicht ganz voran. Das bekannte Spiel soll durch neue Symbole erweitert werden, ohne das man die Eigenschaft verliert, dass jedes Symbol gegen gleich viele andere Symbole gewinnt wie verliert. Unentschieden soll es nur geben, wenn beide Spieler das selbe Symbol wählen. Die erste Aufgabe "Zeige, dass ein solches Spiel mit vier Symbolen nicht existieren kann." habe ich durch schlichtes Argumentieren gelöst, da bei 4 Symbolen (Knoten) jeder Grad 3 haben muss und daher ein Symbol nicht gegen gleich viele verlieren wie gewinnen kann. Bei der zweiten Aufgabe "Für welche Anzahl an Symbolen kann man ein ausgewogenes Spiel definieren? Begründe deine Antwort und gib ein systematisches Verfahren zur Erzeugung der Spielregeln an." habe ich mir erst einmal aus erstens hervorgehend gedacht, dass die Anzahl der Symbole auf jeden Fall ungerade sein muss, da bei jeder geraden Anzahl von Symbolen wieder keine ausgewogene Gewinn/Verlier Verteilung möglich ist. Ob das schon ausreichend ist weiß ich jedoch nicht. Mein größtes Problem habe ich mit dem letzten Teil, der Erzeugung der Spielregeln, also übertragen auf die Graphentheorie, wie man bei gegebenen Knoten gerichtete Kanten (zum Zeigen gewinnt gegen) so verteilen kann, dass am Ende jeder Knoten gegen andere Symbole (Knoten) gewinnt und verliert. Wir hatten uns zuletzt über Kanten und Knotenfärbung unterhalten, weshalb ich versucht habe einen Ansatz dort zu finden, aber Knotenfärbung macht in meinen Augen nur wenig Sinn und mit der Kantenfärbung komme ich auch zu keinem sinnvollen Ergebnis. Danke schon einmal für eure Hilfe :-) PS: Für habe ich mal ein Beispiel angehangen  |
|
 |
|
Schau mal bei YT nach Hannah Fry - die hat das gut erläutert. |
|
|
|
Beweise doch einfach per Vollständiger Induktion über , dass sich ein Vollständiger Graph mit Knoten sich in der von dir beschriebenen Weise färben lässt: Im Induktionsschritt nimmst du von den beliebige zwei Knoten zunächst mal gedanklich weg und färbst den Restgraphen gemäß Induktionsvoraussetzung. Nun überlegst du noch, wie du die verbleibenden Kanten des Gesamtgraphen (das sind Kanten von den zwei neuen Knoten zu dem Altgraphen plus die eine Kante zwischen den beiden neuen Knoten) so färbst, dass die gewünschte Eigenschaft immer noch erfüllt ist. Dazu ist kein gewaltiger Geistesblitz nötig, das ergibt sich fast von selbst mit ein wenig gesundem Menschenverstand. |
 |
|
Wir haben in der Vorlesung schon gezeigt, dass man um einen vollständigen Graphen mit Knoten zu färben Farben für die Kanten braucht. Ich sehe nicht, wie mir das helfen sollte zu entscheiden, wie ich die Kanten gewichte, damit ein gerichteter Graph bei heraus kommt, in dem jeder Knoten gleich viele gerichtete Kanten von sich weg wie zu sich hin hat. Außerdem muss ich zugeben, dass ich nicht ganz verstehe, woher du hernimmst und was genau das hierbei sein soll, wobei ich noch anmerken muss, dass ich mich in meiner ursprünglichen Frage am Ende verschrieben hab, es ist logischerweise ein vollständiger Graph für und nicht . Danke aber auf jeden Fall für dein Antwort! |
|
|
|
Für eine gerade Knotenzahl geht es nicht (deine Überlegung für 4 Knoten lässt sich auch auf eine beliebige gerade Knotenanzahl übertragen). Für eine ungerade Knotenanzahl geht es jedoch, und genau darum geht es in dem vorgeschlagenen Induktionsbeweis. Ich hatte angenommen, dass das nach deinen Vorüberlegungen klar ist, aber da habe ich mich anscheinend getäuscht. Ich wollte eigentlich auch eher über gerichtete Kanten statt über gefärbte Kanten sprechen, denn das passt ja eher zur Aufgabenstellung. Nun gut, beide Betrachtungsweisen kann man äquivalent aufeinander abbilden, wenn wir ZWEI Farben betrachten sowie eine gewisse Ordnung der Knoten einbeziehen - aber so richtig sinnvoll finde ich das hier nicht. |
|
|
|
Aber durch deinen Beweis zeigst du doch nur, dass man einen Graph unter den gewollten Bedingungen erstellen kann solang er eine ungerade Anzahl an Knoten hat aber nicht wie man ihn erstellen kann, was für mich die Aufgabenstellung "gib ein systematisches Verfahren zur Erzeugung der Spielregeln an" eher verlangt. Ich verstehe das so, dass sie ein generelles effizientes Vorgehen, quasi einen Algorithmus verlangen, der dir sagt, wie du am Besten bei gegebenen Knoten vorgehst oder sehe ich das falsch ? |
|
|
|
Du irrst: Der Induktionsbeweis, der mir vorschwebt, ist durchaus konstruktiv, d.h., er beschreibt genau, wie man aus einem "gültigen" -Graph durch passende Kantenergänzungen einen -Graph bastelt. Insofern leistet er das von dir geforderte, wenn man dann sukzessive solche Graphen mit 3, 5, 7, 9, ... Knoten aufbaut. |
|
|
|
"Stein - Papier - Schere - Echse - Spock!" |
|
|
|
"Stein - Papier - Schere - Echse - Spock!" klasse Idee - wie bist Du nur da drauf gekommen ? |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1451560
1451484