- Un idra qualunque è data, un idra è un albero finito, ovvero un grafo connesso senza cicli e un nodo specificato è chiamato $R$ ed esso è la radice del albero. Ciascun nodo ha un singolo parente (tranne la radice che non ha parenti) e un numero di figli. L'obbiettivo è rimanere con soltanto la radice $R$. In altre parole il giocatore vince il gioco se dopo un numero finito di mosse rimane solo $R$. Come si gioca?
Step 1) A ciascuna mossa il giocatore seleziona una foglia $z$ e un numero naturale $n>0$. Una foglia è semplicemente un nodo che non possiede figli.
Step 2) Selezionata la foglia $z$, il giocatore cancella $z$ e l'arco che la connette al suo parente. Denotando $x$ il parente di $z$, se $x=R$ allora il gioco continua allo step 1), altrimenti se \(x \neq R\) allora guardiamo il sotto grafo che cresce da $x$ (dopo aver cancellato $z$) e sia $y$ il parente di $x$. Attacchiamo $n$ copie del sotto grafo che cresce da $x$ al vertice $y$. Un immagine sarà più chiara
Nel immagine, il nodo nero è la radice $R$, i nodi blu sono le foglie, il nodo cancellato è quello tratteggiato,
$n$ è scelto essere uguale a $2$.
Testo nascosto, fai click qui per vederlo
E' possibile perdere questo gioco?