MarcuMihai's blog

By MarcuMihai, history, 2 months ago, In English

There is a graph with n vertexes and m edges. Two players are playing a game on this graph.The first player colors a vertex and the second player can color only one of the neighbors of the vertex which was colored first.After that, the first player can color one of the neighbors of the vertex which was chosen by the second one, and so on.Formaly, a player can only color a neighbor to the vertex colored last by the other player. The player who can't color a vertex anymore wins. The question is that if the first player has a strategy to win. I've solved this problem if the graph is a tree using a DP but I can't see any connections between the tree problem and this one Thank you in advance!

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does the graph consist of one connected component? If so, one can just count the number of nodes of which are not leaves I guess. But if the graph consists of multiple connected components, then DSU will divide the graph into subproblems mentioned above. Correct me if I am wrong please

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, the graph consist only of one component, but I don't think that has anything to do woth the number of nodes that are not leaves. Can you be a bit more precise so I can understand you?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so the way I see it is like this: players take turns selecting a node that is a neighbor of the former node selected. what the players want is to pick a vertex of which all its neighbors are selected. for this to happen, the node has to be a leaf node or a root node. Cycles really dont matter because when the cycle is fully traversed, the players can always find an option to flee the cycle regarding its parity. So in a nutshell, players are trying to fore the other to give them a chance to color the leaf nodes OR the root node. I hope I explained clearly

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can one of the players colour a vertex that was coloured before?