定理842非平凡弱连通有向图G是Euer有向图的充分必要条件是G可分解为有向圈的并 即:G=∪C,其中C是G的有向圈,且E(C)∩E(C)=,(1≤/≤k),k是一个 正整数。 定理843非平凡弱连通有向图G有Euer有向迹的充分必要条件是G中存在两个顶点u和 P满足d'(u)=d(u)+1,d"()=d()-1,而其它顶点都有d(v)=d(v)。 定理844设G是弱连通有向图,如果G中存在两个顶点u和w满足d(u)=d(u)+k, d'()=d(w)-k,(k是一个正整数,而其它顶点都有d(v)=d(v),则G中从u到w 有k条弧不交的有向迹。 上述定理的证明与无向Euer图中相关定理的证明类似。 定理845设G是强连通简单有向图,如果对任二互不相邻顶点u,v都有 d()+d(v)≥2v-1,(v是G的顶点数), 则G是 Hamilton有向图 证明略。 推论1设G是非平凡简单有向图,如果对任二满足(u,v)gA(G)的顶点uv都有 d'(u)+d(v)≥v,(v是G的顶点数) 则G是 Hamilton有向图。 证明:先证G是强连通的 任取G中两点v1,2,我们来证明G中必有n-2有向路。事实上,如果(v,n2)是G中的 一条弧,则结论显然;如果(v,n2)不是G中一条弧,则由条件d(V1)+d(v2)≥v,至少 存在一个异于v,n2的顶点,使(V,),(w,v2)是两条弧,从而vv2是一条v1-2有向路。 同理可知,G中也存在一条v-V1有向路。由v,n2的任意性,G是强连通的。 设u和是任意两个不相邻顶点,由条件d()+d(v)≥v,且d(v)+d()≥v 因此d(a)+d()≥2v,由定理84.5,G是 Hamilton有向图。证毕。 推论2设G是强连通简单有向图,且对每个顶点v都有d(v)≥v,则G是 Hamilton有向图 推论3设G是简单有向图,且对每个顶点v,都有d+(v)≥,d-(v)≥一,则G是 Hamilton 有向图。 定理846设G是非平凡简单有向图,如果对任二互不相邻顶点u,v都有 d(a)+d(v)≥2v-3,(v是G的顶点数, 则G含有 Hamilton有向路5 定理8.4.2 非平凡弱连通有向图G是Euler有向图的充分必要条件是G可分解为有向圈的并， 即： 1 k i i G C= = ∪ ，其中 Ci 是 G 的有向圈，且 ( ) ( ) , (1 , ) E C EC i j k i j ∩ = ∅≤ ≤ ，k 是一个 正整数。 定理 8.4.3 非平凡弱连通有向图 G 有 Euler 有向迹的充分必要条件是 G 中存在两个顶点 u 和 w 满足du du () () + − = +1，dw dw () () + − = −1，而其它顶点都有dv dv () () + − = 。 定理 8.4.4 设 G 是弱连通有向图，如果 G 中存在两个顶点 u 和 w 满足du du () () + − = +k， dw dw () () + − = −k，(k 是一个正整数)，而其它顶点都有dv dv () () + − = ，则 G 中从 u 到 w 有 k 条弧不交的有向迹。 上述定理的证明与无向 Euler 图中相关定理的证明类似。 定理 8.4.5 设 G 是强连通简单有向图，如果对任二互不相邻顶点 u, v 都有 du dv () () 2 1 + ≥− ν ，(ν 是 G 的顶点数)， 则 G 是 Hamilton 有向图。 证明略。 推论 1 设 G 是非平凡简单有向图，如果对任二满足(,) ( ) uv AG ∉ 的顶点 u, v 都有 du dv () () ν + − + ≥ ，(ν 是 G 的顶点数)， 则 G 是 Hamilton 有向图。 证明：先证 G 是强连通的： 任取 G 中两点 v1, v2，我们来证明 G 中必有 v1-v2有向路。事实上，如果(v1, v2)是 G 中的 一条弧，则结论显然；如果(v1, v2)不是 G 中一条弧，则由条件 1 2 dv dv () () ν + − + ≥ ，至少 存在一个异于 v1, v2 的顶点 w，使 1 2 ( , ), ( , ) v w wv 是两条弧，从而 1 2 v wv 是一条 v1-v2 有向路。 同理可知，G 中也存在一条 v2-v1 有向路。由 v1, v2 的任意性，G 是强连通的。 设 u 和 v 是任意两个不相邻顶点，由条件du dv () () ν + − + ≥ ，且dv du () () ν + − + ≥ ， 因此du dv () () 2 + ≥ ν ，由定理 8.4.5，G 是 Hamilton 有向图。证毕。 推论 2 设 G 是强连通简单有向图, 且对每个顶点 v 都有d v( ) ≥ν , 则 G 是 Hamilton 有向图。 推论 3 设 G 是简单有向图，且对每个顶点 v，都有 () , () 2 2 dv dv + − ν ν ≥ ≥ ，则 G 是 Hamilton 有向图。 定理 8.4.6 设 G 是非平凡简单有向图，如果对任二互不相邻顶点 u, v 都有 du dv () () 2 3 + ≥− ν ，(ν 是 G 的顶点数)， 则 G 含有 Hamilton 有向路