中科院研究生院专业基础课：《图论与网络流理论》第八章有向图（高随祥）.pdf_大学文库

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=，其第二分量顶点 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

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

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 () () + − =

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 有向路

证明:给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 是王。证毕

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

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)

10 0110 0011 0001 1000 A = ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ （2）若记顶点的得分向量为 (1) 1 2 (, , , )T m s = ⋅⋅⋅ ss s ，其中 i s 是顶点i 的得分，则由(1)不难知道 (1) , (1,1, ,1)T s Ae e = = ⋅⋅⋅ （3）由(2)、(3)式容易算出双向连通的图(4)（见 4 个顶点情况）的得分向量是 (1) (2,2,,1,1)T s = ，正如前面已经给出的。由 s (1)无法排出名次。注意到矩阵 2 A 的第 i 行第 j 列位置元素表示有向图中从顶点 i 出发两步可以到达的顶点的数目，因此 (2) 2 s = A e 。（此处待续！）其它情况对于既没有唯一完全路径，又不是双向连通的竞赛图，通常可以分解为若干个双向连通的子竞赛图（只有一个顶点的图视为双向连通竞赛图的特例），在下图中 8 个顶点的竞赛图分解为 3 个双向连通子竞赛图 123 GGG , , ，（此处缺图待补！）图中子图之间的边被简化了，实际上两子图的每对顶点之间都有边相连，而这些连的方向必是一致的，否则相应的子图可以合并为更大的双向连通子竞赛图，在每个这样的图中按上面介绍的方法排名次，而子图之间的名次不难由它们相连边的方向决定。在图中G1中各点的名次为{1, 2, 3, 4}；G2 是 3 个顶点的双向连通竞赛图，5、6、7 的名次相同；G3 只有 1 个顶点 8。故全部顶点的名次排列为{1, 2, 4, 3, 5 (6, 7), 8}. §8.6 根树及其应用一、根树定义 8.6.1 如果一个有向图在不考虑方向时是一棵树，则称这个有向图为有向树。定义 8.6.2 设 T 是一棵有向树。若 T 中有一个顶点的入度为 0，其余顶点的入度均为 1，则称 T 为根树。入度为 0 的顶点称为树根，入度为 1 且出度为 0 的顶点称为树叶，其余顶点称为内点，树根和内点称为分支点。注：1.从树根到任意顶点 v 的通路长度称为 v 的层数，层数最大顶点的层数称为树高 2.由于根树中各有向边的方向是一致的，所以画根树的图示时通常省去各边上的箭头，并将树根画在最上方

中科院研究生院专业基础课：《图论与网络流理论》第八章 有向图（高随祥）

中科院研究生院专业基础课：《图论与网络流理论》第八章有向图（高随祥）