1
第八章 有向图
§ 8.1 有向图的基本概念
定义 8.1.1 每条边都具有一个方向的图称为 有向图 。严格的说，一个有向图 G
null
是一个有序二元组 ((),()VG AG
nullnull nullnull
,其中集合 ()VG
nullnull
是非空的顶点集,集合 ()A G
nullnull
是 VV × 的一个子集 （有序对，
元素可重复）,它是带有方向的边的集合，称为 弧集,()A G
nullnull
中的元素称为 弧 或 有向边 。
例 8.1.1 (,)GVA=,其中 },,,,{
54321
vvvvvV =,有序对集合
12 23 23 34 35 15 15 55
{,,,,,,,,,,,,,,,}Avvvvvvvvvvvvvvvv=< >< >< >< >< >< >< >< >。
这便定义出一个有向图。
注,（ 1）相应地，前面所说的边不带有方向的图称为无向图。
（ 2）一个无向图 G 可以对应若干个有向图，它称为所对应的有向图的 基础图 或 底图 。
（ 3）将有向图的顶点可用平面上的一个点来表示，弧可用平面上的有向线段来表示（直的或曲的）,这样画出的平面图形称为图（有向图）的图示。
（ 4）对一条弧 e=<u,v>，其第二分量顶点 v（即箭头指向的顶点）称为它的首顶点，另一顶点称为它的尾顶点。一条首尾顶点相同的弧称为 环弧 （如下图中 e
8
）,两条具有相同首顶点和相同尾顶点的弧称为 并行弧 （如下图中 e
2
和 e
3
） 。既无环弧又无并行弧的有向图称为 简单有向图 （或 严格有向图 ） 。
例如，例 8.1.1 中有向图的一个图示为
定义 8.1.2 设 v是有向图 G
nullnull
的一个顶点。 v的 入度 ()
G
dv
nullnullnull
是指指向 v的弧的数目； v的 出度 ()
G
dG
+
nullnullnull
nullnull
是指从 v 出发的弧的数目。出度和入度可简写为 ()dv
+
和 ()dv
。
最小出度
()
() min{ ()}
vVG
Gdv
++
∈
δ=
nullnullnull
nullnull
最小入度
()
() min{ ()}
vVG
Gdv
∈
δ=
nullnullnull
nullnull
最大出度
()
() max{ ()}
vVG
Gdv
++
∈
Δ=
nullnullnull
nullnull
最大入度
()
() max{ ()}
vVG
Gdv
∈
Δ=
nullnullnull
nullnull
顶点 v 的出邻集 () { |(,) ( )}
G
Nv uvu AG
+
=∈
nullnullnull
nullnull
顶点 v 的入邻集 () { |(,) ( )}
G
Nv uuv AG
=∈
nullnullnull
nullnull
定理 8.1.1 对于有向图 G,ε2)(
)(
=
∑
∈ GVv
vd 且 =
∑
∈
+
)(
)(
GVv
vd
_
()
()
vVG
dv ε
∈
=
∑
。
证明与无向图情况类似。
v
4
e
1
e
2
e
3
e
4
e
5
e
6
e
7
v
1
v
2
v
3
v
5
e
8
2
§ 8.2 有向路与有向圈
定义 8.2.1 有向图的一个 有向途径 是指一个有限非空序列
011 kk
wvav av= null,它的各项交替地是顶点和弧，使得
1
(,),(1,2,,)
iii
avvi k
==null 。弧不重复的有向途径称为 有向迹 ；顶点不重复的有向途径称为 有向路 ；首尾相接的有向路称为 有向圈 。
注,有向图中有向路的长与其底图中路的长之间没有多大关系。例如,
但却与底图的色数有关。
定理 8.2.1 (Roy,1967;Gallai,1968) 以图 G 为底图的有向图 G
nullnull
中必有长为 ()1Gχ? 的有向路。
证明：设 A′是使有向图 GA′?
nullnull
不含有向圈的最小弧子集。设 GA′?
nullnull
中最长有向路的长为 k。
按如下方式将颜色 1,2,···,k+1 分配给 GA′?
nullnull
的顶点,
对任何顶点 ()vVG A′∈?
nullnull
，如 果 GA′?
nullnull
中从 v 出发的最长有向路长为 i，则 给 v 染色 i+1。
用 V
i
表示染有第 i 种色的顶点的集合。下证 (V
1
,V
2
,···,V
k+1
)是 G 的正常 k+1 顶点染色。为此，
先证明关于这种染色的两个结论。
（ 1） GA′?
nullnull
中任一有向路的起点与终点异色
事实上，设 P(u,v)是 GA′?
nullnull
的一条有向路,u≠ v。无妨设
1i
vV
+
∈ 。由染色规则可知，存在有向路
012 i
Qvvv v GA′=
nullnull
null 。
其中 v
0
=v。又因 GA′?
nullnull
中没有有向圈，故
12
,,,(,)
i
vv v Puv?null 。因此 (,)Puv Q∪ 是起点为 u 且长至少为 i＋ 1 的有向路。于是由染色规则，
i
uV? 。
（ 2） G 的任一条边两端点异色。
事实上，设 ()euvEG=∈ 。若 uv A′∈,则由 A′的最小性,( GA′?
nullnull
)+uv 含有有向圈 C。 C
- uv 是 GA′?
nullnull
的一条有向路，故由（ 1）,u 与 v 异色；若 ()uv A G A′∈?
nullnull
，则 uv 是 GA′?
nullnull
的一条有向路。由（ 1）,u 与 v 也异色。
可见 (V
1
,V
2
,···,V
k+1
)是 G 的正常 k+1 顶点染色。因而 () 1Gkχ ≤+，即 ()1kG≥χ? 。证毕。
定理 8.2.2 若 G
null
是无环有向图，则其底图 G 中必有一个独立集 S，使得对 ()VG S? 中的每个顶点 v，存在
0
vS∈,在 G
null
中从
0
v 到 v 有长不超过 2 的有向路。
证明：对顶点数 ν作归纳。
ν=1 时定理显然成立。
假设对顶点数少于 ν的所有有向图 G
null
，结论成立。考虑顶点数为 ν的有向图 G
null
。
3
任取 ()vVG∈
null
,令 ({ } ( ))GG v Nv
+
′=?
nullnull
∪ 。由归纳假设，存在 G′
null
的一个独立集 S′,对
()VG S′′?
null
中任何顶点，可从 S′中的某顶点出发，经过长度 2≤ 的有向路到达它。
(1) 若存在
0
vS′∈,使
0
()vv AG∈
null
，则 ()Nv
+
中每个顶点可从
0
v 出发，经过长度 2≤ 的有向路到达（ G
null
中其它点都在 G′
null
中，本来就长 2 路可达） 。
(2) 否则，对
0
vS′? ∈,
0
()vv AG?
null
，而且因 ()Nv S
+
′=Φ∩,
故
0
()vv A G?
null
，因此在底图 G 中 vS′与 中的点不相邻。
此时 {}SS v′= ∪ 满足定理的要求。 证毕。
§ 8.3 有向图的连通性
定义 8.3.1 设 G
null
是一个有向图,
(1) 若 G
null
的底图 G 是连通图，则称 G
null
是 弱连通的 。
(2) 若对 G
null
的任二顶点 u,v，要么存在有向路 P(u,v)，要么存在有向路 P(v,u)，则称 G
null
是 单连通的 。
(3) 若对 G
null
的任二顶点 u,v，既存在有向路 P(u,v)，又存在有向路 P(v,u)，则称 G
null
是 强连通的 （或称双向连通的） 。
注,易见，强连通?单连通?弱连通。
例,
定理 8.3.1 G
null
是强连通有向图的充要条件是 G
null
的所有顶点在一个有向闭途径上。
证明：必要性：设 G
null
是强连通有向图，
12
{,,,}VG vv v
ν
=
null
null（）,则存在有向路
112
(,),Pv v
223
(,)Pv v,null,
-1 1
(,),Pv v
ννν?
1
(,)Pv v
νν
，于是
1
i
i
P
ν
∪
即为含所有顶点的有向闭途径。
充分性：设 G
null
的顶点共处于一个有向闭途径 C 上，则对,()uv VG?∈
null
，在 C 上必有 u 到 v
的一段有向路
1
(,)Puv，也有 v 到 u 的一段有向路
1
(,)Pvu，故 G 是强连通的。证毕。
定理 8.3.2 无向图 G 可定向成强连通图的充分必要条件为,G 中无割边 (即 G 是 2 边连通图 )。
证明：必要性：用反证法。若 G 中有割边，则无论如何对 G 的各边定向，都无法使割边两端的点在所形成的有向图中双向连通。这与 G 可定向成为强连通有向图矛盾。
充分性：设 G 无割边，则 G 中存在圈。取其一个圈 C，记
1
GC= 。给
1
G 定向为顺时针方向。若
1
G 不是生成子图，则存在
11
() ( )vVGVG∈?,由第二章 Menger 定理，存在两条无弱连通单连通 强连通 不连通
S′
v0
N
+
(v)
v
4
公共边的路
11
,PQ，它们的一端是
1
v,另一端在
1
G 上。给
1
P 定向为指向
1
v,
1
Q 定向为指向
1
G,令
2111
GGPQ= ∪∪，则
2
G 是强连通的。
若
2
G 仍不是生成子图，则存在
22
() ( )vVGVG∈?,同理，存在无公共边的路
22
,PQ，
其一端在
2
v 处，另一端在
2
G 中。给
2
P 定向为指向
2
v,
2
Q 定向为指向
2
G,令
3222
GGPQ= ∪∪，则
3
G 是强连通的。如此反复，可得一个强连通子图序列
12
,,GGnull,
顶点数严格递增。因 |()|VG 是有限数，故必在某一步得到
n
G 后终止，
n
G 是强连通的且是
G 的生成子图。最后，把 G 中不在
n
G 中的边任意定向，得到以 G 为底图的一个强连通有向图。 证毕。
定理 8.3.3 G
null
是单连通有向图的充要条件是 G
null
的所有顶点在一个有向途径上。
证明：充分性是显然的。
必要性,首先用归纳法证明,对 G
null
的任何至少含有 2 个顶点的顶点子集 S,必有 uS∈,
使得 u 到 S 中每个其它顶点在 G
null
中都有有向路。
当 S 只含 2 个顶点时，由于 G
null
单连通，结论显然成立。
假设对任何含有 k 个顶点的子集，结论成立。下证对含有 k+1 个顶点的子集 S，结论也成立。
事实上，任取 vS∈,由归纳假设,S?{v}中必有某点 u，它到 S?{v}中每个其它顶点都有有向路。由于 G
null
单连通，在 G
null
中 u,v 之间必有有向路。如果 u 到 v 有有向路，则 u 符合结论的要求；如果 v 到 u 有有向路，则 v 符合结论的要求。归纳法完成。
下面来证明定理必要性的结论。
取 S
1
=V( G
null
)，由上述结论，存在
11
uS∈,使得 u
1
到 S
1
中每个其它顶点都有有向路。再令 S
2
=V( G
null
)?{u
1
}，由上述结论，存在
22
uS∈,使得 u
2
到 S
2
中每个其它顶点都有有向路。
再令 S
3
=V( G
null
)?{u
1
,u
2
}，由上述结论，存在
33
uS∈,使得 u
3
到 S
3
中每个其它顶点都有有向路。以此类推，可得到含所有顶点的序列，顶点沿序列依次有有向路，这些有向路合成一条含所有点的有向途径。证毕。
§ 8.4 Euler 有向图和 Hamilton 有向图
定义 8.4.1 经过有向图 G
null
的所有弧恰一次的有向迹称为 G
null
的一条 Euler 有向迹 。经过有向图
G
null
的所有弧恰一次的有向闭迹称为 G
null
的一条 Euler 有向闭迹 。存在 Euler 有向迹的有向图称为 Euler 有向图 。经过有向图 G
null
的所有顶点恰一次的有向路称为 G
null
的一条 Hamilton 有向路 ；
经过有向图 G
null
的所有顶点恰一次的有向圈称为 G
null
的一个 Hamilton 有向圈 。存在 Hamilton 有向圈的有向图称为 Hamilton 有向图 。
定理 8.4.1 非平凡弱连通有向图 G 是 Euler 有向图的充分必要条件是对任何 ()vVG∈,都有 () ()dv dv
+?
= 。
5
定理 8.4.2 非平凡弱连通有向图 G是 Euler有向图的充分必要条件是 G可分解为有向圈的并，
即：
1
k
i
i
GC
=
=
∪
，其中 C
i
是 G 的有向圈，且 () ( ),(1,)
ij
E CEC ijk=?≤≤∩,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 都有
() () 2 1du dv ν+≥?,(ν 是 G 的顶点数 ),
则 G 是 Hamilton 有向图。
证明略。
推论 1 设 G 是非平凡简单有向图，如果对任二满足 (,) ( )uv AG? 的顶点 u,v 都有
() ()du dv ν
+?
+≥,(ν 是 G 的顶点数 ),
则 G 是 Hamilton 有向图。
证明,先证 G 是强连通的,
任取 G 中两点 v
1
,v
2
，我们来证明 G 中必有 v
1
-v
2
有向路。事实上，如果 (v
1
,v
2
)是 G 中的一条弧，则结论显然；如果 (v
1
,v
2
)不是 G 中一条弧，则由条件
12
() ()dv dv ν
+?
+ ≥,至少存在一个异于 v
1
,v
2
的顶点 w，使
12
(,),(,)vw wv 是两条弧，从而
12
vwv 是一条 v
1
-v
2
有向路。
同理可知,G 中也存在一条 v
2
-v
1
有向路。由 v
1
,v
2
的任意性,G 是强连通的。
设 u 和 v 是任意两个不相邻顶点，由条件 () ()du dv ν
+?
+ ≥,且 () ()dv du ν
+?
+≥，
因此 () () 2du dv ν+≥，由定理 8.4.5,G 是 Hamilton 有向图。证毕。
推论 2 设 G 是强连通简单有向图,且对每个顶点 v 都有 ()dv ν≥,则 G 是 Hamilton 有向图。
推论 3 设 G 是简单有向图,且对每个顶点 v,都有 (),()
22
dv dv
ν ν
+?
≥≥,则 G 是 Hamilton
有向图。
定理 8.4.6 设 G 是非平凡简单有向图，如果对任二互不相邻顶点 u,v 都有
() () 2 3du dv ν+≥?,(ν 是 G 的顶点数 ),
则 G 含有 Hamilton 有向路。
6
证明,给 G 添加一个新顶点 w，并将 w 与 G 的每个顶点用两条方向相反的弧相连，由此构成一个新的有向图 G′。显然 G′是强连通图，任取 G′中两个不相邻顶点 u,v，则 u,v 是 G 的不相邻顶点，由条件知,
() () () () 4 (2 3) 4 2 1 2( 1) 1
GGGG
du dv du dv ν νν
′′
+=++≥?+=+=+?,
因 G′是 1ν + 阶强连通有向图，故由定理 8.4.5,G′包含一个 Hamilton 有向圈。从该圈删去 w
便得到 G 的一条 Hamilton 有向路。
类似于推论 1~推论 3，有如下推论,
推论 4 设 G 是非平凡简单有向图，如果对任二满足 (,) ( )uv AG? 的顶点 u,v 都有
() () 1du dv ν
+?
+≥?,(ν 是 G 的顶点数 ),
则 G 含有 Hamilton 有向路。
推论 5 设 G 是简单有向图,且对每个顶点 v 都有 () 1dv ν≥?,则 G 含有 Hamilton 有向路。
推论 6 设 G 是简单有向图，且对每个顶点 v 都有
11
(),()
22
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ν?,设它的出邻点为
12
,,,
k
vv v…,而 v 的入邻点为
12 1
,,,
kk
vv v
ν+ +?
…,则对每个
j
v (1 1)kjν+≤≤?,
12
,,,
k
vv v… 不会全是
j
v 的出邻点 （否则，
j
v 的出度为 1k +,
这与最大出度为 k 矛盾） 。因此
12
,,,
k
vv v… 至少有一点是
j
v 的入邻点。可见 v 到每个
j
v 都有长至多为 2 的有向路，从而 v 是王。 证毕。
7
由此定理说明，在循环赛中得胜最多的参赛者必定是王。但反之不真。事实上，王未必唯一。例如，下图 (a)中，顶点 a,b,c 都是王。在图 (b)中，顶点
12
,vv都是王，但 v
1
的出度为
2，而 v
2
的出度为 3。
定理 8.5.3 竞赛图中的顶点 v 是唯一的王当且仅当 v 的出度为 1ν? 。
证明：必要性：若 v 是唯一的王，且其出度小于 1ν?,则 v 有入邻点，设 v 的所有入邻点导出的子竞赛图为 G
1
，则由上一定理,G
1
有自己的王。设 u 是 G
1
的一个王。 因 u 到 v 有弧，故 u 也是 G 的王。这与 v 是唯一的王矛盾。
充分性：设 v 的出度为 1ν?,则 v 显然是王。若 G 还有另一王 v′，则由王的定义，要么存在弧 v′v，要么存在长为 2 的有向路 v′wv。无论如何,v 的入度至少为 1，从而其出度至多为 2ν?,这与前提条件矛盾。证毕。
这个定理说明，如果没有全胜的参赛者，则竞赛图至少有两个王。
定理 8.5.4 竞赛图 K
ν
null
中必存在有向 Hamilton 路（含有所有顶点的有向路） 。
证明,因 ()K
ν
χ =ν,故由定理 8.2.1,竞赛图 K
ν
null
中有长为 ()1 1K
ν
χ?=ν?的有向路,此即为 K
ν
null
的一条有向 Hamilton 路。 证毕。
定理 8.5.5 3ν ≥ 的强连通竞赛图的每个顶点都含在长为 k 的有向圈上 (3,4,,)k ν= null 。
证明：设 G
null
是一个强连通竞赛图,u 是 G 的任一个顶点。下面证明 u 在 G
null
的长为 3 的有向圈上。
取 (),()SNuTNu
+?
==，则 S 与 T 非空 (因 G
null
是强连通的，既有从 u 出发的弧，又有指向 u 的弧 )。用 (S,T)表示尾在 S 而头在 T 中的弧的集合。由于 G
null
是强连通竞赛图，故存在弧 (,) (,)vw ST∈,于是 u 在三角形 uvw 上，它是一个 3 阶有向圈。
下面对 k 用归纳法。
假设有长为 3,4,,mnull 的有向圈含有,( )umν< 。下证必有长为 m+1 的有向圈含有 u。
设
012 m
Cvvv v= null 是含有 u 的一个长为 m 的有向圈。
u
v
w
S=N
+
(u) T=N
(u)
a
b c
(a) (b)
v
1
v
2
v
3
v
4
v
5
8
(1) 若在 () ()VG VC?
null
中存在顶点 v 满足,v 是尾
在 C 上的一条弧的头，又是头在 C 上的一条弧的尾，则
在 C 上有顶点
11
,,() ()
ii i i
v v vv EG vv EG
++
∈∈
null null
使得 且,
(注意 G 是竞赛图,任二顶点间都有弧 )。 此时 u 在长为 m+1 的圈
01 1 2ii i m
vv vvv v v
++
nullnull上。
(2) 否则,用 S 表示 () ()VG VC? 中从圈 C 有弧指向的顶点之集,T 表示 () ()VG VC?
中有弧指向 C 的顶点之集。由于 m ν<,故,ST≠Φ∪ 又因 G
null
是强连通竞赛图，从而
,,(,)ST ST≠Φ ≠Φ ≠Φ。
(若 S =Φ，则 C 到 T 无有向路；同理 T ≠Φ；若 (,)ST =Φ，则 S 到 T 无有向路 )。
① 若 ST ST≠Φ∩∩,则 中的顶点符合 (1)中顶点 v 的要求。
② 若 ST=Φ∩,则存在,vSwT∈∈，使得 ()vw E G∈ (如图)。
注意 w 与 C 上每个顶点间的弧都指向 C (否则将导致情况(1))。同理 v 与 C 上所有顶点间的弧都指向 v。 因此总可适当选择 i 使得 u 在圈
01 2ii m
vv vvwv v
+
nullnull上,这是一个长为 m+1
的圈。证毕。
推论 强连通竞赛图是有向 Hamilton 图。
注,一个含有 ν 个顶点的图（或有向图）有长从 3 直到 ν 的圈（或有向圈）,则称这个图（或有向图）具有 泛圈性 。定理 8.5.5 表明强连通竞赛图具有泛圈性。实际上定理 8.5.5 证明了强连通竞赛图的一个更强的性质：如果竞赛图 G 是强连通的，则 G 中过每个顶点都有长从 3
直到 ν 的有向圈。判断一般图（或有向图）是否具有泛圈性，至今仍是一个悬而未决的难题。
下面讨论竞赛名次的排列问题。
3 个顶点的竞赛图有如下两种情况（不考虑顶点的标号） 。对于情况 (1),3 个队的名次排列显然应是 {1,2,3}；对于情况 (2),3 个队名次相同，因为他们各胜一场,
4 个顶点的竞赛图共有 4 种形式，下面分别进行讨论。
…
…
v0
v
m
v
i
v
i+1
v
…
…
v0
v
m
v
i
v
i+1
v
w
S
T
v
i+2
v1
13
(1)
2
2
1 3
(2)
9
（此处缺图待补！ ）
(1) 有唯一的通过全部顶点的有向路径 1→2→3→4，这种路径称为完全路径； 4 个队得分为 (3,2,1,0)，名次排列无疑应为 {1,2,3,4},
(2) 点 2 显然应排第 1，其余 3 点如图 (2)形式，名次相同； 4 个队得分为 (1,3,1,1)。
(3) 点 2 排在最后，其余 3 点 1 名次相同；得分为 (2,0,2,2),
(4) 有不只一条完全路径，如 1→2→3→4,3→4→1→2；得分为 (2,2,1,1)。由这些我们无法立即排出名次，但这种情形是研究的重点。还可以注意到,(4)具有 (1)~(3)所没有的性质：对于任何一对顶点，存在两条有向路径（每条路径由一条或几条边组成）,使两顶点可以相互连通，这种有向图称为双向连通的。
5 个顶点以上的竞赛图虽然更加复杂，但基本类型仍然如以上 4 个顶点给出的 3 种：具有唯一的完全路径如图 (1)；双向连通如图 (4)；不属于这两种情况如图 (2),(3)。
一般的 n 个顶点的竞赛图具有以下性质,
1) 竞赛图必存在完全路径。 （可用数学归纳法证明）
2) 若存在唯一的完全路径，则由完全路径确定的顶点的顺序，与按得分多少排列相一致。 （这里一个顶点的得分指由它按箭头方向引出的边的数目）,若顶点集为
V=(1,2,…,n)，不妨设唯一的完全路径为 1→2→…→ n,则顶点 i 的得分为 ni?
（ i =1,2,…,n） 。
显然，性质 2 给出了具有唯一完全路径的竞赛图的排列名次方法。 4 个顶点中图 (1)的情况正是这样。
双向连通竞赛图的名次排序 3个顶点的双向连通竞赛图，如上述 4 个顶点的竞赛图
(2),名次排序相同。以下讨论 (4)nn≥ 个顶点的双向连通竞赛图。
首先，竞赛图的邻接矩阵 ()
ij n n
Aa
×
= 重新定义如下,
1
0,
ij
ij
a =
存在从顶点 到 的有向边否则
（ 1）
依此，图 (4)的邻接矩阵为
10
0110
0011
0001
1000
A =
（ 2）
若记顶点的得分向量为
(1)
12
(,,,)
T
m
s ss s=,其中
i
s 是顶点 i 的得分，则由 (1)不难知道
(1)
,(1,,1)
T
sAee= = （ 3）
由 (2),(3)式容易算出双向连通的图 (4)（见 4 个顶点情况） 的得分向量是
(1)
(2,2,,1,1)
T
s =,
正如前面已经给出的。由 s
(1)
无法排出名次。
注意到矩阵
2
A 的第 i 行第 j 列位置元素表示有向图中从顶点 i 出发两步可以到达的顶点的数目，因此
(2) 2
s Ae= 。 （此处待续！ ）
其它情况 对于既没有唯一完全路径，又不是双向连通的竞赛图，通常可以分解为若干个双向连通的子竞赛图（只有一个顶点的图视为双向连通竞赛图的特例）,在下图中 8 个顶点的竞赛图分解为 3 个双向连通子竞赛图
123
,,GGG,
（此处缺图待补！ ）
图中子图之间的边被简化了，实际上两子图的每对顶点之间都有边相连，而这些连的方向必是一致的，否则相应的子图可以合并为更大的双向连通子竞赛图，在每个这样的图中按上面介绍的方法排名次，而子图之间的名次不难由它们相连边的方向决定。在图中
1
G 中各点的名次为 {1,2,3,4}；
2
G 是 3 个顶点的双向连通竞赛图,5,6,7 的名次相同；
3
G 只有 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.由于根树中各有向边的方向是一致的，所以画根树的图示时通常省去各边上的箭头，
并将树根画在最上方。
11
例,有向树和根树
定义 8.6.3 设 T 为一棵非平凡的根树,u,v 是 T 中两点。若 u 到 v 有有向路，则称 u 是 v
的祖先,v 是 u 的后代；若 u 到 v 有有向边，则称 u 是 v 的父亲,v 是 u 的儿子。若 u 和 v
有同一个父亲，则称 u 和 v 是兄弟。
定义 8.6.4
(1) 若将根树 T 中层数相同的顶点都标定次序（比如从左到右）,则称 T 为有序树。
(2) 若 T 的每个顶点至多有 r 个儿子，则称 T 为 r叉树；又若 r 叉树是有序的，则称它为 r
叉有序树。
(3) 若 T 的每个非叶子顶点都恰好有 r 个儿子，则称 T 为 r叉正则树；又若 T 是有序的，则称它为 r叉正则有序树。
(4) 若 T 为 r 叉正则树，且每个树叶的层数都等于树高，则称 T 为 r叉完全正则树；又若 T
是有序的，则称它为 r叉完全正则有序树。
定义 8.6.5 设 T 为一棵根树,v 是 T 中一个顶点。称 v 及其后代的导出子图为 T 的以 v 为根的根子树。 2 叉正则有序树的每个非叶子顶点的两个儿子导出的根子数分别称为左子树和右子树。
二,2 叉树与淘汰赛
定理 8.6.1 有 m 个分支点的 t 叉正则树 T 的阶为 1tmν = + 。
证明：因为 T 中除了树根外，其余点都是儿子，而 T 中 m 个分支点共有 t?m 个儿子。故
1tmν =+。
推论 8.6.1 有 m 个分支点的 t 叉正则树 T 有 (t?1)m+1 个叶子。
证明：因 T 中除了分支点便是叶子，故由上述定理,T 共有 (t?m+1)?m= (t?1)m+1 个叶子。
推论 8.6.2 有 m 个分支点的 2 叉正则树 T 有 2m+1 个顶点，其中有 m+1 个叶子。
定理 8.6.2 设 T 是高为 h 的 ν 阶 2 叉树，则
1
121
h
h ν
+
+ ≤≤?。
证明：设 T 中第 i 层的顶点有 n
i
个（ 0 ih≤ ≤ ）,则
0
h
i
i
n ν
=
=
∑
，又 12
i
i
n≤ ≤,故
1
00 0
11 221
hh h
ih
i
ii i
hnν
+
== =
+= ≤ =≤ =?
∑∑ ∑
。
定理 8.6.3 设 T 是高为 h 的 ν 阶 2 叉树，则
2
1
log ( )
2
h
ν +
≥
。
证明：由上一定理，
1
21
h
ν
+
≤?,即
1
2
2
h
ν +
≥ 。从而
2
1
log ( )
2
h
ν +
≥
。
例 8.6.1 假设某台计算机有一条加法指令，每次执行该指令可计算 3 个数之和。如果要计算
12
11 个数之和，问至少需要执行几次这个加法指令。
解,将 11 个数作为树叶，每个分支点对其儿子执行加法指令所得之数，则执行过程可用一棵 3 叉正则树来表示。因有 11 个叶子，且叉数 t=3，由推论 8.6.1，分支点有
11 1
5
31
m
==
个，故至少需执行这个加法指令 5 次。
2-叉树可用于描述淘汰赛。在淘汰赛中，一旦一支球队输了一场比赛，就被淘汰出局。
有 n 个选手参加的淘汰赛可用一棵有 n 片叶子的 2 叉树来表示。树叶表示选手，树高表示最长赛程。一个选手所在的层数表示他要取得冠军需要赢的比赛次数。如果各选手平等比赛，
则相应的淘汰赛模型是一棵完全正则 2 叉树。 如果某些选手需要经过附加赛才能进入正式赛或上届种子选手可以少参加前若干场比赛，则相应的淘汰赛模型是一棵不完全正则 2-叉树。
在淘汰赛中，最后获胜的球队未必是最好的球队，最好的球队可能在早些某场比赛中被淘汰了。
三,2 叉树与二元前缀码
定义 8.6.6 设
n
ααα null
21
是长为 n 的符号串，其子串
121211
,,,
n
αααααα nullnull 分别称为该符号串的长度为 1,,2,1?nnull 的 前缀 。设 A＝ {
m
βββ,,,
21
null }为一个符号串集合。若对
A
ji
∈? ββ,,（ ji ≠ ）,
i
β 与
j
β 都互不为前缀，则称 A 为 前缀码 。若 A 中每个符号串中都只出现 0,1 两个符号，则称 A 为 二元前缀码 。
例如,{1,00,011,0101,01001,01000}是二元前缀码，而 {1,00,011,0101,0100,01001}不是前缀码。
利用 2 叉树可产生二元前缀码。
定理 8.6.4 由一棵给定的 2 叉正则树可以产生一个二元前缀码。
证 设 T 是具有 t 片树叶的 2 叉树。 T 的任何分支点 v 必有 1 个或 2 个儿子。若 v 有两个儿子，在由 v 引出的两条边上，左边的标上 0，右边的标上 1。若 v 只有一个儿子，由它引出的边可以标 0 也可以标 1。设 u 是 T 的任一片树叶，从树根到 u 的通路上各边的标号按通路上边的顺序组成的符号串放在 u 处，因 u 处的符号串的前缀均在 u 所在的通路上取得，
故 t 片树叶对应的 t 个符号串组成的集合构成一个二元前缀码。
例如,由下列 2 叉树所产生的一个二元前缀码为 {01,11,000,0010,0011}。
如果将其中只有一个儿子的点发出的边标上 0，则得另一个二元前缀码,
0
10
1
0
1
1
0
1
01 11
000
0010 0011
13
{01,10,000,0010,0011}。
易见由一个正则 2 叉树只能产生唯一的二元前缀码。
一个二元前缀码中的码字有长有短，每个码字都可以代表某个符号，比如上述 5 个码字可以分别代表字母 A,B,C,D,E。当这些字母在文字中出现的频率不同时，用哪个码字代表哪个字母,需要优化安排,因为不同的安排方案其效率是不同的 (使用 0,1 符号的数量不同 )。
一个基本的想法是，尽可能用较短的码字代表使用频率较高的字母。这种使得 0,1 符号的数量最为节省的二元前缀码安排称为 最佳前缀码 。最佳前缀码可通过最优 2 叉树得到。
定义 8.6.7 设 2 叉树 T 有 t 片树叶
t
vvv,,,
21
null,分别标有权
t
www,,,
21
null 。称
∑
=
=
t
i
ii
vlwTW
1
)()(
为 T 的权，其中 )(
i
vl 是
i
v 的层数。在所有含 t 片叶子，带权
t
www,,,
21
null 的 2 叉树中，权最小的称为最优2叉树。
例如,下图所示的 3 个树都是带权 2,2,3,3,5 的 2 叉树。它们的权分别为 W(T
1
)=38，
W(T
2
)=36,W(T
3
)=47。
但这三棵 2 叉树都不是带权为 2,2,3,3,5 的最优二叉树。
z 求最优二叉树的算法－ Huffman 算法,
给定实数
t
www,,,
21
null,
t
www ≤≤≤ null
21
。
(1) 连接权为
21
,ww 的两片树叶，得一个分支点（即非叶子顶点）,其权为
21
ww + ；
(2) 在
21
ww +
t
ww,,,
3
null 中选出两个最小的权，连接它们对应的顶点，得到新的分支点及其所带的权。
(3) 重复（ 2）,直到形成 t－ 1 个分支点,t 片树叶为止。
例 8.6.2 求带权 2,2,3,3,5 的最优 2 叉树。
解：运用 Huffman 算法，构造如下,
最终得到一棵最优 2 叉树，权为 2×3+2×3+5×2+3×2+3×2=34。 （注意权的一种简便计算方式：
4+9+6+15 = 34） 。
2 2
4
2 2
4
33
6
22
4
33
6
5
9
2 2
4
3 3
6
5
9
15
25
3
3
2
3
3 5
2
2
T
3
T
2
T
1
2 3
5
3
2
14
利用最优二叉树可求得最佳前缀码。
例 8.6.3 在某种通信中，使用八进制数字串。各个数字出现的频率如下,
0,25%； 1,20%； 2,15%； 3,10%； 4,10%； 5,10%； 6,5%； 7,5%。
（ 1）求传输它们的最佳前缀码。 （ 2）问传输 10
n
个按上述比例出现的八进制数字需要多少个二进制数字？（ 3）如果用等长码字 （长为 3）传输 10
n
个按上述比例出现的八进制数字，
需要多少个二进制数字？
解：用 100 乘以各个数字出现的频率作为权，将权由小到大排列,w
0
=5,w
1
=5,w
2
=10,w
3
=10,
w
4
=10,w
5
=15,w
6
=20,w
7
=25,（记住它们对应哪个数字） 。用 Huffman 算法求出最优 2 叉树如下,
由此获得前缀码 {01,11,001,100,101,0001,00000,00001}，且各码字对应传输数字为,
01 传 0； 11 传 1； 001 传 2； 100 传 3； 101 传 4； 0001 传 5； 00000 传 6； 00001 传 7。
由 2 叉树的最优性可知所得前缀码 {01,11,001,100,101,0001,00000,00001}是最佳的。
用所得前缀码按题中给定频率发送 100 个八进制数字所用的二进制数字的个数为,
100(5×5%+5×5%+4×10%+3×15%+3×10%+3×10%+2×25%+2×20%)=285。
故传输 10
n
个按上述频率出现的八进制数字需要 285×10
n
=2.85×10
n?2
个二进制数字。
若用等长码字 {000,001,010,011,100,101,110,111}传输 10
n
个按上述频率出现的八进制数字需要 3×10
n
个二进制数字。
注,（ 1）最优 2 叉树权的另一种计算方式 W(T)=10+20+35+20+60+40+100=285。
（ 2）最佳前缀码并不唯一。由于每一步选择两个最小权的选法不同，且两个权对应的顶点所放左右位置不同，得到的最优树可能不同，由此可能得到不同的最佳前缀码。
例如，如下 2 叉树也是一棵最优树，权为 10+20+20+35+40+60+100=285，由此最优树给出的前缀码也是满足上例要求的最佳前缀码。
0
1 0
10
1
1
0
0
01
00000
001
0001
1
0 1
0 1
100
4060
20 2025
35
10 10
15
20
10
10
5 5
00001
100 101
11
1
35
0
0
0
1
10
10
0
01
0000 10000001
1
0 1
1
100
60
40
2520
20
20
15
10
10
101055
001
1001
101
11
15
前缀码 {01,11,001,101,0000,0001,1000,1001}，各码字对应传输数字为,
11 传 0； 01 传 1； 101 传 2； 001 传 3； 1000 传 4； 1001 传 5； 0000 传 6； 0001 传 7。
四,2 叉树的遍历
访问一棵根树的每个顶点一次且仅一次称为遍历这棵树。
遍历一棵有序正则二叉树的方法主要有以下三种,
1,中序遍历法：访问次序为“左子树、树根、右子树” ；
2,前序遍历法：访问次序为“树根、左子树、右子树” ；
3,后序遍历法：访问次序为“左子树、右子树、树根” 。
例如，下图所示的 2 叉有序正则树，按中序、前序、后序遍历的结果分别如下,
((hdi)be)a(fcg); a(b(dhi)e)(cfg); ((hid)eb)(fgc)a
利用 2 叉有序正则树和确定的遍历方法可表示四则运算的算式。 一般将最高层次的运算符放在树根上，然后依次将运算符放在根子树的树根上，参加运算的数字放在树叶上，被除数、被减数总是放在左子树树叶上。例如算式 (a?(b+c)+d?e?f)÷(g+(h?i)?j)在中序遍历法下可用下列 2 叉有序正则树表示,
关于有向图的更多内容可参看文献 [1]。
[1] J?rgen Bang-Jensen and Gregory Gutin,Digraphs,Theory,Algorithms and Applications,
Springer,2001,
ih
d
gf
c
e
b
a
a
b c
d
e
f
g
h i
j
÷
+ +
+?
16
第八章习题
1,证明,() ()
vV vV
dv dv ε
+
∈∈
= =
∑∑；
2,证明：若有向图 G 中无有向圈，则 0δδ
+
= = 。
3,证明：对每个竞赛图，要么它本身是强连通的，要么可以只改变一条弧的方向而变成强连通的。
4．任何连通图 G 必有一种定向方式，使得每条有向路的长度不超过 ()GΔ 。
5,设非平凡弱连通有向图 G 满足下列条件,
（ 1） () () () ()dx dx dy dy k
++
=?=；
（ 2） () (),( ( ) {,})dv dv vVG xy
+?
=?∈?。
证明,G 中有 k 条无公共边且以 x 为起点以 y 为终点的有向路。
6,n 名棋手进行循环赛，没有出现平局，也没有出现甲胜乙、乙胜丙、丙又胜甲的情况。证明必有一人在所有比赛中全胜，也必有一人在所有比赛中全败。
7,图有 n 种昆虫，每两种必有一种能吃掉另一种，证明可以把这些昆虫排序，使得每一种昆虫能吃掉它前面的那种昆虫。
8.在一次围棋擂台赛中，双方各出 n 名选手。比赛的规则是双方先各自排定一个次序，设甲方排定的次序为
12
,,,
n
x xx,乙方排定的次序为
12
,,,
n
y yy 。
1
x 与
1
y 先比赛，胜的一位与对方输的下一位选手比赛。按这种方法进行比赛，直到有一方的最后一位选手出场比赛并且输给对方，比赛结束。问最多进行几场比赛可定其胜负（假定比赛不出现平局） 。
第八章 有向图
§ 8.1 有向图的基本概念
定义 8.1.1 每条边都具有一个方向的图称为 有向图 。严格的说，一个有向图 G
null
是一个有序二元组 ((),()VG AG
nullnull nullnull
,其中集合 ()VG
nullnull
是非空的顶点集,集合 ()A G
nullnull
是 VV × 的一个子集 （有序对，
元素可重复）,它是带有方向的边的集合，称为 弧集,()A G
nullnull
中的元素称为 弧 或 有向边 。
例 8.1.1 (,)GVA=,其中 },,,,{
54321
vvvvvV =,有序对集合
12 23 23 34 35 15 15 55
{,,,,,,,,,,,,,,,}Avvvvvvvvvvvvvvvv=< >< >< >< >< >< >< >< >。
这便定义出一个有向图。
注,（ 1）相应地，前面所说的边不带有方向的图称为无向图。
（ 2）一个无向图 G 可以对应若干个有向图，它称为所对应的有向图的 基础图 或 底图 。
（ 3）将有向图的顶点可用平面上的一个点来表示，弧可用平面上的有向线段来表示（直的或曲的）,这样画出的平面图形称为图（有向图）的图示。
（ 4）对一条弧 e=<u,v>，其第二分量顶点 v（即箭头指向的顶点）称为它的首顶点，另一顶点称为它的尾顶点。一条首尾顶点相同的弧称为 环弧 （如下图中 e
8
）,两条具有相同首顶点和相同尾顶点的弧称为 并行弧 （如下图中 e
2
和 e
3
） 。既无环弧又无并行弧的有向图称为 简单有向图 （或 严格有向图 ） 。
例如，例 8.1.1 中有向图的一个图示为
定义 8.1.2 设 v是有向图 G
nullnull
的一个顶点。 v的 入度 ()
G
dv
nullnullnull
是指指向 v的弧的数目； v的 出度 ()
G
dG
+
nullnullnull
nullnull
是指从 v 出发的弧的数目。出度和入度可简写为 ()dv
+
和 ()dv
。
最小出度
()
() min{ ()}
vVG
Gdv
++
∈
δ=
nullnullnull
nullnull
最小入度
()
() min{ ()}
vVG
Gdv
∈
δ=
nullnullnull
nullnull
最大出度
()
() max{ ()}
vVG
Gdv
++
∈
Δ=
nullnullnull
nullnull
最大入度
()
() max{ ()}
vVG
Gdv
∈
Δ=
nullnullnull
nullnull
顶点 v 的出邻集 () { |(,) ( )}
G
Nv uvu AG
+
=∈
nullnullnull
nullnull
顶点 v 的入邻集 () { |(,) ( )}
G
Nv uuv AG
=∈
nullnullnull
nullnull
定理 8.1.1 对于有向图 G,ε2)(
)(
=
∑
∈ GVv
vd 且 =
∑
∈
+
)(
)(
GVv
vd
_
()
()
vVG
dv ε
∈
=
∑
。
证明与无向图情况类似。
v
4
e
1
e
2
e
3
e
4
e
5
e
6
e
7
v
1
v
2
v
3
v
5
e
8
2
§ 8.2 有向路与有向圈
定义 8.2.1 有向图的一个 有向途径 是指一个有限非空序列
011 kk
wvav av= null,它的各项交替地是顶点和弧，使得
1
(,),(1,2,,)
iii
avvi k
==null 。弧不重复的有向途径称为 有向迹 ；顶点不重复的有向途径称为 有向路 ；首尾相接的有向路称为 有向圈 。
注,有向图中有向路的长与其底图中路的长之间没有多大关系。例如,
但却与底图的色数有关。
定理 8.2.1 (Roy,1967;Gallai,1968) 以图 G 为底图的有向图 G
nullnull
中必有长为 ()1Gχ? 的有向路。
证明：设 A′是使有向图 GA′?
nullnull
不含有向圈的最小弧子集。设 GA′?
nullnull
中最长有向路的长为 k。
按如下方式将颜色 1,2,···,k+1 分配给 GA′?
nullnull
的顶点,
对任何顶点 ()vVG A′∈?
nullnull
，如 果 GA′?
nullnull
中从 v 出发的最长有向路长为 i，则 给 v 染色 i+1。
用 V
i
表示染有第 i 种色的顶点的集合。下证 (V
1
,V
2
,···,V
k+1
)是 G 的正常 k+1 顶点染色。为此，
先证明关于这种染色的两个结论。
（ 1） GA′?
nullnull
中任一有向路的起点与终点异色
事实上，设 P(u,v)是 GA′?
nullnull
的一条有向路,u≠ v。无妨设
1i
vV
+
∈ 。由染色规则可知，存在有向路
012 i
Qvvv v GA′=
nullnull
null 。
其中 v
0
=v。又因 GA′?
nullnull
中没有有向圈，故
12
,,,(,)
i
vv v Puv?null 。因此 (,)Puv Q∪ 是起点为 u 且长至少为 i＋ 1 的有向路。于是由染色规则，
i
uV? 。
（ 2） G 的任一条边两端点异色。
事实上，设 ()euvEG=∈ 。若 uv A′∈,则由 A′的最小性,( GA′?
nullnull
)+uv 含有有向圈 C。 C
- uv 是 GA′?
nullnull
的一条有向路，故由（ 1）,u 与 v 异色；若 ()uv A G A′∈?
nullnull
，则 uv 是 GA′?
nullnull
的一条有向路。由（ 1）,u 与 v 也异色。
可见 (V
1
,V
2
,···,V
k+1
)是 G 的正常 k+1 顶点染色。因而 () 1Gkχ ≤+，即 ()1kG≥χ? 。证毕。
定理 8.2.2 若 G
null
是无环有向图，则其底图 G 中必有一个独立集 S，使得对 ()VG S? 中的每个顶点 v，存在
0
vS∈,在 G
null
中从
0
v 到 v 有长不超过 2 的有向路。
证明：对顶点数 ν作归纳。
ν=1 时定理显然成立。
假设对顶点数少于 ν的所有有向图 G
null
，结论成立。考虑顶点数为 ν的有向图 G
null
。
3
任取 ()vVG∈
null
,令 ({ } ( ))GG v Nv
+
′=?
nullnull
∪ 。由归纳假设，存在 G′
null
的一个独立集 S′,对
()VG S′′?
null
中任何顶点，可从 S′中的某顶点出发，经过长度 2≤ 的有向路到达它。
(1) 若存在
0
vS′∈,使
0
()vv AG∈
null
，则 ()Nv
+
中每个顶点可从
0
v 出发，经过长度 2≤ 的有向路到达（ G
null
中其它点都在 G′
null
中，本来就长 2 路可达） 。
(2) 否则，对
0
vS′? ∈,
0
()vv AG?
null
，而且因 ()Nv S
+
′=Φ∩,
故
0
()vv A G?
null
，因此在底图 G 中 vS′与 中的点不相邻。
此时 {}SS v′= ∪ 满足定理的要求。 证毕。
§ 8.3 有向图的连通性
定义 8.3.1 设 G
null
是一个有向图,
(1) 若 G
null
的底图 G 是连通图，则称 G
null
是 弱连通的 。
(2) 若对 G
null
的任二顶点 u,v，要么存在有向路 P(u,v)，要么存在有向路 P(v,u)，则称 G
null
是 单连通的 。
(3) 若对 G
null
的任二顶点 u,v，既存在有向路 P(u,v)，又存在有向路 P(v,u)，则称 G
null
是 强连通的 （或称双向连通的） 。
注,易见，强连通?单连通?弱连通。
例,
定理 8.3.1 G
null
是强连通有向图的充要条件是 G
null
的所有顶点在一个有向闭途径上。
证明：必要性：设 G
null
是强连通有向图，
12
{,,,}VG vv v
ν
=
null
null（）,则存在有向路
112
(,),Pv v
223
(,)Pv v,null,
-1 1
(,),Pv v
ννν?
1
(,)Pv v
νν
，于是
1
i
i
P
ν
∪
即为含所有顶点的有向闭途径。
充分性：设 G
null
的顶点共处于一个有向闭途径 C 上，则对,()uv VG?∈
null
，在 C 上必有 u 到 v
的一段有向路
1
(,)Puv，也有 v 到 u 的一段有向路
1
(,)Pvu，故 G 是强连通的。证毕。
定理 8.3.2 无向图 G 可定向成强连通图的充分必要条件为,G 中无割边 (即 G 是 2 边连通图 )。
证明：必要性：用反证法。若 G 中有割边，则无论如何对 G 的各边定向，都无法使割边两端的点在所形成的有向图中双向连通。这与 G 可定向成为强连通有向图矛盾。
充分性：设 G 无割边，则 G 中存在圈。取其一个圈 C，记
1
GC= 。给
1
G 定向为顺时针方向。若
1
G 不是生成子图，则存在
11
() ( )vVGVG∈?,由第二章 Menger 定理，存在两条无弱连通单连通 强连通 不连通
S′
v0
N
+
(v)
v
4
公共边的路
11
,PQ，它们的一端是
1
v,另一端在
1
G 上。给
1
P 定向为指向
1
v,
1
Q 定向为指向
1
G,令
2111
GGPQ= ∪∪，则
2
G 是强连通的。
若
2
G 仍不是生成子图，则存在
22
() ( )vVGVG∈?,同理，存在无公共边的路
22
,PQ，
其一端在
2
v 处，另一端在
2
G 中。给
2
P 定向为指向
2
v,
2
Q 定向为指向
2
G,令
3222
GGPQ= ∪∪，则
3
G 是强连通的。如此反复，可得一个强连通子图序列
12
,,GGnull,
顶点数严格递增。因 |()|VG 是有限数，故必在某一步得到
n
G 后终止，
n
G 是强连通的且是
G 的生成子图。最后，把 G 中不在
n
G 中的边任意定向，得到以 G 为底图的一个强连通有向图。 证毕。
定理 8.3.3 G
null
是单连通有向图的充要条件是 G
null
的所有顶点在一个有向途径上。
证明：充分性是显然的。
必要性,首先用归纳法证明,对 G
null
的任何至少含有 2 个顶点的顶点子集 S,必有 uS∈,
使得 u 到 S 中每个其它顶点在 G
null
中都有有向路。
当 S 只含 2 个顶点时，由于 G
null
单连通，结论显然成立。
假设对任何含有 k 个顶点的子集，结论成立。下证对含有 k+1 个顶点的子集 S，结论也成立。
事实上，任取 vS∈,由归纳假设,S?{v}中必有某点 u，它到 S?{v}中每个其它顶点都有有向路。由于 G
null
单连通，在 G
null
中 u,v 之间必有有向路。如果 u 到 v 有有向路，则 u 符合结论的要求；如果 v 到 u 有有向路，则 v 符合结论的要求。归纳法完成。
下面来证明定理必要性的结论。
取 S
1
=V( G
null
)，由上述结论，存在
11
uS∈,使得 u
1
到 S
1
中每个其它顶点都有有向路。再令 S
2
=V( G
null
)?{u
1
}，由上述结论，存在
22
uS∈,使得 u
2
到 S
2
中每个其它顶点都有有向路。
再令 S
3
=V( G
null
)?{u
1
,u
2
}，由上述结论，存在
33
uS∈,使得 u
3
到 S
3
中每个其它顶点都有有向路。以此类推，可得到含所有顶点的序列，顶点沿序列依次有有向路，这些有向路合成一条含所有点的有向途径。证毕。
§ 8.4 Euler 有向图和 Hamilton 有向图
定义 8.4.1 经过有向图 G
null
的所有弧恰一次的有向迹称为 G
null
的一条 Euler 有向迹 。经过有向图
G
null
的所有弧恰一次的有向闭迹称为 G
null
的一条 Euler 有向闭迹 。存在 Euler 有向迹的有向图称为 Euler 有向图 。经过有向图 G
null
的所有顶点恰一次的有向路称为 G
null
的一条 Hamilton 有向路 ；
经过有向图 G
null
的所有顶点恰一次的有向圈称为 G
null
的一个 Hamilton 有向圈 。存在 Hamilton 有向圈的有向图称为 Hamilton 有向图 。
定理 8.4.1 非平凡弱连通有向图 G 是 Euler 有向图的充分必要条件是对任何 ()vVG∈,都有 () ()dv dv
+?
= 。
5
定理 8.4.2 非平凡弱连通有向图 G是 Euler有向图的充分必要条件是 G可分解为有向圈的并，
即：
1
k
i
i
GC
=
=
∪
，其中 C
i
是 G 的有向圈，且 () ( ),(1,)
ij
E CEC ijk=?≤≤∩,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 都有
() () 2 1du dv ν+≥?,(ν 是 G 的顶点数 ),
则 G 是 Hamilton 有向图。
证明略。
推论 1 设 G 是非平凡简单有向图，如果对任二满足 (,) ( )uv AG? 的顶点 u,v 都有
() ()du dv ν
+?
+≥,(ν 是 G 的顶点数 ),
则 G 是 Hamilton 有向图。
证明,先证 G 是强连通的,
任取 G 中两点 v
1
,v
2
，我们来证明 G 中必有 v
1
-v
2
有向路。事实上，如果 (v
1
,v
2
)是 G 中的一条弧，则结论显然；如果 (v
1
,v
2
)不是 G 中一条弧，则由条件
12
() ()dv dv ν
+?
+ ≥,至少存在一个异于 v
1
,v
2
的顶点 w，使
12
(,),(,)vw wv 是两条弧，从而
12
vwv 是一条 v
1
-v
2
有向路。
同理可知,G 中也存在一条 v
2
-v
1
有向路。由 v
1
,v
2
的任意性,G 是强连通的。
设 u 和 v 是任意两个不相邻顶点，由条件 () ()du dv ν
+?
+ ≥,且 () ()dv du ν
+?
+≥，
因此 () () 2du dv ν+≥，由定理 8.4.5,G 是 Hamilton 有向图。证毕。
推论 2 设 G 是强连通简单有向图,且对每个顶点 v 都有 ()dv ν≥,则 G 是 Hamilton 有向图。
推论 3 设 G 是简单有向图,且对每个顶点 v,都有 (),()
22
dv dv
ν ν
+?
≥≥,则 G 是 Hamilton
有向图。
定理 8.4.6 设 G 是非平凡简单有向图，如果对任二互不相邻顶点 u,v 都有
() () 2 3du dv ν+≥?,(ν 是 G 的顶点数 ),
则 G 含有 Hamilton 有向路。
6
证明,给 G 添加一个新顶点 w，并将 w 与 G 的每个顶点用两条方向相反的弧相连，由此构成一个新的有向图 G′。显然 G′是强连通图，任取 G′中两个不相邻顶点 u,v，则 u,v 是 G 的不相邻顶点，由条件知,
() () () () 4 (2 3) 4 2 1 2( 1) 1
GGGG
du dv du dv ν νν
′′
+=++≥?+=+=+?,
因 G′是 1ν + 阶强连通有向图，故由定理 8.4.5,G′包含一个 Hamilton 有向圈。从该圈删去 w
便得到 G 的一条 Hamilton 有向路。
类似于推论 1~推论 3，有如下推论,
推论 4 设 G 是非平凡简单有向图，如果对任二满足 (,) ( )uv AG? 的顶点 u,v 都有
() () 1du dv ν
+?
+≥?,(ν 是 G 的顶点数 ),
则 G 含有 Hamilton 有向路。
推论 5 设 G 是简单有向图,且对每个顶点 v 都有 () 1dv ν≥?,则 G 含有 Hamilton 有向路。
推论 6 设 G 是简单有向图，且对每个顶点 v 都有
11
(),()
22
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ν?,设它的出邻点为
12
,,,
k
vv v…,而 v 的入邻点为
12 1
,,,
kk
vv v
ν+ +?
…,则对每个
j
v (1 1)kjν+≤≤?,
12
,,,
k
vv v… 不会全是
j
v 的出邻点 （否则，
j
v 的出度为 1k +,
这与最大出度为 k 矛盾） 。因此
12
,,,
k
vv v… 至少有一点是
j
v 的入邻点。可见 v 到每个
j
v 都有长至多为 2 的有向路，从而 v 是王。 证毕。
7
由此定理说明，在循环赛中得胜最多的参赛者必定是王。但反之不真。事实上，王未必唯一。例如，下图 (a)中，顶点 a,b,c 都是王。在图 (b)中，顶点
12
,vv都是王，但 v
1
的出度为
2，而 v
2
的出度为 3。
定理 8.5.3 竞赛图中的顶点 v 是唯一的王当且仅当 v 的出度为 1ν? 。
证明：必要性：若 v 是唯一的王，且其出度小于 1ν?,则 v 有入邻点，设 v 的所有入邻点导出的子竞赛图为 G
1
，则由上一定理,G
1
有自己的王。设 u 是 G
1
的一个王。 因 u 到 v 有弧，故 u 也是 G 的王。这与 v 是唯一的王矛盾。
充分性：设 v 的出度为 1ν?,则 v 显然是王。若 G 还有另一王 v′，则由王的定义，要么存在弧 v′v，要么存在长为 2 的有向路 v′wv。无论如何,v 的入度至少为 1，从而其出度至多为 2ν?,这与前提条件矛盾。证毕。
这个定理说明，如果没有全胜的参赛者，则竞赛图至少有两个王。
定理 8.5.4 竞赛图 K
ν
null
中必存在有向 Hamilton 路（含有所有顶点的有向路） 。
证明,因 ()K
ν
χ =ν,故由定理 8.2.1,竞赛图 K
ν
null
中有长为 ()1 1K
ν
χ?=ν?的有向路,此即为 K
ν
null
的一条有向 Hamilton 路。 证毕。
定理 8.5.5 3ν ≥ 的强连通竞赛图的每个顶点都含在长为 k 的有向圈上 (3,4,,)k ν= null 。
证明：设 G
null
是一个强连通竞赛图,u 是 G 的任一个顶点。下面证明 u 在 G
null
的长为 3 的有向圈上。
取 (),()SNuTNu
+?
==，则 S 与 T 非空 (因 G
null
是强连通的，既有从 u 出发的弧，又有指向 u 的弧 )。用 (S,T)表示尾在 S 而头在 T 中的弧的集合。由于 G
null
是强连通竞赛图，故存在弧 (,) (,)vw ST∈,于是 u 在三角形 uvw 上，它是一个 3 阶有向圈。
下面对 k 用归纳法。
假设有长为 3,4,,mnull 的有向圈含有,( )umν< 。下证必有长为 m+1 的有向圈含有 u。
设
012 m
Cvvv v= null 是含有 u 的一个长为 m 的有向圈。
u
v
w
S=N
+
(u) T=N
(u)
a
b c
(a) (b)
v
1
v
2
v
3
v
4
v
5
8
(1) 若在 () ()VG VC?
null
中存在顶点 v 满足,v 是尾
在 C 上的一条弧的头，又是头在 C 上的一条弧的尾，则
在 C 上有顶点
11
,,() ()
ii i i
v v vv EG vv EG
++
∈∈
null null
使得 且,
(注意 G 是竞赛图,任二顶点间都有弧 )。 此时 u 在长为 m+1 的圈
01 1 2ii i m
vv vvv v v
++
nullnull上。
(2) 否则,用 S 表示 () ()VG VC? 中从圈 C 有弧指向的顶点之集,T 表示 () ()VG VC?
中有弧指向 C 的顶点之集。由于 m ν<,故,ST≠Φ∪ 又因 G
null
是强连通竞赛图，从而
,,(,)ST ST≠Φ ≠Φ ≠Φ。
(若 S =Φ，则 C 到 T 无有向路；同理 T ≠Φ；若 (,)ST =Φ，则 S 到 T 无有向路 )。
① 若 ST ST≠Φ∩∩,则 中的顶点符合 (1)中顶点 v 的要求。
② 若 ST=Φ∩,则存在,vSwT∈∈，使得 ()vw E G∈ (如图)。
注意 w 与 C 上每个顶点间的弧都指向 C (否则将导致情况(1))。同理 v 与 C 上所有顶点间的弧都指向 v。 因此总可适当选择 i 使得 u 在圈
01 2ii m
vv vvwv v
+
nullnull上,这是一个长为 m+1
的圈。证毕。
推论 强连通竞赛图是有向 Hamilton 图。
注,一个含有 ν 个顶点的图（或有向图）有长从 3 直到 ν 的圈（或有向圈）,则称这个图（或有向图）具有 泛圈性 。定理 8.5.5 表明强连通竞赛图具有泛圈性。实际上定理 8.5.5 证明了强连通竞赛图的一个更强的性质：如果竞赛图 G 是强连通的，则 G 中过每个顶点都有长从 3
直到 ν 的有向圈。判断一般图（或有向图）是否具有泛圈性，至今仍是一个悬而未决的难题。
下面讨论竞赛名次的排列问题。
3 个顶点的竞赛图有如下两种情况（不考虑顶点的标号） 。对于情况 (1),3 个队的名次排列显然应是 {1,2,3}；对于情况 (2),3 个队名次相同，因为他们各胜一场,
4 个顶点的竞赛图共有 4 种形式，下面分别进行讨论。
…
…
v0
v
m
v
i
v
i+1
v
…
…
v0
v
m
v
i
v
i+1
v
w
S
T
v
i+2
v1
13
(1)
2
2
1 3
(2)
9
（此处缺图待补！ ）
(1) 有唯一的通过全部顶点的有向路径 1→2→3→4，这种路径称为完全路径； 4 个队得分为 (3,2,1,0)，名次排列无疑应为 {1,2,3,4},
(2) 点 2 显然应排第 1，其余 3 点如图 (2)形式，名次相同； 4 个队得分为 (1,3,1,1)。
(3) 点 2 排在最后，其余 3 点 1 名次相同；得分为 (2,0,2,2),
(4) 有不只一条完全路径，如 1→2→3→4,3→4→1→2；得分为 (2,2,1,1)。由这些我们无法立即排出名次，但这种情形是研究的重点。还可以注意到,(4)具有 (1)~(3)所没有的性质：对于任何一对顶点，存在两条有向路径（每条路径由一条或几条边组成）,使两顶点可以相互连通，这种有向图称为双向连通的。
5 个顶点以上的竞赛图虽然更加复杂，但基本类型仍然如以上 4 个顶点给出的 3 种：具有唯一的完全路径如图 (1)；双向连通如图 (4)；不属于这两种情况如图 (2),(3)。
一般的 n 个顶点的竞赛图具有以下性质,
1) 竞赛图必存在完全路径。 （可用数学归纳法证明）
2) 若存在唯一的完全路径，则由完全路径确定的顶点的顺序，与按得分多少排列相一致。 （这里一个顶点的得分指由它按箭头方向引出的边的数目）,若顶点集为
V=(1,2,…,n)，不妨设唯一的完全路径为 1→2→…→ n,则顶点 i 的得分为 ni?
（ i =1,2,…,n） 。
显然，性质 2 给出了具有唯一完全路径的竞赛图的排列名次方法。 4 个顶点中图 (1)的情况正是这样。
双向连通竞赛图的名次排序 3个顶点的双向连通竞赛图，如上述 4 个顶点的竞赛图
(2),名次排序相同。以下讨论 (4)nn≥ 个顶点的双向连通竞赛图。
首先，竞赛图的邻接矩阵 ()
ij n n
Aa
×
= 重新定义如下,
1
0,
ij
ij
a =
存在从顶点 到 的有向边否则
（ 1）
依此，图 (4)的邻接矩阵为
10
0110
0011
0001
1000
A =
（ 2）
若记顶点的得分向量为
(1)
12
(,,,)
T
m
s ss s=,其中
i
s 是顶点 i 的得分，则由 (1)不难知道
(1)
,(1,,1)
T
sAee= = （ 3）
由 (2),(3)式容易算出双向连通的图 (4)（见 4 个顶点情况） 的得分向量是
(1)
(2,2,,1,1)
T
s =,
正如前面已经给出的。由 s
(1)
无法排出名次。
注意到矩阵
2
A 的第 i 行第 j 列位置元素表示有向图中从顶点 i 出发两步可以到达的顶点的数目，因此
(2) 2
s Ae= 。 （此处待续！ ）
其它情况 对于既没有唯一完全路径，又不是双向连通的竞赛图，通常可以分解为若干个双向连通的子竞赛图（只有一个顶点的图视为双向连通竞赛图的特例）,在下图中 8 个顶点的竞赛图分解为 3 个双向连通子竞赛图
123
,,GGG,
（此处缺图待补！ ）
图中子图之间的边被简化了，实际上两子图的每对顶点之间都有边相连，而这些连的方向必是一致的，否则相应的子图可以合并为更大的双向连通子竞赛图，在每个这样的图中按上面介绍的方法排名次，而子图之间的名次不难由它们相连边的方向决定。在图中
1
G 中各点的名次为 {1,2,3,4}；
2
G 是 3 个顶点的双向连通竞赛图,5,6,7 的名次相同；
3
G 只有 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.由于根树中各有向边的方向是一致的，所以画根树的图示时通常省去各边上的箭头，
并将树根画在最上方。
11
例,有向树和根树
定义 8.6.3 设 T 为一棵非平凡的根树,u,v 是 T 中两点。若 u 到 v 有有向路，则称 u 是 v
的祖先,v 是 u 的后代；若 u 到 v 有有向边，则称 u 是 v 的父亲,v 是 u 的儿子。若 u 和 v
有同一个父亲，则称 u 和 v 是兄弟。
定义 8.6.4
(1) 若将根树 T 中层数相同的顶点都标定次序（比如从左到右）,则称 T 为有序树。
(2) 若 T 的每个顶点至多有 r 个儿子，则称 T 为 r叉树；又若 r 叉树是有序的，则称它为 r
叉有序树。
(3) 若 T 的每个非叶子顶点都恰好有 r 个儿子，则称 T 为 r叉正则树；又若 T 是有序的，则称它为 r叉正则有序树。
(4) 若 T 为 r 叉正则树，且每个树叶的层数都等于树高，则称 T 为 r叉完全正则树；又若 T
是有序的，则称它为 r叉完全正则有序树。
定义 8.6.5 设 T 为一棵根树,v 是 T 中一个顶点。称 v 及其后代的导出子图为 T 的以 v 为根的根子树。 2 叉正则有序树的每个非叶子顶点的两个儿子导出的根子数分别称为左子树和右子树。
二,2 叉树与淘汰赛
定理 8.6.1 有 m 个分支点的 t 叉正则树 T 的阶为 1tmν = + 。
证明：因为 T 中除了树根外，其余点都是儿子，而 T 中 m 个分支点共有 t?m 个儿子。故
1tmν =+。
推论 8.6.1 有 m 个分支点的 t 叉正则树 T 有 (t?1)m+1 个叶子。
证明：因 T 中除了分支点便是叶子，故由上述定理,T 共有 (t?m+1)?m= (t?1)m+1 个叶子。
推论 8.6.2 有 m 个分支点的 2 叉正则树 T 有 2m+1 个顶点，其中有 m+1 个叶子。
定理 8.6.2 设 T 是高为 h 的 ν 阶 2 叉树，则
1
121
h
h ν
+
+ ≤≤?。
证明：设 T 中第 i 层的顶点有 n
i
个（ 0 ih≤ ≤ ）,则
0
h
i
i
n ν
=
=
∑
，又 12
i
i
n≤ ≤,故
1
00 0
11 221
hh h
ih
i
ii i
hnν
+
== =
+= ≤ =≤ =?
∑∑ ∑
。
定理 8.6.3 设 T 是高为 h 的 ν 阶 2 叉树，则
2
1
log ( )
2
h
ν +
≥
。
证明：由上一定理，
1
21
h
ν
+
≤?,即
1
2
2
h
ν +
≥ 。从而
2
1
log ( )
2
h
ν +
≥
。
例 8.6.1 假设某台计算机有一条加法指令，每次执行该指令可计算 3 个数之和。如果要计算
12
11 个数之和，问至少需要执行几次这个加法指令。
解,将 11 个数作为树叶，每个分支点对其儿子执行加法指令所得之数，则执行过程可用一棵 3 叉正则树来表示。因有 11 个叶子，且叉数 t=3，由推论 8.6.1，分支点有
11 1
5
31
m
==
个，故至少需执行这个加法指令 5 次。
2-叉树可用于描述淘汰赛。在淘汰赛中，一旦一支球队输了一场比赛，就被淘汰出局。
有 n 个选手参加的淘汰赛可用一棵有 n 片叶子的 2 叉树来表示。树叶表示选手，树高表示最长赛程。一个选手所在的层数表示他要取得冠军需要赢的比赛次数。如果各选手平等比赛，
则相应的淘汰赛模型是一棵完全正则 2 叉树。 如果某些选手需要经过附加赛才能进入正式赛或上届种子选手可以少参加前若干场比赛，则相应的淘汰赛模型是一棵不完全正则 2-叉树。
在淘汰赛中，最后获胜的球队未必是最好的球队，最好的球队可能在早些某场比赛中被淘汰了。
三,2 叉树与二元前缀码
定义 8.6.6 设
n
ααα null
21
是长为 n 的符号串，其子串
121211
,,,
n
αααααα nullnull 分别称为该符号串的长度为 1,,2,1?nnull 的 前缀 。设 A＝ {
m
βββ,,,
21
null }为一个符号串集合。若对
A
ji
∈? ββ,,（ ji ≠ ）,
i
β 与
j
β 都互不为前缀，则称 A 为 前缀码 。若 A 中每个符号串中都只出现 0,1 两个符号，则称 A 为 二元前缀码 。
例如,{1,00,011,0101,01001,01000}是二元前缀码，而 {1,00,011,0101,0100,01001}不是前缀码。
利用 2 叉树可产生二元前缀码。
定理 8.6.4 由一棵给定的 2 叉正则树可以产生一个二元前缀码。
证 设 T 是具有 t 片树叶的 2 叉树。 T 的任何分支点 v 必有 1 个或 2 个儿子。若 v 有两个儿子，在由 v 引出的两条边上，左边的标上 0，右边的标上 1。若 v 只有一个儿子，由它引出的边可以标 0 也可以标 1。设 u 是 T 的任一片树叶，从树根到 u 的通路上各边的标号按通路上边的顺序组成的符号串放在 u 处，因 u 处的符号串的前缀均在 u 所在的通路上取得，
故 t 片树叶对应的 t 个符号串组成的集合构成一个二元前缀码。
例如,由下列 2 叉树所产生的一个二元前缀码为 {01,11,000,0010,0011}。
如果将其中只有一个儿子的点发出的边标上 0，则得另一个二元前缀码,
0
10
1
0
1
1
0
1
01 11
000
0010 0011
13
{01,10,000,0010,0011}。
易见由一个正则 2 叉树只能产生唯一的二元前缀码。
一个二元前缀码中的码字有长有短，每个码字都可以代表某个符号，比如上述 5 个码字可以分别代表字母 A,B,C,D,E。当这些字母在文字中出现的频率不同时，用哪个码字代表哪个字母,需要优化安排,因为不同的安排方案其效率是不同的 (使用 0,1 符号的数量不同 )。
一个基本的想法是，尽可能用较短的码字代表使用频率较高的字母。这种使得 0,1 符号的数量最为节省的二元前缀码安排称为 最佳前缀码 。最佳前缀码可通过最优 2 叉树得到。
定义 8.6.7 设 2 叉树 T 有 t 片树叶
t
vvv,,,
21
null,分别标有权
t
www,,,
21
null 。称
∑
=
=
t
i
ii
vlwTW
1
)()(
为 T 的权，其中 )(
i
vl 是
i
v 的层数。在所有含 t 片叶子，带权
t
www,,,
21
null 的 2 叉树中，权最小的称为最优2叉树。
例如,下图所示的 3 个树都是带权 2,2,3,3,5 的 2 叉树。它们的权分别为 W(T
1
)=38，
W(T
2
)=36,W(T
3
)=47。
但这三棵 2 叉树都不是带权为 2,2,3,3,5 的最优二叉树。
z 求最优二叉树的算法－ Huffman 算法,
给定实数
t
www,,,
21
null,
t
www ≤≤≤ null
21
。
(1) 连接权为
21
,ww 的两片树叶，得一个分支点（即非叶子顶点）,其权为
21
ww + ；
(2) 在
21
ww +
t
ww,,,
3
null 中选出两个最小的权，连接它们对应的顶点，得到新的分支点及其所带的权。
(3) 重复（ 2）,直到形成 t－ 1 个分支点,t 片树叶为止。
例 8.6.2 求带权 2,2,3,3,5 的最优 2 叉树。
解：运用 Huffman 算法，构造如下,
最终得到一棵最优 2 叉树，权为 2×3+2×3+5×2+3×2+3×2=34。 （注意权的一种简便计算方式：
4+9+6+15 = 34） 。
2 2
4
2 2
4
33
6
22
4
33
6
5
9
2 2
4
3 3
6
5
9
15
25
3
3
2
3
3 5
2
2
T
3
T
2
T
1
2 3
5
3
2
14
利用最优二叉树可求得最佳前缀码。
例 8.6.3 在某种通信中，使用八进制数字串。各个数字出现的频率如下,
0,25%； 1,20%； 2,15%； 3,10%； 4,10%； 5,10%； 6,5%； 7,5%。
（ 1）求传输它们的最佳前缀码。 （ 2）问传输 10
n
个按上述比例出现的八进制数字需要多少个二进制数字？（ 3）如果用等长码字 （长为 3）传输 10
n
个按上述比例出现的八进制数字，
需要多少个二进制数字？
解：用 100 乘以各个数字出现的频率作为权，将权由小到大排列,w
0
=5,w
1
=5,w
2
=10,w
3
=10,
w
4
=10,w
5
=15,w
6
=20,w
7
=25,（记住它们对应哪个数字） 。用 Huffman 算法求出最优 2 叉树如下,
由此获得前缀码 {01,11,001,100,101,0001,00000,00001}，且各码字对应传输数字为,
01 传 0； 11 传 1； 001 传 2； 100 传 3； 101 传 4； 0001 传 5； 00000 传 6； 00001 传 7。
由 2 叉树的最优性可知所得前缀码 {01,11,001,100,101,0001,00000,00001}是最佳的。
用所得前缀码按题中给定频率发送 100 个八进制数字所用的二进制数字的个数为,
100(5×5%+5×5%+4×10%+3×15%+3×10%+3×10%+2×25%+2×20%)=285。
故传输 10
n
个按上述频率出现的八进制数字需要 285×10
n
=2.85×10
n?2
个二进制数字。
若用等长码字 {000,001,010,011,100,101,110,111}传输 10
n
个按上述频率出现的八进制数字需要 3×10
n
个二进制数字。
注,（ 1）最优 2 叉树权的另一种计算方式 W(T)=10+20+35+20+60+40+100=285。
（ 2）最佳前缀码并不唯一。由于每一步选择两个最小权的选法不同，且两个权对应的顶点所放左右位置不同，得到的最优树可能不同，由此可能得到不同的最佳前缀码。
例如，如下 2 叉树也是一棵最优树，权为 10+20+20+35+40+60+100=285，由此最优树给出的前缀码也是满足上例要求的最佳前缀码。
0
1 0
10
1
1
0
0
01
00000
001
0001
1
0 1
0 1
100
4060
20 2025
35
10 10
15
20
10
10
5 5
00001
100 101
11
1
35
0
0
0
1
10
10
0
01
0000 10000001
1
0 1
1
100
60
40
2520
20
20
15
10
10
101055
001
1001
101
11
15
前缀码 {01,11,001,101,0000,0001,1000,1001}，各码字对应传输数字为,
11 传 0； 01 传 1； 101 传 2； 001 传 3； 1000 传 4； 1001 传 5； 0000 传 6； 0001 传 7。
四,2 叉树的遍历
访问一棵根树的每个顶点一次且仅一次称为遍历这棵树。
遍历一棵有序正则二叉树的方法主要有以下三种,
1,中序遍历法：访问次序为“左子树、树根、右子树” ；
2,前序遍历法：访问次序为“树根、左子树、右子树” ；
3,后序遍历法：访问次序为“左子树、右子树、树根” 。
例如，下图所示的 2 叉有序正则树，按中序、前序、后序遍历的结果分别如下,
((hdi)be)a(fcg); a(b(dhi)e)(cfg); ((hid)eb)(fgc)a
利用 2 叉有序正则树和确定的遍历方法可表示四则运算的算式。 一般将最高层次的运算符放在树根上，然后依次将运算符放在根子树的树根上，参加运算的数字放在树叶上，被除数、被减数总是放在左子树树叶上。例如算式 (a?(b+c)+d?e?f)÷(g+(h?i)?j)在中序遍历法下可用下列 2 叉有序正则树表示,
关于有向图的更多内容可参看文献 [1]。
[1] J?rgen Bang-Jensen and Gregory Gutin,Digraphs,Theory,Algorithms and Applications,
Springer,2001,
ih
d
gf
c
e
b
a
a
b c
d
e
f
g
h i
j
÷
+ +
+?
16
第八章习题
1,证明,() ()
vV vV
dv dv ε
+
∈∈
= =
∑∑；
2,证明：若有向图 G 中无有向圈，则 0δδ
+
= = 。
3,证明：对每个竞赛图，要么它本身是强连通的，要么可以只改变一条弧的方向而变成强连通的。
4．任何连通图 G 必有一种定向方式，使得每条有向路的长度不超过 ()GΔ 。
5,设非平凡弱连通有向图 G 满足下列条件,
（ 1） () () () ()dx dx dy dy k
++
=?=；
（ 2） () (),( ( ) {,})dv dv vVG xy
+?
=?∈?。
证明,G 中有 k 条无公共边且以 x 为起点以 y 为终点的有向路。
6,n 名棋手进行循环赛，没有出现平局，也没有出现甲胜乙、乙胜丙、丙又胜甲的情况。证明必有一人在所有比赛中全胜，也必有一人在所有比赛中全败。
7,图有 n 种昆虫，每两种必有一种能吃掉另一种，证明可以把这些昆虫排序，使得每一种昆虫能吃掉它前面的那种昆虫。
8.在一次围棋擂台赛中，双方各出 n 名选手。比赛的规则是双方先各自排定一个次序，设甲方排定的次序为
12
,,,
n
x xx,乙方排定的次序为
12
,,,
n
y yy 。
1
x 与
1
y 先比赛，胜的一位与对方输的下一位选手比赛。按这种方法进行比赛，直到有一方的最后一位选手出场比赛并且输给对方，比赛结束。问最多进行几场比赛可定其胜负（假定比赛不出现平局） 。
