第二章 道路与回路

《第二章 道路与回路》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章道路与回路2.1道路与回路[有向道路]有向图G=(V,A)中，一条有向道路指的是一个首尾相接的弧的有限非空序列P=a1a2……ak(k1)其中viV(i=0..k),ajA(j=1..k)且aj=(j=1..k)v0和vk分别称为P的起点和终点，k称为P的长度。在简单图中，也可记作P=(v0，v1，v2，…，vk)或v0v1v2……vp2.1道路与回路[简单道路]若对任意的ij有aiaj，称之为简单有向道路(simplepath,没有重复边的路径)[回路]若v0=vn，称之为封闭的。简单封闭有向道路（闭迹）称为有向简单回路

2、。[初级道路]若对任意的ij有vivj，称之为初级道路/基本道路/路径(elementryorprimary)。[圈]若对任意的ij有vivj而例外地v0=vn，称之为初级回路/圈(cycles)。无向图具有完全类似的定义。2.1简单道路与圈2.1道路与回路练习：找出上图结点1至结点9的简单道路和初级道路，1到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

3、V且uv。若u,v之间存在两条不同的路，则G中存在一条回路。[证明]（构造法）[定理2-3]无向图G=(V,E)中每个顶点的度均为偶数，且至少有一个顶点不是孤立点，则G中存在一条回路。[证明]（反证法）设v不是孤立点，从v出发的最长简单路径经过的顶点是v0(=v)v1…vn-1vn，则必存在0i

4、可达性是对称的。[连通性]对于无向图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=

5、V

6、，若对任意u,vV且uv，都有：Deg(u)+Deg(v)n1，则G连通。[证明](反证法)设G可分为不

7、连通的两部分G1=(V1,E1)和G2=(V2,E2)，选取uV1,vV2则Deg(u)<=

8、V1

9、-1，Deg(v)<

10、V2

11、-1，故Deg(u)+Deg(v)<=

12、V1

13、+

14、V2

15、-2=n-2，与Deg(u)+Deg(v)n1矛盾。注意：未加特别声明时，我们讨论的都是简单图。2.2连通的判定[定理2-11]设Ann是G的邻接矩阵，则连接vi与vj（ij）的长度为l的路径的条数等于Al的第i行第j列的元素的数值。[证明]（数学归纳法：对l归纳）2.2图的邻接矩阵[道路矩阵]对有向图G=(V,R)，n=

16、V

17、，构造矩阵P=(pij)nn，其中pij=

18、1若vi到vj可达0其他称P为图G的道路矩阵（或可达矩阵）。2.2道路矩阵及Warshall算法[算法]求给定图G的道路矩阵P设A为G的邻接矩阵，B=A+A2+A3+…+An1，由[定理2-11]，bij表示由vi至vj，长度为1或2或…或n1的路径数目，即为由vi至vj的全部路径总和。令pij=1若bij>00其他可求得G的道路矩阵P。算法复杂度O(n4)2.2道路矩阵道路矩阵可以通过二值矩阵的逻辑运算求得。[定义]二值元素的逻辑运算：00=0，01=10=1，11=100=0，01=10=0，11=1[定义]二值矩阵的逻辑运算。设有矩阵A=

19、(aij)，B=(bij)，矩阵元素值域为{0,1}，定义运算：2.2道路矩阵的计算[定义]A(k)=A(k1)A(k2)，A(1)=A注意A(k)与Ak的区别[定理2-12]设Ann是图G的邻接矩阵，若从vi到vj存在长度为l的路，则[A(l)]ij=1，否则[A(l)]ij=0。[证明]对l作归纳；或直接引用[定理2-11]。2.2道路矩阵的计算[Warshall算法]设Ann是图G的邻接矩阵，求G的道路矩阵P。PAfori=1tondoforj=1tondofork=1tondopjkpjk(pjipik)计算复杂度O(n3)2.2道路矩阵

20、及Wars