Starting from a directed star graph with $n$ nodes and all edges pointing away from the center, let two players alternate making one of the following moves:
Tail move: $b \leftarrow a \rightarrow c \leadsto a \rightarrow b \rightarrow c$
One can imagine the tail of the edge (a, c) following the edge (a, b), such that the edge (a, c) is replaced by the edge (b, c). (Or by symmetry we could make the other tail move replacing (a,b) with (c, b))
Head move: $a \rightarrow b \rightarrow c \leadsto b \rightarrow c \leftarrow a$
One can imagine the head of the edge (a,b) following the edge (b,c), such that the edge (a, b) is replaced by the edge (a,c).
We'll generally play on an unlabelled graph, the labels provided above just for clarity.
Here's an animation of a game on 10 nodes being played randomly:
This is an impartial game. The final position is a directed star graph on $n$ nodes with all edges pointing toward the center.
I have a whole host of questions about this game:
- Who wins the game on $n$ nodes? (Under normal game rules: If you can't move, you lose.)
- What is the optimal strategy?
- Is every polytree on $n$ nodes a possible position in the game?
- How many moves in the longest/shortest/best-played game on $n$ nodes?
- Average number of moves in a randomly played game on $n$ nodes?
As a bonus here's the python code I used for the animation:
import networkx as nx
import matplotlib.pyplot as plt
from random import choice
"""
hmove in: source --> target1 --> target2
hmove out: source --> target2 <-- target1
"""
def hmove(G, source, target1, target2): #Head move
G.remove_edge(source, target1)
G.add_edge(source, target2)
#Return a list of all possible head moves for a node.
def list_hmoves(G, source):
hmove_list=[]
for target1 in G.neighbors(source):
for target2 in G.neighbors(target1):
hmove_list.append([hmove, source, target1, target2])
return hmove_list
"""
tmove in: target1 <-- source --> target2
tmove out: source --> target1 --> target2
"""
def tmove(G, source, target1, target2): #Tail move
G.remove_edge(source, target2)
G.add_edge(target1, target2)
#Return a list of all possible tail moves for a node.
def list_tmoves(G, source):
tmove_list=[]
for target1 in G.neighbors(source):
for target2 in G.neighbors(source):
if target1==target2:
continue
tmove_list.append([tmove, source, target1, target2])
return tmove_list
#Return a list of all available moves for a node.
def list_moves_of_a_node(G, node):
move_list=[]
move_list.extend(list_hmoves(G, node))
move_list.extend(list_tmoves(G, node))
return move_list
#Return a list of all moves for all nodes.
def list_all_moves(G):
all_moves_list=[]
for node in G.nodes():
all_moves_list.extend(list_moves_of_a_node(G, node))
return all_moves_list
def draw_graph(G, filename):
nx.draw(G, pos=nx.circular_layout(G), node_color='black', node_size=20)
plt.title('Polytree Game Move {}'.format(move))
plt.savefig(filename, bbox_inches='tight')
plt.show()
#Create a star graph
number_of_nodes=10
G=nx.empty_graph(number_of_nodes,create_using=nx.DiGraph())
for i in range(1, number_of_nodes):
G.add_edge(0,i)
#Main Loop
move=0
draw_graph(G,'Polytree Game after {} moves.png'.format(move))
input('Enter to Continue')
nomoves=False
while not nomoves:
all_moves=list_all_moves(G)
if len(all_moves)>0:
random_move=choice(all_moves)
random_move[0](G, *random_move[1:])
move +=1
draw_graph(G,'Polytree Game after {} moves.png'.format(move))
input('Enter to Continue')
else:
nomoves=True
Partial answer:
Proof:
Let $a$ be the initial source node, so that $a$ starts with $n-1$ children and ends with $1$ child. Every tail move decreases the number of $a$'s children by at most $1$, and head moves do not affect $a$'s child count. Therefore, there must be at least $n-2$ tail moves. A similar argument applied to $z$, the vertex which becomes the sink in the terminal positions, implies there are at least $n-2$ head moves.
In the initial picture, label the edges of the graph $e_1,e_2,\dots,e_{n-1}$, so $e_i$ is the edge from $a$ to the $i^{th}$ vertex other than $a$. Over the course of the game, the labels of the edges move in a natural way. For example: $$ b\stackrel{e_i}\leftarrow a\stackrel{e_j}\to c\implies a\stackrel{e_i}\to b\stackrel{e_j}\to c $$ For each pair of edges $e_i$ and $e_j$, there can be at most one tail move involving both of them. After the tail move illustrated above, the source of $e_i$ ($a$) is strictly above the source of $e_j$ ($b$), and this property is preserved by further head and tail moves. The only exception is that a tail move involving $e_i$ and $e_j$ will render their sources incomparable, a property which is again preserved.
This means there are at most $\binom{n-1}2=\frac{(n-1)(n-2)}{2}$ tail moves. Applying the same logic to head moves gives the bound.
I leave it as an exercise to figure out how these bounds are achieved.