Zwycięska strategia gry polegającej na usuwaniu „krawędzi lub izolowanego wierzchołka”

Czy ta doskonała gra informacyjna rozgrywana na wykresach jest znana / studiowana?

Biorąc pod uwagę wykres $G= (V,E)$ , dwóch graczy na przemian wybiera krawędź lub izolowany węzeł. Jeśli gracz wybierze krawędź $e = (u,v)$ dwa węzły $u$ i $v$ zostaną usunięte wraz ze swoimi krawędziami padania. Jeśli gracz wybierze izolowany węzeł, węzeł zostanie usunięty. Pierwszy gracz, który nie może się poruszyć, przegrywa.

Jaka jest złożoność znalezienia zwycięzcy?

Jakieś odniesienia do podobnych gier?

Publikuję aktualizację jako odpowiedź własną, aby odróżnić ją od pytania ( które jest nadal otwarte ).

Jak pokazano w komentarzach (dzięki Tsuyoshi Ito) problem polega na rozwiązaniu ścieżek wielomianowych:

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

Począwszy od 0, (obliczona) sekwencja wartości NIM jest okresowa:

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

Nie pracowałem nad rygorystycznym dowodem matematycznym, ale pomysł jest taki:

załóżmy, że chcemy obliczyć element , a następnie pierwszy ruch (wybierz krawędź) może podzielić ścieżkę na ⌈ n / 2 ⌉ na różne sposoby (n-2,0), (n-3,1), ( n-4,2), ...). Nowa wartość nim jest równa:$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}\}$

Pierwsze 34 elementy zestawu są wytwarzane przez pierwszą niepowtarzalną sekwencję (0,1,1,0, ...) (nim) zsumowaną z elementami sekwencji powtarzalnej w odwrotnej kolejności, zaczynając od elementu .$(34-2-x) \bmod 34$

Na przykład: dla :$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

Dla x = 0..33 wynikowa sekwencja mex jest równa powtarzalnej sekwencji:

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

Pozostałe elementy zestawu są calulated tylko w powtarzającej się sekwencji (a): (w j ≥ 34 z pary są powtarzane, więc nie zmieniają wyniku mex). Wynikowa sekwencja mex dla x = 0..33 to:$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,

Co jest równe powtarzającej się sekwencji, z wyjątkiem i x = 33 ; ale wartości są niższe niż odpowiadający mex w powtarzającej się sekwencji, więc:$x=16$$x=33$

= m e x { P n - 2 + P 0 , P n - 3 + P 1$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}\}$

oraz dla , W i n ( P k ∗ 34 + x ) = W i n ( P 34 + x ) = W i n ( P x$(k\geq 4, 0 \leq x < 34)$$Win(P_{k*34 + x}) = Win(P_{34+x}) = Win(P_x)\;$