从两两比较到有向图
设每两位选手恰好比赛一次,且没有平局。从胜者向负者画箭头,就记录了所有结果。但结果未必能排成一致的名次:可能 胜 , 胜 ,而 又胜 。同样的模型也适用于其他完整的、不对称的两两比较,并不要求先给对象赋数值分数。
定义 5.2.1
(竞赛图、有向路径与有向圈)
竞赛图是有限有向图:没有自环,并且对任意不同顶点 , 和 恰有一条。有向路径由互不相同的顶点组成,相邻箭头都向前。哈密顿(Hamilton)路径恰好经过每个顶点一次。有向圈沿箭头走,除起点与终点相同外顶点不重复。出度 是 的出邻点数。允许空竞赛图;约定空排列是其哈密顿排列。讨论可达性时,顶点通过长度零的路径到达自身。
每个竞赛图都有哈密顿路径
这个结论不要求存在战胜所有对手的选手。证明的办法是把一个新顶点插入已有路径,而不是按出度排序。
定理 5.2.2
(竞赛图的有向哈密顿路径)
每个有限竞赛图都有顶点排列 ,使每个 都满足 。
证明
(插入新顶点)
对顶点数归纳。空图和单顶点图显然成立。删除顶点 ,由归纳假设,将其余顶点排成有向路径 。若 ,便把 放在最前。否则,取满足 的最大指标 。若 ,便把 加在末尾;若 ,由最大性, 不指向 。竞赛图中两者之间恰有一个方向,故 。将 插在 和 之间,只把原来的相邻箭头替换为 ,所得仍是经过所有顶点的有向路径。
证明透视
为什么最后一个入邻点标出可用的空位
归纳假设用于删去 后的竞赛图,而它仍是竞赛图:这个类在删去顶点后封闭,证明正依赖这一点。插入所需的是路径上的一个转换位置:某处有 且 ,或者是路径的某一端。分情况讨论保证这样的位置存在。若 ,转换位置在起点之前。否则 ,于是满足 的指标集非空,有最大元 。或者 ,把 放在末尾;或者 不指向 。
最后一步是竞赛图公理唯一被使用之处:一对顶点若不是 ,就必然是 。在一般有向图中,这两点可能不相邻,空位便无法接上。取最大指标只是找出转换位置的方便办法,并非唯一办法;在五顶点例子中,第一个入邻点 也可以,因为 。由于只改动了一对相邻顶点,而两条新箭头都已检查,这一步便完成。
如果查询任意一对顶点间的方向需常数时间,每次插入至多检查当前路径长度,总共需要 次方向检查。哈密顿路径也不表示前面的每个顶点都胜过后面的每个顶点;定义只要求相邻箭头向前。
常见错误
(按出度排序代替插入)
把顶点按出度从大到小排列,若相同出度任意排序,所得未必是有向路径。在 上取 、、、、、,出度为 ,顺序 的出度不增;但 与 之间的箭头是 ,第一步就向后。插入证明从不依赖出度。
常见错误
(把路径升格为哈密顿圈)
定理保证的是路径而非圈。在传递竞赛图 、、 中,排列 是哈密顿路径,但 的出度为零,无法离开,所以没有有向圈经过它。传递竞赛图根本没有任何有向圈。
例题 5.2.3
(插入后的路径仍可能含反向比较)
设 、、。先取路径 ,因为 ,将 加在末尾,得到哈密顿路径 。然而 相对于排列向后,并闭合为有向三角形。所以路径排列未必把所有比较排成一致名次。
例题 5.2.4
(把顶点插入路径中间)
取五个顶点 。在 之间,箭头为 、、、、 和 ,因此 是一条有向路径。涉及 的四次比较为 、、 和 。这十条箭头确定了每一对顶点之间的方向。
沿已有路径检查哪些顶点指向 :它们是 和 。其中最后一个是第三个位置的 ,其后继为 。由于 ,把 插入这个空位,得到路径 ;相邻箭头依次是 、、 和 。特别地, 不妨碍构造,因为非相邻顶点间的箭头无须向前。指向 的顶点不一定连成一段,所以寻找最后一个时要检查相关位置。
什么情况下比较能排成一致名次?
定义 5.2.5
(传递竞赛图与有向三角形)
若不同顶点满足 且 时总有 ,称竞赛图传递。有向三角形是三个不同顶点组成的有向圈。
下面的定理说明,等价地,传递竞赛图的顶点可以排成一个顺序,使所有箭头都从前指向后。
定理 5.2.6
(传递性的三个等价条件)
对于有限竞赛图,下列条件等价:(1)它是传递的;(2)它没有有向三角形;(3)存在一个顶点排列,使所有箭头向前。
证明
(从三点的条件得到整体顺序)
传递图不可能含 ,因为前两条箭头要求 。现在假设没有有向三角形。取一条哈密顿路径 ,对 归纳证明 时都有 。相邻情形由路径定义成立。距离更大时,归纳假设给出 ,路径给出 。若 ,便出现有向三角形,因此只能有 。最后,若所有箭头都向前,则 和 分别迫使 在 前、 在 前,故 ,即传递性成立。
传递竞赛图的这种顺序是唯一的:任意两顶点之间的箭头都决定了它们的先后。 个顶点沿此顺序的出度为 。更一般地,任何竞赛图的出度之和都等于 ,因为每对顶点恰好贡献一条出箭头。但这个和不能判定传递性:同样顶点数的竞赛图都具有相同的和。
反例模式
路径不是整体排名
在三顶点有向圈中, 是哈密顿路径,但 ;三个顶点的出度都是一。因此仅按出度排序,未必能使所有箭头向前;有哈密顿路径也不意味着没有有向圈。
缩短有向圈
不存在有向三角形也会排除更长的有向圈。下面的构造说明竞赛图的特殊条件为何重要:圈上任意两个不相邻的顶点之间仍有箭头,可以用它作为捷径。
引理 5.2.7
(有向圈的顶点中含有向三角形)
在竞赛图中,每个 的有向圈 都含有三个顶点构成有向三角形。
证明
(沿圈取捷径)
设 是有向圈,其中 。若 ,它已经是三角形。若 ,考察 与 间的箭头:若为 ,前三个顶点构成有向三角形 ;否则箭头是 ,可以省去 ,得到较短的有向圈 ,其顶点仍互不相同。反复执行,直到出现三角形;每次取捷径都使圈的长度减少,所以过程终止。
这比仅说竞赛图中某处存在三角形更强:三角形的顶点可以从原圈中选取。但它并不是说原圈上任取三个顶点都形成有向三角形。一般有向图未必有这条捷径,故不能照搬此论证。
出度大的顶点与短路径
定义 5.2.8
(王点)
若顶点 能通过至多两条有向边到达每个顶点,就称 为王点。其中 通过长度零的路径到达自己。王点不一定直接胜过所有对手。
定理 5.2.9
(最大出度顶点是王点)
在非空有限竞赛图中,任意最大出度顶点都能通过至多两条有向边到达每个其他顶点。
证明
(比较出邻点)
取最大出度顶点 。若 ,结论显然。否则 。假设不存在 使 。 的每个出邻点 都不同于 ,因而必须满足 。另外还有 ,所以 至少有 个出邻点,违反 的出度最大。因此必有这样的 ,所需路径是 。
反例模式
离开竞赛图,最大出度并不足够
有人可能以为:在任何有向图中,最大出度顶点都能在两步内到达每个顶点。取顶点 ,只有箭头 、 和 。此时 是最大出度,但没有箭头指向 ,所以 根本无法到达 。证明在“否则 ”这一步失效:这里 与 之间两个方向都没有箭头。定理需要竞赛图公理:每对顶点恰好以一个方向相连。
例题 5.2.10
(王点不一定保持全胜)
在 中,三个出度都是一,且每个顶点都是王点。例如 沿 到达 ,尽管直接比赛中 胜 。王点描述可达性,并非不败选手。
例题 5.2.11
(出度较小的王点)
在 上取箭头 、、、、 和 。 的出度依次为 。尽管如此, 是王点:它直接到达 ,并分别沿 和 到达 。因此定理给出了寻找王点的可靠方法,但逆命题不成立:王点不一定具有最大出度。
练习
快速检查
(顶点集为 ,箭头为 、、、、、。找一条哈密顿路径、一个有向三角形和一个王点。)
让路径从胜过 的顶点开始。
解答 · 答案
是哈密顿路径; 是有向三角形。 是王点:它直接到达 ,并通过 (或 )到达 。
快速检查
(四顶点竞赛图的出度为 。它一定传递吗?解释原因。)
先删去出度为三的顶点。
解答 · 答案
一定。出度为三的顶点胜过其他所有顶点。删除它后,其余三个顶点原来的出度 不变,因为与已删顶点之间的边指向它们。出度为二的顶点胜过剩下两个,最后一条边决定其余二者的顺序,因此按出度 排列时所有箭头向前。
快速检查
(举出一个三顶点竞赛图,它有哈密顿路径但没有出度为二的顶点。它有王点吗?)
出度之和必须为三。
解答 · 答案
取 。 是哈密顿路径,每个顶点出度都是一。每个顶点都是王点:对胜过它的顶点,可以经过第三个顶点到达。
快速检查
(若竞赛图有某长度的有向圈,它必有顶点取自该圈的有向三角形吗?用捷径证明,不要假设给出的圈本身有三条边。)
考察圈上第一与第三个顶点之间的箭头。
解答 · 答案
必有。若圈长至少为四,圈上第一与第三顶点之间的箭头或者与前两条边组成三角形,或者允许我们省去第二个顶点而得到较短的有向圈。重复此步骤终会得到三角形,而且只使用原圈上的顶点。
快速检查
(若非空竞赛图中的一个顶点胜过所有其他顶点,证明它是唯一的王点。)
想一想:其他顶点究竟能否到达它?
解答 · 答案
设 胜过其他所有顶点。它至多经过一条边就能到达所有顶点,因此是王点。其他顶点都不能沿有向路径到达 :这样的路径最后一条边必须指向 ,但与 相接的边都从 指出。所以 是唯一的王点。