第八章有向图 §8.1有向图的基本概念 定义811每条边都具有一个方向的图称为有向图。严格的说,一个有向图G是一个有序二 元组((G),AG),其中集合(G)是非空的顶点集,集合A(G)是×V的一个子集(有序对, 元素可重复),它是带有方向的边的集合,称为弧集,A(G)中的元素称为弧或有向边 例811G=(,A),其中V={v1,V2V3,V4,v5},有序对集合 A={V,V2>,<"2,v3><V2v3><V3,v>,<n,V><V1,v5<v12v>,<",v5>。 这便定义出一个有向图。 注:(1)相应地,前面所说的边不带有方向的图称为无向图。 (2)一个无向图G可以对应若干个有向图,它称为所对应的有向图的基础图或底图。 (3)将有向图的顶点可用平面上的一个点来表示,弧可用平面上的有向线段来表示(直 的或曲的),这样画出的平面图形称为图(有向图)的图示。 (4)对一条弧e=<,1>,其第二分量顶点v(即箭头指向的顶点)称为它的首顶点,另 顶点称为它的尾顶点。一条首尾顶点相同的弧称为环弧(如下图中es),两条具有相同首顶 点和相同尾顶点的弧称为并行弧(如下图中e2和e3)。既无环弧又无并行弧的有向图称为简 单有向图(或严格有向图)。 例如,例8.1.1中有向图的一个图示为 定义81设v是有向图G的一个顶点。v的入度d=(v)是指指向v的弧的数目;v的出度d(G) 是指从v出发的弧的数目。出度和入度可简写为d'()和d(v)。 最小出度6(G)=mg( 最小入度δ(G)=min{d()} 最大出度△(G)=may{ad"(v) 最大入度△(G)=ma{d(v)} 顶点v的出邻集N()={u(,n)∈AG) 顶点v的入邻集N(v)={1(4,)∈AG)} 定理811对于有向图G,∑d()=26且∑d(v) lE(G) EV(G 证明与无向图情况类似
1 第八章 有向图 §8.1 有向图的基本概念 定义 8.1.1 每条边都具有一个方向的图称为有向图。严格的说，一个有向图G G 是一个有序二 元组( ( ), ( )) V G AG JG JG ，其中集合V G( ) JG 是非空的顶点集，集合 A( ) G JG 是V ×V 的一个子集（有序对， 元素可重复），它是带有方向的边的集合，称为弧集， A( ) G JG 中的元素称为弧或有向边。 例 8.1.1 G VA = (,) ，其中 { , , , , } 1 2 3 4 5 V = v v v v v ，有序对集合 12 23 23 34 35 15 15 55 A vv vv vv vv vv vv vv vv = < >< >< >< >< >< >< >< > {, , , , , , , , , , , , , , , }。 这便定义出一个有向图。 注：（1）相应地，前面所说的边不带有方向的图称为无向图。 （2）一个无向图 G 可以对应若干个有向图，它称为所对应的有向图的基础图或底图。 （3）将有向图的顶点可用平面上的一个点来表示，弧可用平面上的有向线段来表示（直 的或曲的），这样画出的平面图形称为图（有向图）的图示。 （4）对一条弧 e=<u, v>，其第二分量顶点 v（即箭头指向的顶点）称为它的首顶点，另一 顶点称为它的尾顶点。一条首尾顶点相同的弧称为环弧（如下图中 e8），两条具有相同首顶 点和相同尾顶点的弧称为并行弧（如下图中 e2和 e3）。既无环弧又无并行弧的有向图称为简 单有向图（或严格有向图）。 例如，例 8.1.1 中有向图的一个图示为 定义8.1.2 设v是有向图G JG 的一个顶点。v的入度 ( ) G d v − JJG 是指指向v的弧的数目；v的出度 ( ) G d G+ JJG JG 是指从 v 出发的弧的数目。出度和入度可简写为d v( ) + 和d v( ) − 。 最小出度 ( ) ( ) min{ ( )} vVG G dv + + ∈ δ = JJG JG 最小入度 ( ) ( ) min { ( )} vVG G dv − − ∈ δ = JJG JG 最大出度 ( ) ( ) max{ ( )} vVG G dv + + ∈ Δ = JJG JG 最大入度 ( ) ( ) max{ ( )} vVG G dv − − ∈ Δ = JJG JG 顶点 v 的出邻集 ( ) { | ( , ) ( )} G N v u vu AG + JJG = ∈ JG 顶点 v 的入邻集 ( ) { | ( , ) ( )} G N v u uv AG − JJG = ∈ JG 定理 8.1.1 对于有向图 G， ( ) 2ε ( ) ∑ = v∈V G d v 且 ∑ = ∈ + ( ) ( ) v V G d v _ ( ) ( ) vVG d v ε ∈ ∑ = 。 证明与无向图情况类似。 v4 e1 e2 e3 e4 e5 e6 e7 v1 v2 v3 v5 e8
§8.2有向路与有向圈 定义8.21有向图的一个有向途径是指一个有限非空序列w=va1"1…a4v4,它的各项交替地 是顶点和弧,使得a=(1,v)(=1,2,…,k)。弧不重复的有向途径称为有向迹;顶点不重复 的有向途径称为有向路:首尾相接的有向路称为有向圈。 注:有向图中有向路的长与其底图中路的长之间没有多大关系。例如: 但却与底图的色数有关 定理8,1(Roy,1967;Gaai,1968)以图G为底图的有向图G中必有长为x(G)-1的有向路 证明:设A是使有向图G-A不含有向圈的最小弧子集。设G-A中最长有向路的长为k。 按如下方式将颜色1,2,…,k+1分配给G-A的顶点: 对任何顶点v∈v(G-A),如果G-A中从v出发的最长有向路长为i,则给v染色计1 用V表示染有第i种色的顶点的集合。下证(1,2…,Wk+1)是G的正常k+1顶点染色。为此, 先证明关于这种染色的两个结论 (1)G-A中任一有向路的起点与终点异色 事实上,设P(l,)是G-A的一条有向路,l≠v。无妨设v∈V。由染色规则可知,存 在有向路 Q=vv1V2…vsG-A 其中v=v。又因G-中没有有向圈,故v1,"2…,ngP(u,)。因此P(u,v)儿UQ是起点为u且 长至少为计+1的有向路。于是由染色规则,ugV。 (2)G的任一条边两端点异色 事实上,设e=∈E(G)。若w∈A',则由A'的最小性,(G-A')+含有有向圈C。C 是G-A的一条有向路,故由(1),u与v异色:若∈AG-A),则v是G-A的 条有向路。由(1),u与v也异色。 可见(1,V2…,Wk)是G的正常k+1顶点染色。因而x(G)≤k+1,即k≥x(G)-1。证毕。 定理822若G是无环有向图,则其底图G中必有一个独立集S,使得对V(G)-S中的每个 顶点v,存在v∈S,在G中从v到v有长不超过2的有向路。 证明:对顶点数v作归纳。 v=1时定理显然成立 假设对顶点数少于v的所有有向图G,结论成立。考虑顶点数为v的有向图G
2 §8.2 有向路与有向圈 定义 8.2.1 有向图的一个有向途径是指一个有限非空序列 w vav av = 0 11" k k ，它的各项交替地 是顶点和弧，使得 1 ( , ),( 1,2, , ) i ii a vv i k = = − " 。弧不重复的有向途径称为有向迹；顶点不重复 的有向途径称为有向路；首尾相接的有向路称为有向圈。 注：有向图中有向路的长与其底图中路的长之间没有多大关系。例如： 但却与底图的色数有关。 定理 8.2.1 (Roy,1967;Gallai,1968) 以图 G 为底图的有向图G JG 中必有长为χ()1 G − 的有向路。 证明：设 A′ 是使有向图G A − ′ JG 不含有向圈的最小弧子集。设G A − ′ JG 中最长有向路的长为 k。 按如下方式将颜色 1, 2, ···, k+1 分配给G A − ′ JG 的顶点： 对任何顶点v VG A ∈ − ( )′ JG ，如果G A − ′ JG 中从 v 出发的最长有向路长为 i，则给 v 染色 i+1。 用 Vi 表示染有第 i 种色的顶点的集合。下证(V1,V2,···,Vk+1)是 G 的正常 k+1 顶点染色。为此， 先证明关于这种染色的两个结论。 （1）G A − ′ JG 中任一有向路的起点与终点异色 事实上，设 P(u,v)是G A − ′ JG 的一条有向路，u≠v。无妨设 i 1 v V ∈ + 。由染色规则可知，存 在有向路 Q vvv v G A 012 i = ⊆ − ′ JG " 。 其中 v0=v。又因G A − ′ JG 中没有有向圈，故 1 2 , , , (,) i v v v Puv " ∉ 。因此 Puv Q (,) ∪ 是起点为 u 且 长至少为 i＋1 的有向路。于是由染色规则， i u V ∉ 。 （2）G 的任一条边两端点异色。 事实上，设e uv E G = ∈ ( ) 。若uv A ∈ ′ ，则由 A′ 的最小性，( G A − ′ JG )+uv 含有有向圈 C。C - uv 是G A − ′ JG 的一条有向路，故由（1），u 与 v 异色；若uv A G A ∈ − ( )′ JG ，则 uv 是G A − ′ JG 的一 条有向路。由（1），u 与 v 也异色。 可见(V1,V2,···,Vk+1)是 G 的正常 k+1 顶点染色。因而χ() 1 G k ≤ + ，即k G ≥χ − ()1。证毕。 定理 8.2.2 若G G 是无环有向图，则其底图 G 中必有一个独立集 S，使得对VG S ( ) − 中的每个 顶点 v，存在 0 v S ∈ ，在G G 中从 0 v 到v 有长不超过 2 的有向路。 证明：对顶点数 ν 作归纳。 ν =1 时定理显然成立。 假设对顶点数少于 ν 的所有有向图G G ，结论成立。考虑顶点数为 ν 的有向图G G
任取v∈v(G),令G=G-({vUN(v)。由归纳假设,存在G的一个独立集S,对 r(G)-S"中任何顶点,可从S中的某顶点出发,经过长度≤2的有向路到达它。 (1)若存在v∈S,使vv∈A(G),则N(v)中每个顶点可从v出发,经过长度≤2的有 向路到达(G中其它点都在G中,本来就长2路可达) (2)否则,对Vv∈S",wvAO),而且因N(v)∩S'=Φ 故vgA(G),因此在底图G中v与S中的点不相邻 此时S=S∪{v}满足定理的要求 N"(y) §8.3有向图的连通性 定义8.3.1设G是一个有向图 (1)若G的底图G是连通图,则称G是弱连通的。 (2)若对G的任二顶点u,v,要么存在有向路P(u,v),要么存在有向路P(v,u),则称G是单 连通的。 (3)若对G的任二顶点,v,既存在有向路P(u,v),又存在有向路P(v,l),则称G是强连通 的(或称双向连通的)。 注:易见,强连通→单连通→弱连通。 例 不连通 弱连通 单连通 强连通 定理831G是强连通有向图的充要条件是G的所有顶点在一个有向闭途径上。 证明:必要性:设G是强连通有向图,(G)={v12n2…,"},则存在有向路P(v1,"2) P("2n),…,P1(-,,),P(,n),于是UP即为含所有顶点的有向闭途径。 充分性:设G的顶点共处于一个有向闭途径C上,则对v,v∈V(G),在C上必有u到v 的一段有向路P(,v),也有v到u的一段有向路P(v,u),故G是强连通的。证毕 定理832无向图G可定向成强连通图的充分必要条件为:G中无割边(即G是2边连通图) 证明:必要性:用反证法。若G中有割边,则无论如何对G的各边定向,都无法使割边两 端的点在所形成的有向图中双向连通。这与G可定向成为强连通有向图矛盾。 充分性:设G无割边,则G中存在圈。取其一个圈C,记G1=C。给G1定向为顺时针方 向。若G1不是生成子图,则存在v∈(G)-(G1),由第二章 Menger定理,存在两条无
3 任取 v VG ∈ ( ) G , 令 G G v Nv ({ } ( )) + ′ = − G G ∪ 。由归纳假设，存在 G′ G 的一个独立集 S′ ，对 VG S ( )′ ′ − G 中任何顶点，可从 S′中的某顶点出发，经过长度 ≤ 2 的有向路到达它。 (1) 若存在 0 v S ∈ ′ ，使 0 vv AG ∈ ( ) G ，则 N v( ) + 中每个顶点可从 0 v 出发，经过长度 ≤ 2 的有 向路到达（G G 中其它点都在G′ G 中，本来就长 2 路可达）。 (2) 否则，对 0 ∀ v S ∈ ′ ， 0 vv AG ∉ ( ) G ，而且因 Nv S ( ) + ∩ ′ = Φ ， 故 0 vv A G ∉ ( ) G ，因此在底图 G 中v S 与 ′中的点不相邻。 此时 SS v = ′∪{ }满足定理的要求。 证毕。 §8.3 有向图的连通性 定义 8.3.1 设G G 是一个有向图， (1) 若G G 的底图 G 是连通图，则称G G 是弱连通的。 (2) 若对G G 的任二顶点 u, v，要么存在有向路 P(u, v)，要么存在有向路 P(v, u)，则称G G 是单 连通的。 (3) 若对G G 的任二顶点 u, v，既存在有向路 P(u, v)，又存在有向路 P(v, u)，则称G G 是强连通 的（或称双向连通的）。 注：易见，强连通⇒单连通⇒弱连通。 例： 定理 8.3.1 G G 是强连通有向图的充要条件是G G 的所有顶点在一个有向闭途径上。 证明：必要性：设 G G 是强连通有向图， 1 2 VG vv v {, , , } = ν G （ ） " ，则存在有向路 112 Pv v ( , ), 223 Pv v (,) , ", -1 1 Pv v ( , ), νν ν − 1 Pv v (,) ν ν ，于是 1 i i P ν − ∪ 即为含所有顶点的有向闭途径。 充分性：设G G 的顶点共处于一个有向闭途径 C 上，则对∀ ∈ uv VG , () G ，在 C 上必有 u 到 v 的一段有向路 1Puv (,) ，也有 v 到 u 的一段有向路 1P vu (, ) ，故 G 是强连通的。证毕。 定理 8.3.2 无向图 G 可定向成强连通图的充分必要条件为：G 中无割边(即 G 是 2 边连通图)。 证明：必要性：用反证法。若 G 中有割边，则无论如何对 G 的各边定向，都无法使割边两 端的点在所形成的有向图中双向连通。这与 G 可定向成为强连通有向图矛盾。 充分性：设 G 无割边，则 G 中存在圈。取其一个圈 C，记G C 1 = 。给G1定向为顺时针方 向。若G1不是生成子图，则存在 1 1 v VG VG ∈ () ( ) − ，由第二章 Menger 定理，存在两条无 不连通 弱连通 单连通 强连通 S′ v0 N + (v) v
公共边的路P,Q1,它们的一端是v1,另一端在G1上。给定向为指向v1,Q1定向为指向 G1,令G2=G1UPUQ,则G2是强连通的。 若G2仍不是生成子图,则存在v2∈(G)-1(G2),同理,存在无公共边的路P2,Q2 其一端在v2处,另一端在G2中。给P定向为指向v2,Q2定向为指向G2,令 G3=G2UP2UQ2,则G3是强连通的。如此反复,可得一个强连通子图序列G1,G2 顶点数严格递增。因|I(G)是有限数,故必在某一步得到Gn后终止,G是强连通的且是 G的生成子图。最后,把G中不在G,中的边任意定向,得到以G为底图的一个强连通有向 证毕 定理8.3.3G是单连通有向图的充要条件是G的所有顶点在一个有向途径上 证明:充分性是显然的 必要性:首先用归纳法证明:对G的任何至少含有2个顶点的顶点子集S,必有u∈S, 使得u到S中每个其它顶点在G中都有有向路。 当S只含2个顶点时,由于G单连通,结论显然成立 假设对任何含有k个顶点的子集,结论成立。下证对含有k+1个顶点的子集S,结论也 成立 事实上,任取v∈S,由归纳假设,S-{v中必有某点u,它到S-{v}中每个其它顶点都 有有向路。由于G单连通,在G中、ν之间必有有向路。如果u到v有有向路,则u符合 结论的要求;如果v到u有有向路,则ν符合结论的要求。归纳法完成 下面来证明定理必要性的结论。 取S=v(G),由上述结论,存在劭1∈S,使得u到S中每个其它顶点都有有向路。再 令S2V(G)-{an},由上述结论,存在l2∈S2,使得l2到S2中每个其它顶点都有有向路。 再令S=V(G)-{n,a2},由上述结论,存在l2∈S3,使得3到S3中每个其它顶点都有有向 路。以此类推,可得到含所有顶点的序列,顶点沿序列依次有有向路,这些有向路合成一条 含所有点的有向途径。证毕 §84 Euler有向图和 Hamilton有向图 定义841经过有向图G的所有弧恰一次的有向迹称为G的一条 Euler有向迹。经过有向图 G的所有弧恰一次的有向闭迹称为G的一条 Euler有向闭迹。存在 Euler有向迹的有向图称 为Euer有向图。经过有向图G的所有顶点恰一次的有向路称为G的一条 Hamilton有向路 经过有向图G的所有顶点恰一次的有向圈称为G的一个 Hamilton有向圈。存在 Hamilton有 向圈的有向图称为 Hamilton有向图 定理8..平凡弱连通有向图G是Euer有向图的充分必要条件是对任何v∈(G),都 有d(v)=d(v)
4 公共边的路 1 1 P Q, ，它们的一端是 1 v ，另一端在G1上。给 P1定向为指向 1 v ，Q1定向为指向 G1，令G G PQ 2 11 1 = ∪ ∪ ，则G2 是强连通的。 若G2 仍不是生成子图，则存在 2 2 v VG VG ∈ () ( ) − ，同理，存在无公共边的路 2 2 P Q, ， 其一端在 2 v 处，另一端在 G2 中。给 P2 定向为指向 2 v ， Q2 定向为指向 G2 ， 令 G G PQ 3 22 2 = ∪ ∪ ，则G3 是强连通的。如此反复，可得一个强连通子图序列 1 2 G G, ,"， 顶点数严格递增。因| ( )| V G 是有限数，故必在某一步得到Gn 后终止，Gn 是强连通的且是 G 的生成子图。最后，把 G 中不在Gn 中的边任意定向，得到以 G 为底图的一个强连通有向 图。 证毕。 定理 8.3.3 G G 是单连通有向图的充要条件是G G 的所有顶点在一个有向途径上。 证明：充分性是显然的。 必要性：首先用归纳法证明：对G G 的任何至少含有 2 个顶点的顶点子集 S，必有u S ∈ ， 使得 u 到 S 中每个其它顶点在G G 中都有有向路。 当 S 只含 2 个顶点时，由于G G 单连通，结论显然成立。 假设对任何含有 k 个顶点的子集，结论成立。下证对含有 k+1 个顶点的子集 S，结论也 成立。 事实上，任取v S ∈ ，由归纳假设，S−{v}中必有某点 u，它到 S−{v}中每个其它顶点都 有有向路。由于G G 单连通，在G G 中 u、v 之间必有有向路。如果 u 到 v 有有向路，则 u 符合 结论的要求；如果 v 到 u 有有向路，则 v 符合结论的要求。归纳法完成。 下面来证明定理必要性的结论。 取 S1=V( G G )，由上述结论，存在 1 1 u S ∈ ，使得 u1到 S1 中每个其它顶点都有有向路。再 令 S2=V( G G ) −{u1}，由上述结论，存在 2 2 u S ∈ ，使得 u2到 S2 中每个其它顶点都有有向路。 再令 S3=V( G G ) −{u1, u2}，由上述结论，存在 3 3 u S ∈ ，使得 u3 到 S3 中每个其它顶点都有有向 路。以此类推，可得到含所有顶点的序列，顶点沿序列依次有有向路，这些有向路合成一条 含所有点的有向途径。证毕。 §8.4 Euler 有向图和 Hamilton 有向图 定义 8.4.1 经过有向图G G 的所有弧恰一次的有向迹称为G G 的一条 Euler 有向迹。经过有向图 G G 的所有弧恰一次的有向闭迹称为G G 的一条 Euler 有向闭迹。存在 Euler 有向迹的有向图称 为 Euler 有向图。经过有向图G G 的所有顶点恰一次的有向路称为G G 的一条 Hamilton 有向路； 经过有向图G G 的所有顶点恰一次的有向圈称为G G 的一个 Hamilton 有向圈。存在 Hamilton 有 向圈的有向图称为 Hamilton 有向图。 定理 8.4.1 非平凡弱连通有向图 G 是 Euler 有向图的充分必要条件是对任何v VG ∈ ( ) ，都 有dv dv () () + − =
定理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 有向路