竞赛图的一些性质

又浪费了一个愉♂快的中午

为了方便表述,以下若无特殊说明,我们均考虑对于一个有个点的竞赛图。

我们约定表示有一条连向的边,表示能到达

性质一:任何一个竞赛图一定存在一条哈密顿路径

我们可以很容易的归纳证明。

时,显然存在哈密顿路径。

时,对于新加入的点,我们分下面三种情况考虑:

1、点向之前的所有点连边,从出发走到原哈密顿路径起点再沿之前的路径走即可。

2、之前的所有点向点连边,从原路径起点出发沿原路径走到终点再走到点即可。

3、之前某些点向点连边,点向剩下的点连边,考虑一定存在两个在原哈密顿路径上相邻的点(我们认为原哈密顿路径的终点和起点是相邻的,此时只需要换一个起点开始即可),前面的点向点连边,点向后面的点连边,那么把插在这两个点之间即可。

性质二:任何一个强连通的竞赛图一定存在一条哈密顿回路

我们也可以很容易的归纳证明。

时,显然存在哈密顿回路。

时,不是一般性,我们假设之前的回路为

考虑一个事实:一定存在两个在原回路上的相邻的点,然后只需要把插进之间即可。这个事实也很显然,因为如果不存在这样两个点,那么一定是点向之前所有的点连边,或者之前所有的点向点连边,这样显然与强联通矛盾。

性质三:对于一个竞赛图,将所有强连通分量缩点之后,一定形成一条链。(这里的链只对点考虑,与边无关)

这个性质也非常容易证明。首先,该竞赛图有一条哈密顿路径,我们在哈密顿路径上考虑。

我们不难发现,哈密顿路径上的强连通分量一定是成连续的一段,因为如果对于

那么,所以强连通。所以,缩点之后在哈密顿路径上形成一条链。

性质四:对于一个竞赛图,如果存在长度为的简单环,也一定存在长度为的简单环

我们先考虑环上的边,如果存在相邻的三个点,如果则删掉以后图仍然成环。

当不存在这样的时,那么我们就会得到个这样的三元环,我们再考虑三元环上的边。

为偶数时,这些三元环上返回的边构成了两个环,删去任意一个点后,我们找到它之前的点作为起点,再往前跳两个点作为终点,现在完整的环上走,然后再走完被破坏的环,最后回到终点。以为例,我们删掉了号点,那么我们从号点开始有

为奇数时,情况就变得复杂起来,由于上面的方法不是很可行,我们需要换一种思路。

由于存在个上面的三元环,所以删掉了任意一个点后,剩下的点显然可以通过后退两格,前进一格的方法全部强联通。或者我们可以考虑向一个三元环不断加入点,每一个加入的点都有一条连进去的和练出来的边,所以我们可以得到删掉任何一个点后,图仍是强连通的。

然后由于性质二,我们可以得到剩下的图仍存在哈密顿回路。

Q.E.D

竞赛图还有一些其他有趣的性质,留坑待填。