图论有向图.pptx

1 图论及其应用图论及其应用应用数学学院应用数学学院2本次课主要内容本次课主要内容(一一)、有向图的概念与性质、有向图的概念与性质(二二)、有向图的连通性、有向图的连通性有向图有向图(三三)、图的定向问题、图的定向问题(四四)、有向路与有向圈、有向路与有向圈3 1、概念、概念 定义定义1 一个有向图一个有向图D是指一个三元组是指一个三元组(V(D),E(D),D D)。其中，。其中，V(D)V(D)是非空的顶点集合，是非空的顶点集合，E(D)E(D)是不与是不与V(D)V(D)相交相交的边集合，而的边集合，而D是关联函数，它使是关联函数，它使D的每条边对应的每条边对应D的有的有序顶点对序顶点对(不必相异不必相异)。如果如果e是是D的一条边，而的一条边，而u与与v是使得是使得D(u,v)=e的顶点，的顶点，那么称那么称e是由是由u连接到连接到v，记为，记为e=。同时，称。同时，称u为为e的的弧尾弧尾(起点起点),v为为e的弧头的弧头(终点终点)。(一一)、有向图的概念与性质、有向图的概念与性质 注：有向图可以简单地理解为注：有向图可以简单地理解为“边有方向的图边有方向的图”。4 例如：例如：有向图有向图Dv4v3v2v1e2e1e4e3e6e5e7 v3与与v2分别是分别是e1 的起点与终点。的起点与终点。定义定义2 在一个有向图在一个有向图D中，具有相同起点和终点的边中，具有相同起点和终点的边称为平行边。两点间平行边的条数称为该两点间的重数。称为平行边。两点间平行边的条数称为该两点间的重数。例如，在上图中，例如，在上图中，e6与与e7是平行边。是平行边。5 定义定义3 在一个有向图在一个有向图D中，如果没有有向环和平行边，中，如果没有有向环和平行边，则称该图为简单有向图。则称该图为简单有向图。定义定义4 设设D是有向图，去掉是有向图，去掉D中边的方向后得到的无向中边的方向后得到的无向图图G，称为，称为D的基础图。又若的基础图。又若G是无向图，给是无向图，给G的每条边的每条边加上方向后得到的有向图加上方向后得到的有向图D称为称为G的一个定向图。的一个定向图。e3非简单有向图非简单有向图Dv4v3v2v1e2e1e4e6e5e7简单有向图简单有向图Dv4v3v2v1e2e1e4e6e56 定义定义5 设设D是有向图，是有向图，v是是D中顶点。以中顶点。以v为始点的边的条为始点的边的条数称为点数称为点v的出度，以的出度，以v为端点的一个自环算为端点的一个自环算1度。点度。点v的出度的出度记为记为d+(v);以以v为终点的边的条数称为点为终点的边的条数称为点v的入度，以的入度，以v为端点为端点的一个自环算的一个自环算1度。点度。点v的入度记为的入度记为d-(v);点点v的出度与入度之和称为点的出度与入度之和称为点v的度，记为的度，记为d(v)。有向图有向图Dv4v3v2v1e2e1e4e6e5e77 例例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)是有向图，则：是有向图，则：证明：由出度与入度的定义立即可得上面等式。证明：由出度与入度的定义立即可得上面等式。3、有向图的矩阵表示、有向图的矩阵表示9 E=e1,e2,em (1)称称A(D)=(aij)nn是是D的邻接矩阵，其中的邻接矩阵，其中aij是是vi为始点，为始点，vj为终点的边的条数，为终点的边的条数，1 i n,1 j n。定义定义6 设设D=(V,E)是有向图，其中是有向图，其中V=v1,v2,vn (2)若若D无环。称矩阵无环。称矩阵M=(mij)nm是是D的关联矩阵，其中的关联矩阵，其中10 例例1 写出下面有向图写出下面有向图D1的邻接阵和的邻接阵和D2的关联阵。的关联阵。v4v3v2v1D1v4v3v2v1e1e4e3e2e5D211 1、相关概念、相关概念(二二)、有向图的连通性、有向图的连通性 (1)有向途径有向途径(闭途径闭途径)、迹、迹(闭迹闭迹)和路和路(圈圈)上面概念与无向图中相关概念类似。上面概念与无向图中相关概念类似。(2)有向图中顶点间的连通性有向图中顶点间的连通性 定义定义7 设设D=(V,E)是有向图，是有向图，u与与v是是D中两个顶点。中两个顶点。1)若若D中存在一条中存在一条(u，v)路，则称路，则称u可达可达v,记为记为uv。规定规定u u。2)若若D中存在一条中存在一条(u，v)路或路或(v,u)路，则称路，则称u与与v是单是单向连通的。向连通的。12 3)若若D中存在一条中存在一条(u，v)路和一条路和一条(v,u)路，则称路，则称u与与v是是双向连通的或强连通的。双向连通的或强连通的。D1D2D3 定义定义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)=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是强连通图。是强连通图。v1v5v4v2v3v6D 解：解：v1v5v6v2v4v3v2v4v5v6v2v1是含是含D所有顶点的一条回路。所有顶点的一条回路。15 例例3 求下图求下图D的强连通分支、单向连通分支。的强连通分支、单向连通分支。定义定义9 设设D是是有向图有向图D=(V,E)的一个子图。如果的一个子图。如果D是强是强连通的连通的(单向连通的、弱连通的单向连通的、弱连通的),且且D中不存在真包含中不存在真包含D的的子图是强连通的子图是强连通的(单向连通的、弱连通的单向连通的、弱连通的),则称则称D是是D的一的一个强连通分支个强连通分支(单向连通分支、弱连通分支单向连通分支、弱连通分支)。613254879D16 (1)D的强连通分支的强连通分支12,3,9,8,4,7613254879D56 上面点集导出的子图是上面点集导出的子图是 D的强的强连通分支。连通分支。32487916517 (2)D的单向连通分支的单向连通分支D的单向连通分支就是的单向连通分支就是D本身。本身。613254879D注：求注：求D的强、弱连通分支比较的强、弱连通分支比较容易，求单向分支比较困难。容易，求单向分支比较困难。定理定理2：有向图有向图D=(V,E)的每个点位于且仅位于的每个点位于且仅位于D的某个的某个强强(弱弱)连通分支中。连通分支中。证明：对于弱连通分支情形，命题结论是显然的。证明：对于弱连通分支情形，命题结论是显然的。对于强连通分支情形，因为不难证明：对于强连通分支情形，因为不难证明：D中顶点间的强中顶点间的强连通关系是等价关系。该等价关系对应的等价类在连通关系是等价关系。该等价关系对应的等价类在D中的导中的导出子图必然是出子图必然是D的一个强分支。而的一个强分支。而D的一个强分支包含的顶的一个强分支包含的顶点也必然是该等价关系的一个等价类。点也必然是该等价关系的一个等价类。18 但是，对于单向连通分支来说，但是，对于单向连通分支来说，D的某个顶点，可能会分的某个顶点，可能会分属于属于D的若干个单向连通分支。原因是单向连通关系不是等的若干个单向连通分支。原因是单向连通关系不是等价关系。价关系。(三三)、图的定向问题、图的定向问题 图的定向问题是有向图中的一个典型问题之一，具有广图的定向问题是有向图中的一个典型问题之一，具有广泛的应用背景。泛的应用背景。城市交通网设计问题城市交通网设计问题:一座城市为某种需要，要把所有街一座城市为某种需要，要把所有街道改为单行道，使得人们在任意两个位置都可以相互到达。道改为单行道，使得人们在任意两个位置都可以相互到达。如何设计单行道方向？如何设计单行道方向？图论建模：街道交叉口模型为图的顶点，两点连线当且图论建模：街道交叉口模型为图的顶点，两点连线当且仅当该两点是某街道的端点。仅当该两点是某街道的端点。19 问题等价于在模型图中给出其强连通定向。问题等价于在模型图中给出其强连通定向。对于任意一个无环图对于任意一个无环图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)+1,L=Lu,U=U-u且且A=A ;(3)若若LV,转转(2);否则转否则转(4);(4)对剩下的未赋予方向的边，按由标号值大的顶点指向标对剩下的未赋予方向的边，按由标号值大的顶点指向标号值小的顶点赋予方向。号值小的顶点赋予方向。21 例例4 求下图求下图G的强连通定向。的强连通定向。v2v1v6v5v4v3v7G 解解:(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=Gv2v1(1)v6v5v4v3V7(2)22 (2)在在L中取中取v7,U中取点中取点v6,作边作边。令。令l(v6)=l(v7)+1=3,L=v1,v7,v6,U=v2,v3,v5,A=,Gv2v1(1)V6(3)v5v4v3v7(2)(2)在在L中取中取v6,U中取点中取点v5,作边作边。令。令l(v5)=l(v6)+1=4,L=v1,v7,v6,v5,U=v2,v3,v4,A=,Gv2v1(1)V6(3)v5(4)v4v3v7(2)23 (2)在在L中取中取v4,U中取点中取点v2,作边作边。令。令l(v2)=l(v4)+1=5,L=v1,v7,v6,v5,v2,U=v3,v4,A=,Gv2(5)v1(1)V6(3)v5(4)v4v3v7(2)(2)在在L中取中取v2,U中取点中取点v3,作边作边。令。令l(v3)=l(v2)+1=6,L=v1,v7,v6,v5,v2,v3,U=v4,A=,Gv2(5)v1(1)V6(3)v5(4)v4v3(6)v7(2)24 (2)在在L中取中取v3,U中取点中取点v4,作边作边。令。令l(v4)=l(v3)+1=7,L=v1,v7,v6,v5,v2,v3,v4,U=,A=,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)25 1、有向路的性质、有向路的性质(四四)、有向路与有向圈、有向路与有向圈 定理定理4(加莱加莱)有向图有向图D中最长有向路长度下界是中最长有向路长度下界是 证明：设证明：设A是是D中使得中使得D1=D-A不包含有向圈的极小边不包含有向圈的极小边集合。又假定集合。又假定D1中最长有向路的长度为中最长有向路的长度为k。设设C=1,2,k+1是颜色集合。按如下方法给是颜色集合。按如下方法给D1中中顶点着色：顶点着色：当当D1中以中以v为起点的最长有向路的长度为为起点的最长有向路的长度为i-1时，则给时，则给顶点顶点v着上着上i色。色。如此得到如此得到D1的的k+1个顶点子集：个顶点子集：V1,V2,Vk+126 下面证明：下面证明：V1,V2,Vk+1构成构成D的色划分。的色划分。首先证明：首先证明：D1中任意一条有向路的两个端点一定着了中任意一条有向路的两个端点一定着了不同颜色。不同颜色。设设P是是D1中的任意一条中的任意一条(u,v)路。设路。设v着了着了i色，则以色，则以v为为起点的最长路起点的最长路Q的长度为的长度为i-1。因为。因为D1中没有有向圈，所中没有有向圈，所以，以，u不可能在不可能在Q上，于是上，于是P的长度至少为的长度至少为i,这表明这表明u没有没有着着i色。色。其次证明：其次证明：D中任一有向边的端点着了不同颜色。中任一有向边的端点着了不同颜色。事实上：设事实上：设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，1331Thank You!