patternMinor
Acyclic Tournament Digraphs and Hamiltonian Paths
Viewed 0 times
hamiltonianacyclictournamentpathsdigraphsand
Problem
I am studying MIT OCW lecture notes but they do not have solutions for the following problem.
Directed Acyclic Tournaments
In a round-robin tournament, every two distinct players play against each other
just once. For a round-robin tournament with no tied games, a record of who beat
whom can be described with a tournament digraph, where the vertices correspond
to players and there is an edge $x \rightarrow y$ iff $x$ beat $y$ in their game.
A ranking is a path that includes all the players. So in a ranking, each player won
the game against the next lowest ranked player, but may very well have lost their
games against much lower ranked players —whoever does the ranking may have a
lot of room to play favorites.
$Q$, is a DAG and a tournament graph that has no ranking.
I got stuck at questions 2, 3, and 4. I have no idea how to solve it. I tried induction on b without a luck but still induction does not even help for infinite DAG cases.
Directed Acyclic Tournaments
In a round-robin tournament, every two distinct players play against each other
just once. For a round-robin tournament with no tied games, a record of who beat
whom can be described with a tournament digraph, where the vertices correspond
to players and there is an edge $x \rightarrow y$ iff $x$ beat $y$ in their game.
A ranking is a path that includes all the players. So in a ranking, each player won
the game against the next lowest ranked player, but may very well have lost their
games against much lower ranked players —whoever does the ranking may have a
lot of room to play favorites.
- Give an example of a tournament digraph with more than one ranking.
- Prove that if a tournament digraph is a DAG, then it has at most one ranking.
- Prove that every finite tournament digraph has a ranking.
- Prove that the greater-than relation, $>$, on the rational numbers,
$Q$, is a DAG and a tournament graph that has no ranking.
I got stuck at questions 2, 3, and 4. I have no idea how to solve it. I tried induction on b without a luck but still induction does not even help for infinite DAG cases.
Solution
I am completing Nicholas's answer because I think there are problems with his answers to 3 and 4 and explaining why is a bit too long for comments.
For 3. you need to show there is a simple path in the tournament that visits every vertex (this is called a hamiltonian path). You can do this simply by induction. Clearly this is true for a tournament on 2 vertices. Now assume you have a tournament $T = (V, A)$ on $n$ vertices. Remove some arbitrary $v$ from $V$ and find a hamiltonian path $v_1, \ldots, v_{n-1}$ in the induced tournament on $V \setminus \{v\}$. If for all $i \leq n-1$, $(v_i, v) \in A$, then $(v_{n-1}, v) \in A$ and you can append $v$ to the existing path. Otherwise, there exists some edge from $v$ to the $\{v_1, \ldots, v_{n-1}\}$; let $i$ be the smallest integer such that $(v, v_i) \in A$. Either $i = 1$ and you can pre-pend $v$ to the existing path, or, since $i$ was the smallest $i$ such that $(v, v_i) \in A$, you know that $(v_{i-1}, v) \in A$, and, therefore, you can take the path $v_1, \ldots, v_{i-1}, v, v_i, v_{i+1}, \ldots, v_{n-1}$.
For 4., I also don't think it's enough to say that the rationals have no infimum or supremum. That's true of the integers too, but there exists a path through the integers which is infinite in both directions. I think the crucial property of the rationals that causes problems is that they are dense: there is a rational between every two rationals. In particular, assume for contradiction there exists a path that visits all rationals in the graph defined in the question. Take any edge $(x, y)$ in the path: $x < \frac{x+y}{2} <y$, so $\frac{x+y}{2}$ cannot precede $x$ in the path and it cannot succeed $y$, so it cannot be in the path - a contradiction.
For 3. you need to show there is a simple path in the tournament that visits every vertex (this is called a hamiltonian path). You can do this simply by induction. Clearly this is true for a tournament on 2 vertices. Now assume you have a tournament $T = (V, A)$ on $n$ vertices. Remove some arbitrary $v$ from $V$ and find a hamiltonian path $v_1, \ldots, v_{n-1}$ in the induced tournament on $V \setminus \{v\}$. If for all $i \leq n-1$, $(v_i, v) \in A$, then $(v_{n-1}, v) \in A$ and you can append $v$ to the existing path. Otherwise, there exists some edge from $v$ to the $\{v_1, \ldots, v_{n-1}\}$; let $i$ be the smallest integer such that $(v, v_i) \in A$. Either $i = 1$ and you can pre-pend $v$ to the existing path, or, since $i$ was the smallest $i$ such that $(v, v_i) \in A$, you know that $(v_{i-1}, v) \in A$, and, therefore, you can take the path $v_1, \ldots, v_{i-1}, v, v_i, v_{i+1}, \ldots, v_{n-1}$.
For 4., I also don't think it's enough to say that the rationals have no infimum or supremum. That's true of the integers too, but there exists a path through the integers which is infinite in both directions. I think the crucial property of the rationals that causes problems is that they are dense: there is a rational between every two rationals. In particular, assume for contradiction there exists a path that visits all rationals in the graph defined in the question. Take any edge $(x, y)$ in the path: $x < \frac{x+y}{2} <y$, so $\frac{x+y}{2}$ cannot precede $x$ in the path and it cannot succeed $y$, so it cannot be in the path - a contradiction.
Context
StackExchange Computer Science Q#10410, answer score: 3
Revisions (0)
No revisions yet.