一道图论题

最近看到一道很有意思的图论题,来自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)图为

那么ranking为

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

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

下面证明

首先证明

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

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

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

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

这就与条件矛盾,所以

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

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

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

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

如果

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

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

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

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

本文标题:一道图论题

文章作者:Doraemonzzz

发布时间:2019年03月30日 - 20:43:50

最后更新:2019年03月30日 - 21:01:11

原始链接:http://doraemonzzz.com/2019/03/30/一道图论题/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。