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