由此定理说明,在循环赛中得胜最多的参赛者必定是王。但反之不真。事实上,王未必 唯一。例如,下图(a)中,顶点a,b,c都是王。在图(b)中,顶点v1v2都是王,但v1的出度为 2,而v2的出度为3 定理853竞赛图中的顶点v是唯一的王当且仅当v的出度为v-1。 证明:必要性:若v是唯一的王,且其出度小于v-1,则v有入邻点,设v的所有入邻点 导出的子竞赛图为G1,则由上一定理,G1有自己的王。设u是G1的一个王。因u到v有 弧,故u也是G的王。这与v是唯一的王矛盾。 充分性:设v的出度为v-1,则ν显然是王。若G还有另一王v,则由王的定义,要么存 在弧yv,要么存在长为2的有向路yv。无论如何,v的入度至少为1,从而其出度至多 为v-2,这与前提条件矛盾。证毕。 这个定理说明,如果没有全胜的参赛者,则竞赛图至少有两个王。 定理854竞赛图K中必存在有向 Hamilton路(含有所有顶点的有向路)。 证明:因x(K)=v.故由定理821,竞赛图R中有长为x(K)-1=v-1的有向路,此即为K 的一条有向 Hamilton路 证毕。 定理855v≥3的强连通竞赛图的每个顶点都含在长为k的有向圈上(k=3,4,…,v)。 证明:设G是一个强连通竞赛图,u是G的任一个顶点。下面证明u在G的长为3的有向 圈上。 取S=N(),T=N(u),则S与T非空(因G是强连通的,既有从u出发的弧,又 有指向u的弧)。用(S,T表示尾在S而头在T中的弧的集合。由于G是强连通竞赛图,故存 在弧(v,w)∈(S,T),于是u在三角形n上,它是一个3阶有向圈 T=N(u) 下面对k用归纳法。 假设有长为3,4,…,m的有向圈含有u,(m<v)。下证必有长为m+1的有向圈含有u 设C=v0VV2…vm是含有a的一个长为m的有向圈。7 由此定理说明，在循环赛中得胜最多的参赛者必定是王。但反之不真。事实上，王未必 唯一。例如，下图(a)中，顶点 a, b, c 都是王。在图(b)中，顶点 1 2 v v, 都是王，但 v1 的出度为 2，而 v2 的出度为 3。 定理 8.5.3 竞赛图中的顶点 v 是唯一的王当且仅当 v 的出度为ν −1。 证明：必要性：若 v 是唯一的王，且其出度小于ν −1，则 v 有入邻点，设 v 的所有入邻点 导出的子竞赛图为 G1，则由上一定理，G1 有自己的王。设 u 是 G1的一个王。 因 u 到 v 有 弧，故 u 也是 G 的王。这与 v 是唯一的王矛盾。 充分性：设 v 的出度为ν −1，则 v 显然是王。若 G 还有另一王 v′，则由王的定义，要么存 在弧 v′v，要么存在长为 2 的有向路 v′wv。无论如何，v 的入度至少为 1，从而其出度至多 为ν − 2 ，这与前提条件矛盾。证毕。 这个定理说明，如果没有全胜的参赛者，则竞赛图至少有两个王。 定理 8.5.4 竞赛图 Kν G 中必存在有向 Hamilton 路（含有所有顶点的有向路）。 证明：因χ( ) Kν = ν . 故由定理 8.2.1，竞赛图 Kν G 中有长为χ( )1 1 Kν − =ν− 的有向路，此即为 Kν G 的一条有向 Hamilton 路。 证毕。 定理 8.5.5 ν ≥ 3 的强连通竞赛图的每个顶点都含在长为 k 的有向圈上( 3,4, , ) k = " ν 。 证明：设G G 是一个强连通竞赛图，u 是 G 的任一个顶点。下面证明 u 在G G 的长为 3 的有向 圈上。 取 S NuT Nu ( ), ( ) + − = = ，则 S 与 T 非空(因G G 是强连通的，既有从 u 出发的弧，又 有指向 u 的弧)。用(S, T)表示尾在 S 而头在 T 中的弧的集合。由于G G 是强连通竞赛图，故存 在弧(, ) (, ) vw ST ∈ ，于是 u 在三角形 uvw 上，它是一个 3 阶有向圈。 下面对 k 用归纳法。 假设有长为3, 4, , " m 的有向圈含有u m ,( ) <ν 。下证必有长为 m+1 的有向圈含有 u。 设C vvv v = 012" m 是含有 u 的一个长为 m 的有向圈。 u v w S=N+ (u) T=N − (u) a b c (a) (b) v1 v2 v3 v4 v5