一道图论题

最近看到一道很有意思的图论题，来自Mit公开课Session 16。

In a round-robin tournament, every two distinct players play against each other just once. For around-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 $\langle x\to y\rangle$ 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 ranked player, but may very well have lost their games against players ranked later—who ever does the ranking may have a lot of room to play favorites.

(a)Give an example of a tournament digraph with more than one ranking.

(b)Prove that every finite tournament digraph has a ranking.

(a)图为

$1\to2,2\to 3,3\to 1$

那么ranking为

$1,2,3;2,3,1$

(b)只要证明存在一个经过每个点的path即可，假设图中共有$n$个节点，设最长路径为$r$，并且设长度为$r$的全体路径为

$a^{(1)}_1...a^{(1)}_r\\ a^{(2)}_1...a^{(2)}_r\\ \ldots \\ a^{(s)}_1...a^{(s)}_r\\$

记构成这些路径的节点为$A$，考虑其补集$B$，设

$B=\{b_1,...,b_m\}$

下面证明

$r= n$

首先证明

$B=\varnothing$

利用反证法，如果$B\neq \varnothing$，那么首先我们必然有

$a^{(i)}_r \not \to b_k ,\forall i,j,k$

那么由round-robintournament的性质，我们必然有

$b_k \to a^{(i)}_r ,\forall i,j,k$

接着考虑$a^{(i)}_{r-1}$和$ b_k$的关系，事实上，我们依然有

$a^{(i)}_{r-1} \not \to b_k ,\forall i,j,k$

这是因为如果上述事实不成立，那么存在$i,k$，使得有如下长度为$r+1$的路径

$a^{(i)}_1... a^{(i)}_{r-1}b_k a^{(i)}_{r}$

这就与条件矛盾，所以

$b_k \to a^{(i)}_{r-1} ,\forall i,j,k$

利用归纳法，同样可以证明

$b_k \to a^{(i)}_{l} ,\forall i,j,k,l$

因此我们有长度为$r+1$的路径

$b_k a^{(1)}_1...a^{(1)}_r$

这就与$A$的定义矛盾，所以

$B= \varnothing,|A| =n$

现在利用这点证明$r=n$，如果不成立，那么有$r\le n-1$，又因为$|A| =n$，所以必然存在两条路径，其包含的节点不全相同，不妨设为

$a^{(i)}_1...a^{(i)}_r, a^{(j)}_1...a^{(j)}_r$

如果

$a^{(i)}_r \neq a^{(j)}_r$

那么必然有一个胜者，不妨设为$a^{(i)}_r$，因此

$a^{(i)}_1...a^{(i)}_ra^{(j)}_r$

为一条长度为$r+1$的路径，产生矛盾，所以必然有

$a^{(i)}_r=a^{(j)}_r$

利用归纳法，同样可以推出我们有

$a^{(i)}_k=a^{(j)}_k,k=1,...,r$

这就与这两条路径包含的节点不全相同产生矛盾，因此必然有$r=n$。