证明:给G添加一个新顶点w,并将w与G的每个顶点用两条方向相反的弧相连,由此构 成一个新的有向图G。显然G是强连通图,任取G中两个不相邻顶点l,v,则u,v是G的 不相邻顶点,由条件知, dG(l)+dG(v)=d()+d(v)+4≥(2-3)+4=2v+1=2(V+1)-1 因G′是v+1阶强连通有向图,故由定理845,G包含一个 Hamilton有向圈。从该圈删去w 便得到G的一条 Hamilton有向路 类似于推论1~推论3,有如下推论: 推论4设G是非平凡简单有向图,如果对任二满足(l,)∈A(G)的顶点,v都有 d(u)+d-(v)≥v-1,(v是G的顶点数, 则G含有 Hamilton有向路。 推论5设G是简单有向图,且对每个顶点v都有d(v)≥v-1,则G含有 Hamilton有向路 推论6设G是简单有向图,且对每个顶点v都有d(2~~1 d-(v)≥ 2,则G含有 Hamilton有向路。 §8.5竞赛图 在球队的循环赛中,任意两队之间都会比赛一场,每场比赛都要决出胜负,不许出现平 局。循环赛的图论模型是竞赛图:以参赛队作为顶点,若队u胜了队ν,则由u向v连一条 弧,获得一个完全图的定向图。竞赛图的确切定义如下。 定义8.5.1完全图的每条边确定一个方向后所得的有向图称为竞赛图。 定理85.1竞赛图中必有一个顶点v,它到其它任何顶点都有长不超过2的有向路。 证明:因竞赛图的底图的任何独立集只含一个顶点,故由定理822,结论成立。证毕 注:定理85,1中所述的顶点v称为竞赛图的“王”。直观地讲,若ν是王,则所有其它 参赛者要么败给了v,要么败给了败给过v的参赛者。 竞赛图中王总是存在的。事实上,有如下定理。 定理852竞赛图中出度最大的顶点必为王 证明:设是竞赛图中的出度最大的顶点。如果ν的出度为v-1,则ν显然是王。如果v 的出度为k<v-1,设它的出邻点为v1v2…,vk,而v的入邻点为vk1,vk+2,…,V 对每个v(k+1sj≤V-1),V1,V2…,"k不会全是v,的出邻点(否则,v,的出度为k+1, 这与最大出度为k矛盾)。因此v,V2…,vk至少有一点是v,的入邻点。可见v到每个v,都 有长至多为2的有向路,从而v是王
6 证明：给 G 添加一个新顶点 w，并将 w 与 G 的每个顶点用两条方向相反的弧相连，由此构 成一个新的有向图 G′。显然 G′是强连通图，任取 G′中两个不相邻顶点 u, v，则 u, v 是 G 的 不相邻顶点，由条件知， ( ) ( ) ( ) ( ) 4 (2 3) 4 2 1 2( 1) 1 G G GG du d v du dv ′ ′ + = + + ≥ − + = += + − ν ν ν . 因 G′是ν +1阶强连通有向图，故由定理 8.4.5，G′包含一个 Hamilton 有向圈。从该圈删去 w 便得到 G 的一条 Hamilton 有向路。 类似于推论 1~推论 3，有如下推论： 推论 4 设 G 是非平凡简单有向图，如果对任二满足(,) ( ) uv AG ∉ 的顶点 u, v 都有 du dv () () 1 ν + − + ≥− ，(ν 是 G 的顶点数)， 则 G 含有 Hamilton 有向路。 推论 5 设 G 是简单有向图，且对每个顶点 v 都有d v() 1 ≥ − ν ，则 G 含有 Hamilton 有向路。 推论 6 设 G 是简单有向图，且对每个顶点 v 都有 1 1 () , () 2 2 dv dv + − ν − ν − ≥ ≥ ，则 G 含有 Hamilton 有向路。 §8.5 竞赛图 在球队的循环赛中，任意两队之间都会比赛一场，每场比赛都要决出胜负，不许出现平 局。循环赛的图论模型是竞赛图：以参赛队作为顶点，若队 u 胜了队 v，则由 u 向 v 连一条 弧，获得一个完全图的定向图。竞赛图的确切定义如下。 定义 8.5.1 完全图的每条边确定一个方向后所得的有向图称为竞赛图。 定理 8.5.1 竞赛图中必有一个顶点 v，它到其它任何顶点都有长不超过 2 的有向路。 证明：因竞赛图的底图的任何独立集只含一个顶点，故由定理 8.2.2，结论成立。证毕。 注：定理 8.5.1 中所述的顶点 v 称为竞赛图的“王”。直观地讲，若 v 是王，则所有其它 参赛者要么败给了 v，要么败给了败给过 v 的参赛者。 竞赛图中王总是存在的。事实上，有如下定理。 定理 8.5.2 竞赛图中出度最大的顶点必为王。 证明：设 v 是竞赛图中的出度最大的顶点。如果 v 的出度为ν −1，则 v 显然是王。如果 v 的出度为 k <ν −1，设它的出邻点为 1 2 ,,, k vv v … ，而 v 的入邻点为 12 1 , ,, k k vv v + + − … ν ，则 对每个 j v ( 1 1) k j +≤ ≤ − ν ， 1 2 ,,, k vv v … 不会全是 j v 的出邻点（否则， j v 的出度为k + 1， 这与最大出度为 k 矛盾）。因此 1 2 ,,, k vv v … 至少有一点是 j v 的入邻点。可见 v 到每个 j v 都 有长至多为 2 的有向路，从而 v 是王。 证毕
由此定理说明,在循环赛中得胜最多的参赛者必定是王。但反之不真。事实上,王未必 唯一。例如,下图(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