[MaLo] Ü8 A4

[Thomas]

Hab bei der a) folgendes heraus, hat jemand ähnliches heraus, oder hab ich ein paar Kanten vergessen?
Sei
G=
1 -> 2
|
\/
3 -> 4
und H=
5 -> 6

= {
(1,5),(1,6)
(1,5),(2,5)
(1,5),(3,5)
(1,6),(2,6)
(1,6),(3,6)
(2,5),(2,6)
(3,5),(4,5)
(3,6),(4,6)
(3,5),(3,6)
(4,5),(4,6)
}

= {
(1,5),(2,6)
(1,5),(3,6)
(3,5),(4,6)
}

= {
(1,2),(1,3),(3,4),(2,5),(4,5),(5,6)
}

EDIT: Hatte bei || noch 2 vergessen.

[stefffan]

Hallo.

Deine Lösungen zu i) und ii) sind leider aus syntaktischen Gründen irgendwie falsch. Bei der iii) könnte es aber stimmen. Außerdem denke ich, dass es keine so gute Idee ist, hier komplette Lösungen zu posten ... wenn, dann solltest du vielleicht nur Auszüge davon reinschreiben!

[nathan99]

Ich hab im Prinzip genau das gleiche, ich glaub bei mir stimmen sogar die Klammern der Tupel. .

*hust*

[kb]

Ich hab auch das gleiche.

bei der (b) hab ich, dass von den Fällen keins immer gilt.
Begründungen werd ich erst hinschreiben, wenn jemand anderer Meinung und bereit zur Diskussion ist ^^

---edit---
im Moment hab ich andere Meinungen, da ich auch einiges übersehen/falsch verstanden hatte ^^

[jim]

also bei der Sequenz ists klar, aber warum bei den anderen.
Wenn Spieler 0 ne Gewinnstrategie hat dann müssen alle Pfade im Spielgraphen gerade länge haben.

Bei der Komposition kann man dann einen Pfad aus Graph 1 und einen aus Graph 2 wählen hat also doppelt so lange Pfade. Aber immer noch gerade.

Beim Produkt kann man zwei Pfade (einen aus Graph 1 und einen aus Graph2) langgehen bis einer endet. Dieser endet aber nach einer geraden Länge.

Also müsste doch bei Komposition und Produkt eine Gewinnstrategier existieren.

Oder?

[Coolcat]

@jim:
Bei der (i) (Komposition) ist es nicht ganz so einfach. Ich denke es müsste eine Strategie existieren, aber es ist jedenfalls nicht einfach zu zeigen (bzw. alternativ bin ich nur zu blöde ). Habe mir da schon recht lange den Kopf dran zerbrochen.
Meine Idee sieht so aus:
Spieler 1 fängt an. Folglich kann Spieler 0 immer im selben Graphen ziehen, in dem auch Spieler 1 gezogen hat. Das dürfte immer funktionieren und ist vom Prinzip das was ihr euch auch gedacht habt (oder?)
Problem: Eine Gewinnstrategie wurde definiert als eine Funktion von einem Knoten zum anderen, es fehlt also die Information was der andere Spieler gemacht hat.

Die Begründung zu (ii) (Produkt) ist richtig, jedenfalls habe ich mir das auch so gedacht.

Bei der (iii) (Sequenz) dürfte es einfach gehen, da immer Spieler 1 anfängt. Spieler 0 hat gewonnen, wenn Spieler 1 nicht mehr ziehen kann. Daraus folgt das Spieler 1 als erster in H ziehen muss, wenn Spieler 0 seiner Strategie folgt.

[kb]

aaah, hab überlesen, dass immer Spieler 1 (in Vo) anfängt --__--
Aber dennoch: Es soll ja genzeigt/widerlegt werden, dass Spieler 0 IMMER einge Gewinnstrategie hat.

Kompostion: Spieler 1 nimmt Zug ((1,5),(3,5)). Somit kann Spieler 0 nicht mehr gewinnen.

Produkt: Naja, das Spiel endet nach 1 Zug, da ja in beiden Komponenten gezogen werden muss. Einfacher gehts doch kaum =]

Sequenz: siehe Komposition

[jim]

aaah, hab überlesen, dass immer Spieler 1 (in Vo) anfängt --__--
Aber dennoch: Es soll ja genzeigt/widerlegt werden, dass Spieler 0 IMMER einge Gewinnstrategie hat.

Kompostion: Spieler 1 nimmt Zug ((1,5),(3,5)). Somit kann Spieler 0 nicht mehr gewinnen.

Produkt: Naja, das Spiel endet nach 1 Zug, da ja in beiden Komponenten gezogen werden muss. Einfacher gehts doch kaum =]

Sequenz: siehe Komposition

Das Beispiel aus der Aufgabe kannste da doch gar nicht verwenden, weil in H hat Spieler 0 ja gar keine Gewinnstrategie.

[jim]

Bei der (iii) (Sequenz) dürfte es einfach gehen, da immer Spieler 1 anfängt. Spieler 0 hat gewonnen, wenn Spieler 1 nicht mehr ziehen kann. Daraus folgt das Spieler 1 als erster in H ziehen muss, wenn Spieler 0 seiner Strategie folgt.

Du musst dabei beachten das Spieler 1 wenn er in Graph 1 in einem Knoten nicht mehr kann von diesem Knoten zu v0 vom anderen Graphen wechselt. Dadurch beginnt Spieler 0 im zweiten Graphen und hat damit nicht unbedingt eine Gewinnstrategie.

Zur Komposition: Egal wie die beiden Spieler ziehen geht man jeweils einen Pfad in einem Graphen bis zum ende durch. Also bleibt die Gewinnstrategie.

[kb]

@Jim
Stimmt, das sind ja jetzt gar nicht die G und H aus Aufgabe a

Also "Spieler 0 hat dort Gewinnstrategien" ... heißt das, er hat Gewinnstrategien für jede Partie in G/H, oder er hat Gewinnstrategien von bestimmten Positionen in G/H??

[jim]

Gewinnstrategie heisst das er immer Gewinnen kann, egal was der andere macht. Also für jede Partie.

[kb]

Hm...nimm mal Beispiel G aus der (a).
Dort hat Sp-0 auch Geinnstrategie, nämlich von Position 3 aus. Trotzdem wird er das Spiel verlieren, weil Sp-1 eine Gewinnstrategie von einer "vorherigen" Position hat.

[nathan99]

Ich bin der Meinung, Spieler0 hat für E^|| und E^* eine Gewinnstrategie, aber für GoH nicht.

In G||H, weil:
Spieler1 beginnt das Spiel in v0 oder v'0, und zieht auf einen Nachfolger der beiden Knoten.
Das hindert S0 natürlich nicht am Verfolgen der Gewinnstrategie. S0 muss einfach nur immer in DEM Graphen weiterziehen, in dem S1 zuletzt gezogen hat - dann kann S1 nicht auf einen Knoten kommen, von dem S0 keine Gewinnstrategie mehr hat. (Denn das S0 eine Gewinnstrategie hat, impliziert ja eigentlich nur, dass er die von den Nachfolgeknoten der Startknoten für S1 hat *G*)

S1 kann sich bei manchen Graphenpaare höchstens aussuchen, in WELCHEM Graphen er "zuerst" verlieren möchte.


In GxH trivialerweise, weil S0 einfach in jedem Knoten nach der Gewinnstrategie für den entsprechenden Graphen die Kante wählt.
Fertig, aus. Glaubt doch jeder, oder?

In GoH hat S0 KEINE Gewinnstrategie, weil:
S0 hat Gewinnstrategie in G und H heisst, dass S0, wenn er in allen Nachfolgeknoten von v0 und v'0 drann ist, das Spiel gewinnt (wenn er will).
Das Spiel beginnt nun in G, mit Spieler1 der von v0 zieht.
Da S0 Gewinnstrategie hat, befindet sich S1 nach einigen Zügen auf einem Knoten in G, der keinen Nachfolger in G hat.
Nach der Definition des Spiels in GoH muss S1 dann auf v'0 ziehen.
Auf v'0 ist dann S0 an der Reihe.
Auf den Nachfolgeknoten von v'0 ist dann aber S1 an der Reihe, was "normalerweise", bei einem Spiel ausschliesslich in H, nie der Fall sein kann. Daher kann es S1 möglich sein, von allen (v'0)-Nachfolgern einen Knoten erreichen zu können, von dem S1 dann eine Gewinntrategie haben kann.

Beispielgraph folgt.

[kb]

hehe, hab den Beitrag grad editiert ^^

Ich setzte voraus, dass mein vorheriger Beitrag gilt ^^ denn so versteh ich das.

Sequenz: Sp-0 hat nicht immer GS.
Seien G und H:
* --> * --> *
Dann hat Sp-0 GS in G und H, da bei jedem Sp-1 anfangen würde.
Doch da in der Sequen Sp-1 in G verliert, zieht er von der letzten Position aus G nach v'. Somit beginnt Sp-0 in H und verliert die Sequenz. Damit hat Sp-0 auch keine einzige GS.
(--edit-- ich hatte die Sequenz auch falsch verstanden, denn so wie es da steht, zieht der Verlierer von G nach v', fängt aber nicht bei v' an!)

Produkt: Sp-0 hat immer GS.
Da Sp-1 in G und H anfängt, ändert das nichts an den Strategien, da das bei einzelnen Spielen in G und H identisch wäre. (Hoffe das ist verständlich ^^)

Komposition: überleg ich mir ncoh ^^
jedenfalls hat er GS ^^

[nathan99]

Ok, Beispielgraph siehe über diesem Post .

Jupp, ich denke mal das reicht als Argument...