有向图

a1 a6 v0 a5
定理8.1 有向图G包含长度至少为χ-1的单向通路。 证 设A’ ∈A(D)是使D-A’不含回路的极小集合，记 D’=D-A’并设D’中最长的单向通路的长为k。当D’中以v 为起点的最长单向通路长为i-1时，给v点染颜色i，这样 得到一个(k+1)-点染色B=(V1,V2, …,Vk+1)，以下证明B是 正常的(k+1)-点染色。 首先证明：D’中任一条单向通路µ=(u, …,v)的起点u与终 点v(u≠v)具有不同颜色。 设v∈Vi，则从v出发，有长为i-1的单向通路µ’=(v1, v2,…,vi)，因为D’不含回路，所以(µ∪µ’)=(u, …,v=v1, v2, … vi)是从u出发，长度≥i的单向通路，因此u不属于Vi。
其次证明D的任一弧的起点、终点有不同颜色。 设(u,v) ∈A(D)，若(u,v)∈A(D’)，则(u,v)是D’中的一 条单向通路，因此u,v不同色；若(u,v)不属于A(D’)， 则(u,v) ∈A’，由A’的极小性D’+(u,v)必然包含单向 回路C，于是C-(u,v)是D’中的单向(v,u)-通路。因此 v,u的染色不同。 这样一来(V1,V2, …,Vk+1)是D的一个正常(k+1)-点染色， 因此k+1≥χ即k≥χ-1，这就是说D有长至少为χ-1的单 向通路。
定理8.6 设D是单向连通图，对任意的v∈ V(D)，如果 d+(v)=1(或d-(v)=1)，那么D存在唯一的单向回路。 证 从D的某一顶点出发，由于出度非0，所以可找到一 条单向链。因为D的顶点有限，且所有顶点出度为1，所 以此链终止于已经过的一个顶点w，去掉该链上首次出 现w之间的部分，得D中一条单向回路。 假定D中含有两条不同的单向回路C1,C2，那么无非是以 下三种情况：
单向回路
定理8.5 设C是有向图D的连通子图，如果C的任 意顶点v，有d+(v)=d-(v)=1，那么C是D的一条单 向回路。 证 在有向图D的基础图上，C可对应一个回路， 故在D中C上任意两邻接顶点间只有一条弧。对 C的任意顶点v，因为d+(v)=d-(v)=1，所以v既是 前一条弧的头，又是后一条弧的尾。由单向回路 的定义，得证。
比赛图
完全图的一个定向称为比赛图。N阶比赛图 可以用来表示n个选手间循环赛的胜负状态。
推论8.2 每个比赛图都有单向Hamilton通路。 证 由于比赛图的基础图是完全图。任何两点都邻接， 所以χ=p，据定理8.1，比赛图中有长度至少为p-1的 单向通路，显然它过比赛图的全部顶点，故是一条 单向Hamilton通路。
U C1 V C2
C1
U C2
C1
U C2 V
定理8.7 有向图D有单向回路的充要条件是：D有这样的 子图H，H的任意顶点v满足d+(v)>0和d-(v)<0。 证 必要性。如果D有单向回路，取这一回路为H，即得 证。 下面证充分性。对于H的顶点v，因为d+(v)>0，所以有从 此点出发的单向链。由于顶点个数有限且所有顶点入度 大于0，因此得到一条单向闭链，类似于无向图的情况， 可以找到一条单向回路。
定理8.12 连通有向图D为外(内)向树的 充要条件是仅存在一个顶点v，使d(v)=0(d+(v)=0)，而对D的所有其它顶点 vi，有d-(vi)=1(d+(vi)=1) v0 在外向树中，入度为0的点称为(始)根。 出度为0的点称为叶。其它顶点称为分 v2 枝顶点。由根到某一顶点v的单向通路 v1 的长，称为v的层数。以v0为根的外向 v 3 v5 树，也称为以v0为根的树形图，简称树 v4 形图。 v2为v3, v4, v5的父，v3, v4, v5为v2的子； v6 v2为v3, v6的先辈， v6为v2的后裔； 单向树T上任一顶点v及其后裔构成T的 一棵子树，v称为该子树的根。
练习
1、一个简单图G具有多少种定向? 答：2q个定向图 2、证明：∑d-(v)=q=∑d+(v) 证：因为有向图D中的任一弧恰有一个头和一个尾，故 上述命题成立。 3、对有向完全图，证明：∑(d-(v))2=∑(d+(v))2 ∑(d-(v))2-∑(d+(v))2=∑(d-(v)+ d+(v))(d-(v)-d+(v)) = ∑(n-1)(d-(v)-d+(v))= (n-1)∑(d-(v)-d+(v))=0
4、设D是没有单向回路的有向图 (a)证明：δ-=0； (b)证明：存在V的一个有序点列v1, v2,…, vp，使得对于 1≤i≤p，以vi为头的D的每条弧在{v1, v2,…, vi-1}中都有它的 尾。 证：(a)用反证法。若δ->0，则D中每一个顶点至少有一条 入弧，故均可沿这弧反向到达D的一个顶点，且这过程永 远不会终止。另一方面，由于D是不含单向回路的有限图， 故上述过程不可能永远进行下去，矛盾。所以δ-=0。 (b)由(a)知，存在v1，dD-(v1)=0，然后考虑D1 =D-v1，它仍 是一个不含单向回路的有向图，再由(a)知，存在v2， dD1(v2)=0；再考虑D2 = D1-v2，如此一直进行下去，共进行p 次后，得v1, v2,…, vp，按作法易知，即为所求之V(D)的排 序。
有序树
如果在单向树中规定了每一层的顶点的次序，这样 的单向树就叫做有序树。 一般地，在画出的有序树中，规定同一层的顶点次 序为从左到右，排在左边的是兄，右边是弟。 首先把根记为v，然后把v的儿子们从左到右记为v1, v2,…对vi的儿子们也是这样排列，并分别记为vi1, vi2,…，依次类推，这样顶点下标的位数就清楚地表 明了它是第几代子孙。
有向树
如果一个有向图的基础图是树，则 称为有向树。 有向树T中如果有这样一个顶点u， 使得从u到T中任一顶点v都恰有一 条单向通路，则T称为外向树(出 u 树)，u为T的始根。 有向树T中如果有这样一个顶点u， 使得从T中任一顶点v到u都恰有一 条单向通路，则T称为内向树(入 u 树)，u为T的终根。 外向树和内向树统称为单向树。
完全m元单向树
如果在单向(有序)树中，每个顶点v满足d+(v)≤m，则称这个 单向树为m元单向(有序)树。 如果每个顶点v满足d+(v)=m或d+(v)=0，则称这个为完全m元 单向(有序)树。 完全二元有序树又称为二分树。 有序树要考虑顶点的位置，我们把这种要求叫做定位。这样 的有序树就叫定位有序树。 前缀码：一明：若D是严格的有向图，则D包含一条长度至少 为max{δ-,δ+}的单向通路。 证：不失一般性，可假定max{δ-,δ+}=δ+。设P(u0,v0)是D 中的最长有向路，若它的长度小于δ+ ，则由于D是严格 的，必存在以v0为尾，头不在P(u0,v0)中的弧，从而 P(u0,v0)可继续延长，这与P(u0,v0)是最长有向路相矛盾。 所以P(u0,v0)的长充小于δ+=max{δ-,δ+}。
定理8.3 无环有向图D总存在这样一个独立集S，对V-S中任 一点v，可找到u∈S，使得从u到v有长度不超过2的单向通路。 证 对D的顶点个数p作归纳。p=1时，结论显然成立。 假设对所有顶点个数少于p的有向图，结论成立。若有向图D 顶点个数为p，设v∈V(D)，记ND+(V)={w|(v,w) ∈A(D)}称为v 的外邻接顶点集。不妨设{v}∪ND+(V)≠ V(D)，考虑D’=D({v}∪ND+(V))，由归纳假设，D’中存在一个独立集S’满足定 理要求。 若v∈ND+(V)，u∈S’，则对于ND+(V)中的点，从u出发，经长 为2的单向通路可到达。于是取S=S’即可。 若v不是S’中任何顶点的外邻接顶点，则取S={v}∪S’即可。 由归纳法原理，定理得证。 推论8.4 比赛图总包括这样一个顶点，从它出发，经过长度 不超过2的单向通路可以到达其它任何顶点。
单向通路
有向图D的单向途径指的是D的 顶点及弧交错的非空有限序列 v2 v5 v1 (v0a1v1…vk-1akvk)，v0、vk分别称为 途径的起点和终点。途径中所含 v3 v4 弧的数目k称为途径的长，单向 途径往往用顶点的序列(v0v1…vka2 v3 v1 1vk)表示。 a1 起点、终点重合的单向途径称为 a3 a8 a7 a6 单向闭途径 v0 a5 单向闭链、单向回路 v4 a4 v 5
v3
a2 a8 a4
v1 a7 v5
a1 a6 v0 a5
有向图D的顶点间的双向连通关系具有反身性、对称性 和传递性，是V(D)的一个等价关系。据此，可对V(D)进 行分类(V1,V2, …,Vm)。则D的有向子图D[Vi]都是双向连 通的，称为D的双向连通片。
v3 a3 v4
a2 a8 a4
v1 a7 v5
6、证明：若D是严格的有向图， 并且max{δ-,δ+}=k>0， 则D包含一条长度至少为k+1的单向回路。 证：不失一般性，可假定max{δ-,δ+}=δ+。由上题可知， D中最长之有向路P(u0,v0)长度≥k，由于D是严格的，从 而有d+(v0)≥k条头不相同的弧，以v0为尾。且由于P(u0,v0) 是最长的有向路，这些以v0为尾的d+(v0)条弧的头均在 P(u0,v0)上，故D中含有长度不小于k+1的有向回路。
a5 w a6
a4 a8 a7
v a3 a2 u a1
t
有向图的概念
有向图D中，以v为起点的弧的数目称 为v的出度，记为d+(v)；以v为终点的弧 的数目称为v的入度，记为d-(v) ；顶点v 的出度、入度之和，记为d(v)。 给定无向图G，对于它的每一条边，给 它的两个端点指定一个次序，就得到一 个有向图，这称为G的一个定向。 反之，对一个有向图D，把所有弧都改 换成不计方向的边，就得到了一个无向 图G，称为D的基础图。