图论课件有向图

单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,图论及其应用,1,本次课主要内容,(,一,),、有向图的概念与性质,(,二,),、有向图的连通性,有向图,(,三,),、图的定向问题,(,四,),、有向路与有向圈,2,1,、概念,定义,1,一个有向图,D,是指一个三元组,(V(D) , E(D),D,),。其中，,V(D),是非空的顶点集合，,E(D),是不与,V(D),相交的边集合，而,D,是关联函数，它使,D,的每条边对应,D,的有序顶点对,(,不必相异,),。,如果,e,是,D,的一条边，而,u,与,v,是使得,D,(u,v)=e,的顶点，那么称,e,是由,u,连接到,v,，记为,e=,。同时，称,u,为,e,的弧尾,(,起点,), v,为,e,的弧头,(,终点,),。,(,一,),、有向图的概念与性质,注：有向图可以简单地理解为“边有方向的图”。,3,例如：,有向图,D,v,4,v,3,v,2,v,1,e,2,e,1,e,4,e,3,e,6,e,5,e,7,v,3,与,v,2,分别是,e,1,的起点与终点。,定义,2,在一个有向图,D,中，具有相同起点和终点的边称为平行边。两点间平行边的条数称为该两点间的重数。,例如，在上图中，,e,6,与,e,7,是平行边。,4,定义,3,在一个有向图,D,中，如果没有有向环和平行边，则称该图为简单有向图。,定义,4,设,D,是有向图，去掉,D,中边的方向后得到的无向图,G,，称为,D,的基础图。又若,G,是无向图，给,G,的每条边加上方向后得到的有向图,D,称为,G,的一个定向图。,e,3,非简单有向图,D,v,4,v,3,v,2,v,1,e,2,e,1,e,4,e,6,e,5,e,7,简单有向图,D,v,4,v,3,v,2,v,1,e,2,e,1,e,4,e,6,e,5,5,定义,5,设,D,是有向图，,v,是,D,中顶点。以,v,为始点的边的条数称为点,v,的出度，以,v,为端点的一个自环算,1,度。点,v,的出度记为,d,+,(v);,以,v,为终点的边的条数称为点,v,的入度，以,v,为端点的一个自环算,1,度。点,v,的入度记为,d,-,(v);,点,v,的出度与入度之和称为点,v,的度，记为,d(v),。,有向图,D,v,4,v,3,v,2,v,1,e,2,e,1,e,4,e,6,e,5,e,7,6,例,1,一个简单图有多少个定向图？,答：因为每条边有,2,种定向方式，所以共有,2,m(G),种定向。,例,2,求证：,G,存在一个定向图,D,，使得对 ，有,证明：不失一般性，设,G,是连通图。,G,中奇度顶点个数必然为偶数个，将偶数个奇数度顶点配对，然后在每一对配对顶点间连一条边得到欧拉图,G,1,。在,G,1,中用,Fluery,算法求出,G,的一欧拉环游,C,然后顺次地在,C,上标上方向，由此得到,C,的定向图,C,1,。,在,C,1,中，去掉添加的边后，得到,G,的定向图,D.,显然：,7,对 ，有,2,、性质,定理,1,设,D=(V, E),是有向图，则：,证明：由出度与入度的定义立即可得上面等式。,3,、有向图的矩阵表示,8,E=,e,1,e,2,e,m,(1),称,A(D)=(a,ij,),n,n,是,D,的邻接矩阵，其中,a,ij,是,v,i,为始点，,v,j,为终点的边的条数，,1,in,1jn,。,定义,6,设,D=(V,E),是有向图，其中,V=,v,1,v,2,v,n,(2),若,D,无环。称矩阵,M=(m,ij,),nm,是,D,的关联矩阵，其中,9,例,1,写出下面有向图,D,1,的邻接阵和,D,2,的关联阵。,v,4,v,3,v,2,v,1,D,1,v,4,v,3,v,2,v,1,e,1,e,4,e,3,e,2,e,5,D,2,10,1,、相关概念,(,二,),、有向图的连通性,(1),有向途径,(,闭途径,),、迹,(,闭迹,),和路,(,圈,),上面概念与无向图中相关概念类似。,(2),有向图中顶点间的连通性,定义,7,设,D=(V, E),是有向图，,u,与,v,是,D,中两个顶点。,1),若,D,中存在一条,(u,，,v),路，则称,u,可达,v,记为,u,v,。规定,u,u,。,2),若,D,中存在一条,(u,，,v),路或,(v, u),路，则称,u,与,v,是单向连通的。,11,3),若,D,中存在一条,(u,，,v),路和一条,(v, u),路，则称,u,与,v,是双向连通的或强连通的。,D,1,D,2,D,3,定义,8,设,D=(V, E),是有向图。,1),若,D,的基础图是连通的，称,D,是弱连通图；,2),若,D,的中任意两点是单向连通的，称,D,是单向连通图；,3),若,D,的中任意两点是双向连通的，称,D,是强连通图；,12,在上面三图中，,D,1,是强连通的，,D,2,是单向连通的，而,D,3,仅为弱连通图。,关于强连通图，我们有如下结论：,定理,1,： 有向图,D=(V,E),是强连通的，当且仅当,D,中存在包含,D,中所有顶点的回路。,证明：“必要性”,设,V(D)=,v,1,v,2,v,n,。由于,D,是强连通图，所以，对任意两点,v,i,与,v,j,都存在,(v,i, v,j,),路，同时也存在,(v,j,v,i,),路。所以存在如下闭途径：,v,1,v,2,v,n,v,1,。这是一条包含,D,的所有顶点的回路。,13,“充分性”,不失一般性，设,C= v,1,v,2,v,n,v,1,是包含,D,的所有顶点的一条回路。对于,D,的任意两点,v,i,与,v,j,(ij) ,一方面，由,C,可得到,v,i,到,v,j,的途径,v,i,v,i+1, v,j,。另一方面，由,C,又可得到,v,j,到,v,i,的途径,v,j,v,j+1,v,i-1,v,i,。所以,D,中任意两点是强连通的，即,D,是强连通图。,例,2,说明下图,D,是强连通图。,v,1,v,5,v,4,v,2,v,3,v,6,D,解：,v,1,v,5,v,6,v,2,v,4,v,3,v,2,v,4,v,5,v,6,v,2,v,1,是含,D,所有顶点的一条回路。,14,例,3,求下图,D,的强连通分支、单向连通分支。,定义,9,设,D,是,有向图,D=(V, E),的一个子图。如果,D,是强连通的,(,单向连通的、弱连通的,),且,D,中不存在真包含,D,的子图是强连通的,(,单向连通的、弱连通的,),则称,D,是,D,的一个强连通分支,(,单向连通分支、弱连通分支,),。,6,1,3,2,5,4,8,7,9,D,15,(1) D,的强连通分支,1,2, 3, 9, 8, 4, 7,6,1,3,2,5,4,8,7,9,D,5,6,上面点集导出的子图是,D,的强连通分支。,3,2,4,8,7,9,1,6,5,16,(2) D,的单向连通分支,D,的单向连通分支就是,D,本身。,6,1,3,2,5,4,8,7,9,D,注：求,D,的强、弱连通分支比较容易，求单向分支比较困难。,定理,2,： 有向图,D=(V,E),的每个点位于且仅位于,D,的某个强,(,弱,),连通分支中。,证明：对于弱连通分支情形，命题结论是显然的。,对于强连通分支情形，因为不难证明：,D,中顶点间的强连通关系是等价关系。该等价关系对应的等价类在,D,中的导出子图必然是,D,的一个强分支。而,D,的一个强分支包含的顶点也必然是该等价关系的一个等价类。,17,但是，对于单向连通分支来说，,D,的某个顶点，可能会分属于,D,的若干个单向连通分支。原因是单向连通关系不是等价关系。,(,三,),、图的定向问题,图的定向问题是有向图中的一个典型问题之一，具有广泛的应用背景。,城市交通网设计问题,:,一座城市为某种需要，要把所有街道改为单行道，使得人们在任意两个位置都可以相互到达。如何设计单行道方向？,图论建模：街道交叉口模型为图的顶点，两点连线当且仅当该两点是某街道的端点。,18,问题等价于在模型图中给出其强连通定向。,对于任意一个无环图,G,，要对其作强连通定向，需要解决两个问题：一是强连通定向的存在性问题，二是如何定向问题。,上面两个问题都已经得到解决。,1,、存在性问题,定理,3(,罗宾斯，,1939),非平凡连通图,G,具有强连通定向当且仅当,G,是,2,边连通的。,罗宾斯,(1915-2001),美国拓扑学家，数理统计学家。,2,、强连通定向算法,19,2,、强连通定向算法,该算法采用顶点标号方法给边标上方向。设,G=(V, E),是,2,边连通图。,(1),在,G,中任取顶点,w,令,l,(w)=1, L=,w,U=V-,w,A=,;,(2),在,L,中求点,v,使得,l,(v),最大且满足在,U,中存在其邻点,u,。然后作有向边,。令,l,(u)=,l,(v)+1 , L = L,u,U=U-,u,且,A=A,;,(3),若,L,V,转,(2);,否则转,(4);,(4),对剩下的未赋予方向的边，按由标号值大的顶点指向标号值小的顶点赋予方向。,20,例,4,求下图,G,的强连通定向。,v,2,v,1,v,6,v,5,v,4,v,3,v,7,G,解,: (1),取点,v,1,令,l,(v,1,)=1, L=,v,1, U=,v,2,v,3,v,7,A=,;,(2),在,U,中取点,v,7,作边,。令,l,(v,7,)=,l,(v,1,)+1=2,L =,v,1,v,7, U=,v,2,v,3,v,6, A=,G,v,2,v,1,(1),v,6,v,5,v,4,v,3,V,7,(2),21,(2),在,L,中取,v,7, U,中取点,v,6,作边,。令,l,(v,6,)=,l,(v,7,)+1=3,L =,v,1,v,7,v,6, U=,v,2,v,3,v,5, A=,G,v,2,v,1,(1),V,6,(3),v,5,v,4,v,3,v,7,(2),(2),在,L,中取,v,6, U,中取点,v,5,作边,。令,l,(v,5,)=,l,(v,6,)+1=4,L =,v,1,v,7,v,6,v,5, U=,v,2,v,3, v,4, A=, ,G,v,2,v,1,(1),V,6,(3),v,5,(4),v,4,v,3,v,7,(2),22,(2),在,L,中取,v,4, U,中取点,v,2,作边,。令,l,(v,2,)=,l,(v,4,)+1=5,L =,v,1,v,7,v,6,v,5,v,2, U=,v,3, v,4, A=, , ,G,v,2,(5),v,1,(1),V,6,(3),v,5,(4),v,4,v,3,v,7,(2),(2),在,L,中取,v,2, U,中取点,v,3,作边,。令,l,(v,3,)=,l,(v,2,)+1=6,L =,v,1,v,7,v,6,v,5,v,2,v,3, U=,v,4, A=, , , ,G,v,2,(5),v,1,(1),V,6,(3),v,5,(4),v,4,v,3,(6),v,7,(2),23,(2),在,L,中取,v,3, U,中取点,v,4,作边,。令,l,(v,4,)=,l,(v,3,)+1=7,L =,v,1,v,7,v,6,v,5,v,2,v,3,v,4, U=, A=, , , , ,G,v,2,(5),v,1,(1),V,6,(3),v,5,(4),v,4,(7),v,3,(6),v,7,(2),(3) U=,所以，由,(4) ,对剩下的边赋予方向。,G,v,2,(5),v,1,(1),V,6,(3),v,5,(4),v,4,(7),v,3,(6),v,7,(2),24,1,、有向路的性质,(,四,),、有向路与有向圈,定理,4 (,加莱,),有向图,D,中最长有向路长度下界是,证明：设,A,是,D,中使得,D,1,=D-A,不包含有向圈的极小边集合。又假定,D,1,中最长有向路的长度为,k,。,设,C=,1,2,k+1,是颜色集合。按如下方法给,D,1,中顶点着色：,当,D,1,中以,v,为起点的最长有向路的长度为,i-1,时，则给顶点,v,着上,i,色。,如此得到,D,1,的,k+1,个顶点子集：,V,1,V,2,V,k+1,25,下面证明：,V,1,V,2,V,k+1,构成,D,的色划分。,首先证明：,D,1,中任意一条有向路的两个端点一定着了不同颜色。,设,P,是,D,1,中的任意一条,(u, v),路。设,v,着了,i,色，则以,v,为起点的最长路,Q,的长度为,i-1,。因为,D,1,中没有有向圈，所以，,u,不可能在,Q,上，于是,P,的长度至少为,i,这表明,u,没有着,i,色。,其次证明：,D,中任一有向边的端点着了不同颜色。,事实上：设,e=uv,是,D,的任意一条边。若,e,是,D,1,中边，则因,e,是路。由前面证明，,e,的端点着了不同色；,26,设,e=uv,是,D,的任意一条边。若,e,不是,D,1,中边，则因,A,的极小性，,D+uv,必然有唯一圈,C,， 显然，,C-uv,是,D,1,中的一条,(u, v),路，所以，,u,与,v,着了不同色。,由此，证明了定理。,2,、有向圈的性质,定理,5,设,D=(V,E),是有向图。,(1),若,D,中存在子图,H,使得对任意的,v,V(H),均有,d,+,(v)0,(,或,d,-,(v)0),则,D,中存在有向圈。,(2),若,D,连通，且对任意的,v,V(D),均有,d,+,(v)=1(,或,d,-,(v)=1),则,D,中存在唯一有向圈。,27,定理,6,设,D=(V,E),是有向图。,D,中存在有向欧拉环游，当且仅当,D,连通且每个点的出度和入度相等；,D,中存在有向欧拉迹，当且仅当,D,连通且除了两个点外，每个点的出度和入度相等。而这两个点中，一个点的入度比出度大,1,，另一个点出度比入度大,1.,在各种比赛中，循环比赛是常见形式，即对与对之间都要进行比赛。,循环比赛的结果可以用所谓的“竞赛图”来表示。,u,队战胜了,v,队，则由点,u,向,v,画一条有向边。,显然， “竞赛图”是完全图的一种定向图。,28,n,阶完全图的定向有多少不同方式？,2,n,种！当,n=12,时，有,1540,亿个。,定理,7,竞赛图中存在有向,H,圈。,29,作业,P256-259,习题,9,：,1,，,2,，,5,，,7,，,8,，,11,，,12,，,13,30,Thank You !,31,