当前位置:首页 > 电子/通信 > 综合/其它 > 图论28电子科大杨春
0.810.60.40.20xt00.511.5210.500.51n1Email:yc517922@126.com图论及其应用任课教师:杨春数学科学学院0.810.60.40.20xt00.511.5210.500.51n2本次课主要内容(一)、有向图的概念与性质(二)、有向图的连通性有向图(三)、图的定向问题(四)、有向路与有向圈0.810.60.40.20xt00.511.5210.500.51n31、概念定义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,v。同时,称u为e的弧尾(起点),v为e的弧头(终点)。(一)、有向图的概念与性质注:有向图可以简单地理解为“边有方向的图”。0.810.60.40.20xt00.511.5210.500.51n4例如:有向图Dv4v3v2v1e2e1e4e3e6e5e7132,evvv3与v2分别是e1的起点与终点。定义2在一个有向图D中,具有相同起点和终点的边称为平行边。两点间平行边的条数称为该两点间的重数。例如,在上图中,e6与e7是平行边。0.810.60.40.20xt00.511.5210.500.51n5定义3在一个有向图D中,如果没有有向环和平行边,则称该图为简单有向图。定义4设D是有向图,去掉D中边的方向后得到的无向图G,称为D的基础图。又若G是无向图,给G的每条边加上方向后得到的有向图D称为G的一个定向图。e3非简单有向图Dv4v3v2v1e2e1e4e6e5e7简单有向图Dv4v3v2v1e2e1e4e6e50.810.60.40.20xt00.511.5210.500.51n6定义5设D是有向图,v是D中顶点。以v为始点的边的条数称为点v的出度,以v为端点的一个自环算1度。点v的出度记为d+(v);以v为终点的边的条数称为点v的入度,以v为端点的一个自环算1度。点v的入度记为d-(v);点v的出度与入度之和称为点v的度,记为d(v)。有向图Dv4v3v2v1e2e1e4e6e5e74()2dv4()2dv4()4dv0.810.60.40.20xt00.511.5210.500.51n7例1一个简单图有多少个定向图?答:因为每条边有2种定向方式,所以共有2m(G)种定向。例2求证:G存在一个定向图D,使得对,有()vVD()()1dvdv证明:不失一般性,设G是连通图。G中奇度顶点个数必然为偶数个,将偶数个奇数度顶点配对,然后在每一对配对顶点间连一条边得到欧拉图G1。在G1中用Fluery算法求出G的一欧拉环游C,然后顺次地在C上标上方向,由此得到C的定向图C1。在C1中,去掉添加的边后,得到G的定向图D.显然:0.810.60.40.20xt00.511.5210.500.51n8对,有()vVD()()1dvdv2、性质定理1设D=(V,E)是有向图,则:()()()()()vVDvVDdvdvmD证明:由出度与入度的定义立即可得上面等式。3、有向图的矩阵表示0.810.60.40.20xt00.511.5210.500.51n9E={e1,e2,…,em}(1)称A(D)=(aij)n×n是D的邻接矩阵,其中aij是vi为始点,vj为终点的边的条数,1≦i≦n,1≦j≦n。定义6设D=(V,E)是有向图,其中V={v1,v2,…,vn}(2)若D无环。称矩阵M=(mij)n×m是D的关联矩阵,其中1,-1(1,1),0,.ijijijvemveinjm是的始点,,是边的终点,其它0.810.60.40.20xt00.511.5210.500.51n10例1写出下面有向图D1的邻接阵和D2的关联阵。v4v3v2v1D1v4v3v2v1e1e4e3e2e5D2101000212()00000010AD21000011110()0110100011MD0.810.60.40.20xt00.511.5210.500.51n111、相关概念(二)、有向图的连通性(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是单向连通的。0.810.60.40.20xt00.511.5210.500.51n123)若D中存在一条(u,v)路和一条(v,u)路,则称u与v是双向连通的或强连通的。D1D2D3定义8设D=(V,E)是有向图。1)若D的基础图是连通的,称D是弱连通图;2)若D的中任意两点是单向连通的,称D是单向连通图;3)若D的中任意两点是双向连通的,称D是强连通图;0.810.60.40.20xt00.511.5210.500.51n13在上面三图中,D1是强连通的,D2是单向连通的,而D3仅为弱连通图。关于强连通图,我们有如下结论:定理1:有向图D=(V,E)是强连通的,当且仅当D中存在包含D中所有顶点的回路。证明:“必要性”设V(D)={v1,v2,…,vn}。由于D是强连通图,所以,对任意两点vi与vj,都存在(vi,vj)路,同时也存在(vj,vi)路。所以存在如下闭途径:v1→v2→…→vn→v1。这是一条包含D的所有顶点的回路。0.810.60.40.20xt00.511.5210.500.51n14“充分性”不失一般性,设C=v1→v2→…→vn→v1是包含D的所有顶点的一条回路。对于D的任意两点vi与vj(ij),一方面,由C可得到vi到vj的途径vi→vi+1→…→vj。另一方面,由C又可得到vj到vi的途径vj→vj+1→…vi-1→vi。所以D中任意两点是强连通的,即D是强连通图。例2说明下图D是强连通图。v1v5v4v2v3v6D解:v1v5v6v2v4v3v2v4v5v6v2v1是含D所有顶点的一条回路。0.810.60.40.20xt00.511.5210.500.51n15例3求下图D的强连通分支、单向连通分支。定义9设D`是有向图D=(V,E)的一个子图。如果D`是强连通的(单向连通的、弱连通的),且D中不存在真包含D`的子图是强连通的(单向连通的、弱连通的),则称D`是D的一个强连通分支(单向连通分支、弱连通分支)。613254879D0.810.60.40.20xt00.511.5210.500.51n16(1)D的强连通分支{1}{2,3,9,8,4,7}613254879D{5}{6}上面点集导出的子图是D的强连通分支。3248791650.810.60.40.20xt00.511.5210.500.51n17(2)D的单向连通分支D的单向连通分支就是D本身。613254879D注:求D的强、弱连通分支比较容易,求单向分支比较困难。定理2:有向图D=(V,E)的每个点位于且仅位于D的某个强(弱)连通分支中。证明:对于弱连通分支情形,命题结论是显然的。对于强连通分支情形,因为不难证明:D中顶点间的强连通关系是等价关系。该等价关系对应的等价类在D中的导出子图必然是D的一个强分支。而D的一个强分支包含的顶点也必然是该等价关系的一个等价类。0.810.60.40.20xt00.511.5210.500.51n18但是,对于单向连通分支来说,D的某个顶点,可能会分属于D的若干个单向连通分支。原因是单向连通关系不是等价关系。(三)、图的定向问题图的定向问题是有向图中的一个典型问题之一,具有广泛的应用背景。城市交通网设计问题:一座城市为某种需要,要把所有街道改为单行道,使得人们在任意两个位置都可以相互到达。如何设计单行道方向?图论建模:街道交叉口模型为图的顶点,两点连线当且仅当该两点是某街道的端点。0.810.60.40.20xt00.511.5210.500.51n19问题等价于在模型图中给出其强连通定向。对于任意一个无环图G,要对其作强连通定向,需要解决两个问题:一是强连通定向的存在性问题,二是如何定向问题。上面两个问题都已经得到解决。1、存在性问题定理3(罗宾斯,1939)非平凡连通图G具有强连通定向当且仅当G是2边连通的。罗宾斯(1915---2001),美国拓扑学家,数理统计学家。2、强连通定向算法0.810.60.40.20xt00.511.5210.500.51n202、强连通定向算法该算法采用顶点标号方法给边标上方向。设G=(V,E)是2边连通图。(1)在G中任取顶点w,令l(w)=1,L={w},U=V-{w},A=Φ;(2)在L中求点v,使得l(v)最大且满足在U中存在其邻点u。然后作有向边v,u。令l(u)=l(v)+1,L=L∪{u},U=U-{u}且A=A∪{v,u};(3)若L≠V,转(2);否则转(4);(4)对剩下的未赋予方向的边,按由标号值大的顶点指向标号值小的顶点赋予方向。0.810.60.40.20xt00.511.5210.500.51n21例4求下图G的强连通定向。v2v1v6v5v4v3v7G解:(1)取点v1,令l(v1)=1,L={v1},U={v2,v3,…,v7},A=Φ;(2)在U中取点v7,作边v1,v7。令l(v7)=l(v1)+1=2,L={v1,v7},U={v2,v3,…,v6},A={v1,v7}Gv2v1(1)v6v5v4v3V7(2)0.810.60.40.20xt00.511.5210.500.51n22(2)在L中取v7,U中取点v6,作边v7,v6。令l(v6)=l(v7)+1=3,L={v1,v7,v6},U={v2,v3,…,v5},A={v1,v7,v7,v6}Gv2v1(1)V6(3)v5v4v3v7(2)(2)在L中取v6,U中取点v5,作边v6,v5。令l(v5)=l(v6)+1=4,L={v1,v7,v6,v5},U={v2,v3,v4},A={v1,v7,v7,v6,v6,v5}Gv2v1(1)V6(3)v5(4)v4v3v7(2)0.810.60.40.20xt00.511.5210.500.51n23(2)在L中取v4,U中取点v2,作边v4,v2。令l(v2)=l(v4)+1=5,L={v1,v7,v6,v5,v2},U={v3,v4},A={v1,v7,v7,v6,v6,v5,v4,v2}Gv2(5)v1(1)V6(3)v5(4)v4v3v7(2)(2)在L中取v2,U中取点v3,作边v2,v3。令l(v3)=l(v2)+1=6,L={v1,v7,v6,v5,v2,v3},U={v4},A={v1,v7,v7,v6,v6,v5,v4,v2,v2,v3}Gv2(5)v1(1)V6(3)v5(4)v4v3(6)v7(2)0.810.60.40.20xt00.511.5210.500.51n24(2)在L中取v3,U中取点v4,作边v3,v4。令l(v4)=l(v3)+1=7,L={v1,v7,v6,v5,v2,v3,v4},U=Φ,A={v1,v7,v7,v6,v6,v5,v4,v2,v2,v3,v3,v4}Gv2(5)v1(1)V6(3)v5(4)v4(7)v3(6)v7(2)(3)U=Φ,所以,由(4),对剩下的边赋予方向。Gv2(5)v1(1)V6(3)v5(4)v4(7)v3(6)v7(2)0.81
本文标题:图论28电子科大杨春
链接地址:https://www.777doc.com/doc-69205 .html