Gewinnstrategie eines Löschspiels „Rand oder isolierter Scheitelpunkt“

Ist dieses perfekte Informationsspiel, das auf Grafiken gespielt wird, bekannt / studiert?

Bei einem Graphen wählen zwei Spieler abwechselnd eine Kante oder einen isolierten Knoten aus. Wenn der Spieler eine Kante die beiden Knoten und zusammen mit ihren einfallenden Kanten gelöscht. Wenn der Spieler einen isolierten Knoten auswählt, wird der Knoten gelöscht. Der erste Spieler, der sich nicht bewegen kann, verliert das Spiel. e = ( u , v ) u $G= (V,E)$$e = (u,v)$$u$$v$

Wie komplex ist es, den Gewinner zu finden?

Irgendwelche Verweise auf ähnliche Spiele?

Ich poste ein Update nur als Selbstantwort, um es von der noch offenen Frage zu unterscheiden .

Wie in den Kommentaren gezeigt (dank Tsuyoshi Ito), ist das Problem in der Polynomzeit für Pfade lösbar:

$Win(P_n) = 1$ iif$(n \bmod 34) \in \{3,7,23,27\}$

Ab 0 ist die (berechnete) Folge der Nim-Werte periodisch:

0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
...
the subsequence rseq of length 34:
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6
is repeated

Ich habe nicht an einem strengen mathematischen Beweis gearbeitet, aber die Idee ist:

Angenommen, wir wollen das Element berechnen , dann kann die erste Bewegung (eine Kante auswählen) den Pfad auf verschiedene Arten (n-2,0), (n-3, 1), (n-4,2), ...). Der neue Nim-Wert ist gleich:$Win(P_n), n = k*34 + x \; (k\geq 4, 0 \leq x < 34)$$\lceil n / 2 \rceil$

$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$

Die ersten 34 Elemente der Menge werden durch die erste nicht wiederholte Sequenz (0,1,1,0, ...) (nim) erzeugt, die mit den Elementen der sich wiederholenden Sequenz in umgekehrter Reihenfolge beginnend mit Element .$(34-2-x) \bmod 34$

Zum Beispiel: für :$x = 0$

     0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6 +
     3,4,4,1,1,0,2,1,3,0,1,1,3,2,2,7,5,4,4,3,2,2,3,1,1,0,3,1,2,0,1,1,4,6 =
mex{ 3,5,5,1,3,1,1,1,2,1,2,3,1,1,6,6,0,7,6,1,1,3,2,1,2,1,1,1,3,1,5,5,6,0 } = 4

Für x = 0..33 ist die resultierende mex-Sequenz gleich der sich wiederholenden Sequenz:

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6

Die verbleibenden Elemente der Menge werden nur für die Wiederholungssequenz (en) : (für die Paare also wiederholt Sie ändern das mex-Ergebnis nicht. Die resultierende mex-Sequenz für x = 0..33 lautet:$rseq[j \bmod 34] + rseq[(34-2-x-j) \bmod 34]$$j \geq 34$

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,4,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,4,

Welches ist gleich der Wiederholungssequenz mit Ausnahme von und ; aber die Werte sind niedriger als das entsprechende mex in der nicht wiederholenden Sequenz, also:$x=16$$x=33$

$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$ =$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{n-2-33}+P_{33}\}$

und für ist$(k\geq 4, 0 \leq x < 34)$$Win(P_{k*34 + x}) = Win(P_{34+x}) = Win(P_x)\;$