乔海燕-qhy-graph2道路与回路

第二章道路与回路[有向道路]

有向图G=(V,A)中，一条有向道路指的是一个首尾相接的弧的有限非空序列

P=

a1

a2

……

ak

(k1)

其中viV(i=0..k),ajA(j=1..k)

且aj=<vj1,vj>(j=1..k)

v0

和vk分别称为P的起点和终点，k称为P的长度。在简单图中，也可记作P=(v0，v1，v2，…，vk

)或

v0

v1

v2

……

vp

2.1道路与回路[简单道路]若对任意的ij有ai

aj

，称之为简单有向道路。(没有重复边的路径)[回路]若v0=vn

，称之为封闭的。简单封闭有向道路（闭迹）称为有向回路。[初级道路]若对任意的ij有vi

vj

，称之为初级道路/基本道路。

[圈]若对任意的ij有vi

vj

而例外地v0=vn，称之为初级回路/圈。无向图具有完全类似的定义。

2.1简单道路与圈容易证明：[定理2-1]（1）基本道路是简单道路；（2）如果存在u到v的道路，则存在u到v的基本道路；

(3)n阶图的基本道路长度不超过n-1;(4)n阶图的圈的长度不超过n.2.1基本道路[定理2-2]

无向图G=(V,E)，u,v

V且uv。若u,v

之间存在两条不同的路，则G中存在一条回路。[证明]

（构造法）[定理2-3]

无向图G=(V,E)中每个顶点的度均为偶数，且至少有一个顶点不是孤立点，则

G中存在一条回路。

[证明]

（反证法）设v不是孤立点，从v出发的最长简单路径经过的顶点是v0(=v)v1…vn-1vn，则必存在0i<n使得vn=vi，否则,因为vn的度是偶数，存在与vn邻接另一个顶点u,从而得到一条更长的简单路径。矛盾！2.1道路与回路的关系[可达性]

对于有向图G=(V,A)中，若从

vi

到vj

存在一条路，则称从

vi

到vj

是可达的，或称

vi

可达vj

。对无向图G=(V,E)，结点间的可达性是对称的。[连通性]

对于无向图G=(V,E)，任意两点之间可达时，称G为连通的（连通图）。

G中的一个极大连通子图称为G的一个连通分支。一个图总是由一些连通分支构成的。G的连通分支数，记为W(G)。2.2连通性[强连通性]对于有向图G=(V,A)，如果任意两点之间相互可达，则称G为强连通的.[弱连通性]对于有向图G=(V,A),若不考虑弧的方向后得到的无向图是连通的，则称有向图G是弱连通的。2.2有向图的连通性[定理2-5]

G=(V,E)，n=|V|，若对任意u,v

V且

uv，都有：Deg(u)+Deg(v)n1，则G连通。[证明](反证法)设G可分为不连通的两部分G1=(V1,E1)和G2=(V2,E2)，选取

uV1,vV2

则Deg(u)<=|V1|-1，

Deg(v)<|V2|-1，

故Deg(u)+Deg(v)<=|V1|+|V2|-2=n-2，与Deg(u)+Deg(v)n1矛盾。注意：未加特别声明时，我们讨论的都是简单图。2.2连通的判定[定理2-11]

设Ann是G的邻接矩阵，则连接vi与vj（ij）的长度为l的路径的条数等于Al的第i行第j列的元素的数值。[证明]（数学归纳法：对l归纳）2.2图的邻接矩阵[道路矩阵]

对有向图G=(V,R)，n=|V|，构造矩阵P=(pij)nn，其中

pij

=1若vi

到vj可达0其他称P为图G的道路矩阵（或可达矩阵）。2.2道路矩阵及Warshall算法[算法]

求给定图G的道路矩阵P

设A为G的邻接矩阵，B=A+A2+A3+…+An1，由[定理2-11]，bij表示由vi至vj

，长度为1或2或…或n1的路径数目，即为由vi至vj的全部路径总和。令

pij

=1若bij

>00其他可求得G的道路矩阵P。算法复杂度O(n4)2.2道路矩阵道路矩阵可以通过二值矩阵的逻辑运算求得。[定义]

二值元素的逻辑运算：

00=0，01=10=1，11=100=0，01=10=0，11=1[定义]

二值矩阵的逻辑运算。设有矩阵A=(aij)，B=(bij)，矩阵元素值域为{0,1}，定义运算：2.2道路矩阵的计算[定义]

A(k)=A(k1)

A(k2)，A(1)=A注意A(k)与Ak

的区别[定理2-12]

设Ann是图G的邻接矩阵，若从vi

到vj存在长度为l的路，则[A(l)]ij

=1，否则[A(l)]ij

=0。[证明]对l作归纳；或直接引用[定理2-11]。2.2道路矩阵的计算[Warshall算法]

设Ann是图G的邻接矩阵，求G的道路矩阵P。PAfori=1tondoforj=1tondofork=1tondo

pjk

pjk(pji

pik)计算复杂度O(n3)2.2道路矩阵及Warshall算法初始：pij表示有无长度为1的直达路径第i次外层循环结束时：pjk表示有中间通过{v1,v2,…,vi}的路径。[例]

图G的邻接矩阵A如右，使用Warshall算法求G的道路矩阵P。[解]PA2.2道路矩阵及Warshall算法(1)i=1j

=1,2,3,4

增量方向i

=1矩阵元素处理次序：p11，

p12，

p13，

p14，

p21，

p22，

……

p31，……

p41，……，p44，2.2道路矩阵及Warshall算法如：p11

=p11(p1i

pi1)=p11(p11

p11)=0p12

=p12(p1i

pi2)=p12(p11

p12)=1p13

=p13(p1i

pi3)=p13(p11

p13)=0…………结果为2.2道路矩阵及Warshall算法2.2图上的搜索可以使用搜索的方法判断从一个顶点u到另一个顶点v是否有路径。[深度优先DFS]从顶点u出发检查其后继u1是否ｖ，如果不是，则从u1开始进行深度优先搜索；如果没有后继,则回溯，直至找到ｖ或者没有可搜索的顶点。2.2图上的搜索[广度优先BFS]从u出发，首先检查其所有的直接后继是否等于ｖ；然后依次检查这些后继的直接后继，直到找到ｖ或者没有可遍历顶点。练习：编写一个使用深度优先或者广度优先搜索判定两个点之间是否有道路的程序。[Euler回路]

若连通图G=(V,E)中存在一条简单回路（无重复边）经过G的所有边，则称该回路为G中的一条Euler回路。存在Euler回路的图称为Euler图。[定理2-6-1]

设有连通图G=(V,E)，则下述命题等价：

(1)G是一个Euler图；

(2)G的每一个顶点的度是偶数；[证明]（见戴一奇教材p16定理2.3.1）2.3Euler回路注意定理中对图的连通性的假定；Euler回路经过图的所有边一次且仅仅一次。定理对非简单图也成立；定理的证明过程给出了为一个Euler图构造Euler回路的构造算法。[定理2-7]

设连通图G=(V,E)中恰有2个顶点度为奇数，则G存在Euler道路。[证明]连接两个奇度数结点形成Euler图，再删除该边即可。2.3Euler回路[有向图的Euler回路]

若有向连通图G=(V,A)中存在一条简单有向回路经过G的所有弧，则称该回路为G中的一条Euler回路，称该图为Euler有向图。[定理2-6-2]

设连通有向图G=(V,A)，则下述命题等价：

(1)G是一个Euler有向图；

(2)G的每一个顶点的入度等于出度；[证明]（略）2.3Euler回路[Hamilton路]

若连通图G=(V,E)中存在一条初级道路（无重复顶点）经过G中每个顶点一次，则称该道路为G中的一条Hamilton路。存在Hamilton回路（圈）的图称为Hamilton图。Hamilton路经过图的所有顶点一次且仅仅一次。引入记号：G=(V,E)，SV。从G中去除S中的顶点及其关联边得到的G的子图记为GS。2.4Hamilton道路2.４Hamilton图构造Hamilton圈的简单规则：Halmilton圈含n条边；Halmilton圈正好包含每个结点的两条关联边，其他边可以删除；左图如有H圈，则必包含三个二度结点的邻接边，从而中心结点至少有三个邻接边包含在其中，故不可能有Ｈ圈。

[定理2-8]

若G=(V,E)是一个Hamilton图，SV且S，则G的子图GS的连通分支数

W(GS)|S|[证明]

记G中H-回路为C，C中包含了G中所有顶点。考察CS：每从C中去除属于S的一个顶点，连通分支数至多增加1（第一次以及当该顶点处于边缘时操作不会增加连通分支数），故

W(CS)|S|

而G可视为向C中添加边构成，故W(GS)W(CS)

所以W(GS)|S|2.４Hamilton图[例]

图G12345786令S={2,6}，则W(GS)=3。而|S|=2，即W(GS)>|S|故图G不可能是Hamilton图。134578图G-S2.４Hamilton图[例]

Petersen图。|V|=10，对任何SV，都有W(GS)S

，但Petersen图不是Hamilton图（留作习题）。Peterson图存在Hamilton道路。2.４Hamilton图删除一个或者两个顶点仍然连通，删除三个顶点最多得到两个连通分支，．．．[例]

下图不存在Hamilton圈。给图的相邻顶点标以A，B，则Hamilton圈包含相同个数的A,B.2.４Hamilton图[定理2-9]

简单图G=(V,E)，n=|V|，若对任一对不相邻顶点u,vV,uv，有deg(u)+deg(v)n1，则G中存在一条Hamilton路。[证明](见戴一奇教材p18定理2.4.1)梗概:(1)G是连通的；

(2)如果v1,v2,…,vp是一条基本道路，p<n,则可以扩展这条道路：(a)v1,vp存在{v1,…,vp}之外的邻接点，可以立即扩展；(b)v1,vp仅与{v1,…,vp}邻接，则存在包含这些点的圈。

由连通性，存在圈外的结点与圈上某结点邻接，所以，这样的圈可以扩展成更长的基本道路，直至p=n.2.４Hamilton道路[推论]

上述有deg(u)+deg(v)n时，G为Hamilton图。[证明]（见戴一奇教材p19推论2.4.1）假设v1,v2,…,vn

是Hamilton路，如果v1与vn

不邻接，设v1的邻接点集是{vi1,vi2,…,vik},则vn必与{vi1-1,vi2-1,…,vik-1}之一邻接，否则deg(vn)<=n-1-k,deg(v1)=k,deg(v1)+deg(vn)<=n-1。矛盾！2.４Hamilton道路定理及其推论给出了Hamilton图成立的充分条件，可用于对Hamilton图的肯定性判定。Hamilton图成立的充要条件尚未得到解决，是图论求解的课题之一。2.４Hamilton图[旅行商问题]

已知n个城市，任两个城市之间都有无向路相通，求一条经过所有城市一次且仅仅一次，并且总路程最短的回路。在一个边带正权的n阶无向完全图中，存在不同的Hamilton回路。旅行商问题在其中寻找一条最短的Hamilton回路。精确算法：分支与界法近似算法：最近邻法；最近插入法；2.５旅行商问题[最近邻法]

设城市之间道路长度符合三角不等式。[算法]从v1出发,找到其最近邻城市vi2,再从vi2出发…vin,将vin与v1连接得到H-回路。2.５旅行商问题[例]结果是：

v1v2v5v6v3v4v1

回路长度=407但是：

v1v2v4v6v5v3v1

回路长度=404[最近插入法]

先构成一个初始旅行圈，再选择与该圈最接近的城市扩展。扩展时可采用某种策略，如便宜算法，直至得到H-回路。2.５旅行商问题v1v1C1设v2是距C1最近的点C2v1v2设v3是距C2最近的点v1v2C3v3设v3是距C2最近的点v1v2C2v3如果w(v1,v4)-w(v1,v2)<w(v3,v4)-w(v2,v3),则连接v1,v4,否则,连接v3,v4.设v4是距C3上v2最近的点v1v2C3v3v4[网络]

有向图G=(V,A)中，给每条边a=<vi,vj>赋予一个非负实数权wij

，得到一个有向网络。[距离矩阵]

对上述网络，定义D=(dij)nn，n=|V|

wij

当<vi,vj>A

dij=其它[带权路径长度]

对上述网络，路径v1,v2,…,vk

的带权路径长度定义为2.6最短路径[两点间的最短距离]

对上述网络，结点vi到vj可达时，vi到vj的所有路径中具有最小带权路径长度者称为vi到vj的最短路径，其带权路径长度称为vi到vj的最短距离。[引理]

在有向网络中，若路径v1,v2,…,vk-1,vk是v1到vk的最短路，则路径v1,v2,…,vk-1是v1到vk-1的最短路。2.6最短路径[证明]

如果路径v1,v2

,…,vk-1

不是v1到vk-1的最短路，则v1,v2,…,vk-1

,vk不是v1到vk的最短路。2.6Dijkstra

算法[Dijkstra算法基本思想]:如果v0至u的最短路经经过v1,那么v0到v1的路径也是v0至v1的最短路经。按路径长度的递增次序，逐步产生最短路径.

设源点为v0首先求出v0为源点长度最短的一条最短路径，即具有最小权的边<v0,v>;求出源点到各个顶点下一个最短路径：设其终点是u，则v0到u的最短路径或者是边<v0,u>，或者由一条已求得的最短路径（v0…v)和边<v,u>构成；重复2直到从顶点v0到其它各顶点的最短路径全部求出为止。2.6Dijkstra

算法例：求v0其他各点的最短路径用S表示已求出最短路径的结点集初始状态：S={v0}v5v4v3v2v1v0

1006030101020

550第一条最短路径：(v0,v2)S={v0,v2}求下一条最短路径：先求v0到其他顶点vi的只经过S结点的路径：v0---v1:∞v0---v3:(v0,v2,v3)60v0---v4:(v0,v4)30v0---v5:(v0,v5)100第二条最短路径：(v0,v4)

，S={v0,v2,v4}2.6Dijkstra

算法v5v4v3v2v1v0

1006030101020

550第一条最短路径：(v0,v2)S={v0,v2}求下一条最短路径：先求v0到其他顶点vi的只经过S结点的路径：v0---v1:∞v0---v3:(v0,v2,v3)60,(v0,v4,v3)50v0---v5:(v0,v5)100,(v0,v4,v5)90第二条最短路径：

(v0,v4)

，S={v0,v2,v4}第三条最短路径：(v0,v4,v3)

，S={v0,v2,v4,v3}第四条最短路径：(v0,v4,v3,v5)

，S={v0,v2,v4,v3,v5}2.6Dijkstra

算法用S表示当前找到最短路径的终点集；引入一个辅助数组D,D[j]表示当前找到的从源点v0到终点vi

的途径S的最短路径的长度。初始状态：S={v0}若从源点v0到顶点vi有边，则D[i]为该边上的权值；若从源点v0到顶点vi

没有边，则D[i]为+一般情况下，2.6Dijkstra

算法初始化S：S[0]=1;S[1..n-1]=0；初始化D:D[j]=W<v0,vj>;在D中选择最小的路径长度D[k],并将vk加入S；修改数组D:D[j]=min{D[j],D[k]+W<vk,vj>};重复3，4n-1次，直至求得v0到所有顶点的最短路径此外,增设一个数组P记录v0到各点的最短路径：若v0，w1,…,wk,v是v0到v的最短路径，则P[v]=wk,P[wk]=w(i-1),…,P[w1]=v0.2.6Dijkstra

算法Dijkstra算法要求图上的权是非负数，否则结果不正确；Dijkstra算法同样适用于无向图，此时一个无向边次相当于两个有向边。[习题]证明Dijkstra算法的正确性。[例]2.6求单源点最短距离的Dijkstra算法

结果：U=(0,50,55,40,25)计算复杂度：O(n2)［Dijkstra算法的证明］对于任意结点v,假如在将ｖ加入Ｓ之前另外有一条更短的路径，首先经过ｘ，然后到达ｖ，那么ｘ在ｖ之前加入Ｓ，矛盾。2.7关键路径[作业网络]一项工程通常包括多个工序，这些工序间存在次序的约束：一个工序的开始的前提是某些工序已经结束。每个工序有预计的完成时间。1CS10132CS10213CS201CS101CS10224CS302CS20115CS305CS30216CS405CS3021编号课程号先修课时间2.7AOV网1CS10132CS10213CS201CS101CS10224CS302CS10215CS305CS201CS30216CS405CS3021142365311211顶点表示活动的图(AOV网)：工序用顶点表示，工序j在工序i之后开始用有向边<i,j>表示，其权表示工序i所需的时间。2.7AOV网142365311211一个工程的两个问题：工程能否顺利进行，即可否找到工序的一个线性排列：v1,v2,v3,v4,v5,v6,使得如果<vi,vj>是一条有向边，那么i<j.－拓扑排序问题。

估算工程完成所需要的最短时间。－求关键路径问题。2.7拓扑排序142365311211[拓扑排序]将一个n阶有向图G=(V,A)的所有顶点排列成一个线性序v1,v2,…,vn，使得如果<vi,vj>A,则i<j.称这样的序列为Ｇ的一个拓扑排序。例如，左图的一个拓扑排序是：1,2,3,4,6,52.7拓扑排序[定理]若有向图G=(V,A)不存在有向回路，则Ｇ存在拓扑排序。[证明]设v0是出度为零的顶点，记G1=G-v0,令v1是G1中出度为零的结点，由此反复，则序列v0,v1,…,vn是G的一个拓扑排序。

[引理]若有向图G=(V,A)不存在有向回路，则Ｇ存在入度为零和出度为零的结点。[AOV网络]有向连通网络G=(V,A)：①每一结点表示一个作业，有向边<vi,vj>表示作业vj必须在vi完成之后开始；②边<vi,vj>所带的非负实数权为完成作业vi所需时间；③作业开始条件：该作业的所有前驱作业全部完成；④无回路假设(DAG:DirectedAcyclicGraph有向无环图)