1
$\begingroup$

Greography is a game where players take turns naming cities. Each city chosen must begin with the same letter that ended the previous city. The game begins with any starting city and ends when a player loses because he is unable to continue.

This can be modelled with a directed graph $G=(V,E)$ where $(i,j)\in E$ $\Leftrightarrow$ $j$ can be named immediately after $i$.

A subset $M\subseteq M$ is called a matching in $G$ $\Leftrightarrow$ ($v\in V\Rightarrow v$ is incident to at most one edge in $M$). $M$ is called a perfect matching in $G$ $\Leftrightarrow$ $|M|=\frac{|V|}{2}$.

This implies that |V| must consists of an even count of nodes and that each node is incident to exactly one edge in $M$, if $M$ is a perfect matching in $G$.

I'm searching for an explanation why the first player has a winning strategy if and only if $G$ has no perfect matching.

If $M=\left\{(a_i,b_i) : 1\le i\le \frac{|V|}{2}\right\}$, then the player who needs to find a node after $a_i$ for some $i$ can use the matching edge $(a_i,b_i)$ to do so.

However, this is it. So, what's the winning strategy of the first player if $G$ has a perfect matching?

$\endgroup$
  • 1
    $\begingroup$ As stated this is false for directed graphs. For instance, consider the graph with two vertices and a single directed edge between them; the first player can win by naming the vertex with outdegree 0. You might want to check if your source has a different definition for matching in a directed graph? $\endgroup$ – universalset Jan 13 '14 at 12:56
  • $\begingroup$ @universalset - I may have misinterpreted the statement and reformulated it. I hope it's now more clear. $\endgroup$ – 0xbadf00d Jan 13 '14 at 13:17
1
$\begingroup$

The first player should find a maximum matching of $G$. His first move should be to pick an unmatched vertex(it is possible since the graph has no perfect matching) and every subsequent move should be to pick the vertex matched to the vertex the second player picked. Player two choices are always matched making it possible for player one to have a move. For if they were not, you could find an augmenting path(a path with its internal vertices matched but its ends vertices are unmatched)for the matching through which you could make the matching bigger which is impossible since we started with a maximum matching.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I assume it's related to the "$G$ has no perfect matching"-part, isn't it? What would be the winning strategy of player one, if $G$ has a perfect matching? Thanks in advance for your help. $\endgroup$ – 0xbadf00d Jan 14 '14 at 15:25
  • 1
    $\begingroup$ If the graph has a perfect matching, then player one has no winning strategy. Player two can use the perfect matching to beat player one. $\endgroup$ – hbm Jan 14 '14 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.