(1)若在V(G)-V(C)中存在顶点v满足:v是尾 在C上的一条弧的头,又是头在C上的一条弧的尾,则 在C上有顶点v,V1,使得vv∈E(G)且w∈E(G) (注意G是竞赛图,任二顶点间都有弧)。此时u在长为m+1的圈vv1…vv12…vm上。 (2)否则,用S表示V(G)-(C)中从圈C有弧指向的顶点之集,T表示V(G)-V(C) 中有弧指向C的顶点之集。由于m<v,故SUT≠Φ,又因G是强连通竞赛图,从而 S≠Φ,T≠Φ,(S,T)≠Φ。 (若S=Φ,则C到T无有向路;同理T≠Φ;若(S,T)=Φ,则S到T无有向路)。 ①若S∩T≠Φ,则S∩T中的顶点符合(1)中顶点v的要求 ②若S∩T=d,则存在v∈S,w∈T,使得w∈E(G)(如图) 注意w与C上每个顶点间的弧都指向C(否则将导致情况(1))。同理ν与C上所有顶点间 的弧都指向v。因此总可适当选择i使得u在圈vov1…",v*2…vn上,这是一个长为m+1 的圈。证毕。 推论强连通竞赛图是有向 Hamilton图。 注:一个含有v个顶点的图(或有向图)有长从3直到v的圈(或有向圈),则称这个图(或 有向图)具有泛圈性。定理8.55表明强连通竞赛图具有泛圈性。实际上定理8.55证明了强 连通竞赛图的一个更强的性质:如果竞赛图G是强连通的,则G中过每个顶点都有长从3 直到v的有向圈。判断一般图(或有向图)是否具有泛圈性,至今仍是一个悬而未决的难题 下面讨论竞赛名次的排列问题 3个顶点的竞赛图有如下两种情况(不考虑顶点的标号)。对于情况(1),3个队的名次 排列显然应是{1,2,3};对于情况(2),3个队名次相同,因为他们各胜一场 (1) 4个顶点的竞赛图共有4种形式,下面分别进行讨论8 (1) 若在VG VC () () − G 中存在顶点 v 满足：v 是尾 在 C 上的一条弧的头，又是头在 C 上的一条弧的尾，则 在 C 上有顶点 1 1 , , () () ii i i v v v v E G vv E G + + ∈ ∈ G G 使得 且 ， (注意 G 是竞赛图，任二顶点间都有弧)。此时 u 在长为 m+1 的圈 01 1 2 ii i m v v v vv v v " " + + 上。 (2) 否则，用 S 表示VG VC () () − 中从圈 C 有弧指向的顶点之集，T 表示VG VC () () − 中有弧指向 C 的顶点之集。由于m <ν ，故 S T ∪ ≠ Φ, 又因G G 是强连通竞赛图，从而 S T ST ≠Φ ≠Φ ≠Φ , ,( , ) 。 (若 S = Φ ，则 C 到 T 无有向路；同理T ≠ Φ ；若(, ) S T = Φ ，则 S 到 T 无有向路)。 ① 若 ST ST ∩ ∩ ≠ Φ，则 中的顶点符合 (1)中顶点 v 的要求。 ② 若 S T ∩ = Φ ，则存在v Sw T ∈ ∈ , ，使得vw E G ∈ ( ) (如图)。 注意 w 与 C 上每个顶点间的弧都指向 C (否则将导致情况(1))。同理 v 与 C 上所有顶点间 的弧都指向 v。 因此总可适当选择 i 使得 u 在圈 01 2 ii m v v v vwv v " "+ 上，这是一个长为 m+1 的圈。证毕。 推论 强连通竞赛图是有向 Hamilton 图。 注：一个含有ν 个顶点的图（或有向图）有长从 3 直到ν 的圈（或有向圈），则称这个图（或 有向图）具有泛圈性。定理 8.5.5 表明强连通竞赛图具有泛圈性。实际上定理 8.5.5 证明了强 连通竞赛图的一个更强的性质：如果竞赛图 G 是强连通的，则 G 中过每个顶点都有长从 3 直到ν 的有向圈。判断一般图（或有向图）是否具有泛圈性，至今仍是一个悬而未决的难题。 下面讨论竞赛名次的排列问题。 3 个顶点的竞赛图有如下两种情况（不考虑顶点的标号）。对于情况(1)，3 个队的名次 排列显然应是{1，2，3}；对于情况(2)，3 个队名次相同，因为他们各胜一场. 4 个顶点的竞赛图共有 4 种形式，下面分别进行讨论。 … … v0 vm vi vi+1 v … … v0 vm vi vi+1 v w S T vi+2 v1 1 3 (1) 2 2 1 3 (2)