离散数学第五版耿素云屈婉玲张立昂编著省公共课一等奖全国赛课获奖课件.pptx

1离散数学离散数学第1页2第五章第五章 图基本概念图基本概念5.1 无向图及有向图5.2 通路、回路、图连通性5.3 图矩阵表示5.4 最短路径及关键路径第2页35.1 无向图及有向图无向图及有向图123（1）123（2）abdxy（3）注：在离散数学中，我们只关心点之间是否有连线，而 不关心点位置，以及连线曲直。这是离散数学 中图与几何学中图本质区分。第3页45.1 无向图及有向图无向图及有向图一、无序积定义设A、B为任意两个集合，称a,b|aA bB为A与B无序积无序积，记作AB，并将a,b记作(a,b)。而且不论a、b是否相等，都有(a,b)=(b,a)，所以AB=BA。注：迪卡尔乘积定义与无序积定义区分。第4页55.1 无向图及有向图无向图及有向图二、无向图定义(定义5.1)一个无向图是一个有序二元组，记作G，其中(1)V称为顶点集顶点集，其元素称为顶点顶点或结点结点。(2)E为边集边集，它是无序积VV多重子集，其元素称为 无向边无向边，简称边边。123无向图G=:V=1,2,3,E=(1,1),(1,2),(2,3)。第5页65.1 无向图及有向图无向图及有向图三、有向图定义(定义5.2)一个有向图是一个有序二元组，记作D，其中(1)V称为顶点集顶点集，其元素称为顶点顶点或结点结点。(2)E为边集边集，它是迪卡尔积VV多重子集，其元素称 为有向边有向边，简称边边。123有向图D=:V=1,2,3,E=,。第6页75.1 无向图及有向图无向图及有向图 1 2 3 4 5e6e1e2e3e4e5e7(a)3e2abcde1e3e4e5e6e7(b)(1)G(1)G泛指图，泛指图，D D只能表示有向图，只能表示有向图，V(G)V(G)、E(G)E(G)分别分别 表示图表示图顶点集顶点集和和边集边集，|V(G)|V(G)|、|E(G)|E(G)|分别分别 表示图表示图顶点数顶点数和和边数边数，若，若|V(G)|=n|V(G)|=n，则称，则称G G为为 n阶图阶图。(2)(2)当当|V(G)|V(G)|与与|E(G)|E(G)|均为有限数，则均为有限数，则G G为为有限图有限图。(3)(3)在图在图G G中，若边集中，若边集E(G)=E(G)=，则称，则称G G为为零图零图，此时，此时 又若又若G G为为n n阶图，则称阶图，则称G G为为n阶零图阶零图，记作，记作N Nn n，特，特 别是称别是称N N1 1为为平凡图平凡图。顶点集。顶点集V(G)=V(G)=图为图为空图空图。第7页85.1 无向图及有向图无向图及有向图 1 2 3 4 5e6e1e2e3e4e5e7(a)3e2abcde1e3e4e5e6e7(b)(4)(4)设设e ek k=(v=(vi i,v,vj j)为无向图为无向图G=G=中一条边，称中一条边，称 v vi i,v,vj j为为e ek k端点，端点，e ek k与与v vi i(或或v vj j)是是彼此关联彼此关联。无边关联点称为无边关联点称为孤立点孤立点。若。若v vi i=v=vj j，则称，则称e ek k为为 环。若环。若v vi i v vj j，则称，则称e ek k与与v vi i(或或v vj j)关联次数关联次数为为1 1；若若v vi i=v=vj j，称，称e ek k与与v vi i关联次数关联次数为为2 2；若；若v vi i不是不是e ek k 端点，则称端点，则称e ek k与与v vi i关联次数关联次数为为0 0。(5)(5)无向图无向图G=G=，v vi i,v,vj j V V，e ek k,e,el l E E。若存在一。若存在一 条边条边e e以以v vi i,v,vj j为端点，即为端点，即e=(ve=(vi i,v,vj j)，则称，则称v vi i,v,vj j 是是彼此相邻彼此相邻，简称，简称相邻相邻；若；若e ek k，e el l最少有一最少有一 个公共端点，则称个公共端点，则称e ek k，e el l是是彼此相邻彼此相邻，简称，简称相相邻邻。第8页95.1 无向图及有向图无向图及有向图 1 2 3 4 5e6e1e2e3e4e5e7(a)3e2abcde1e3e4e5e6e7(b)(7)(7)设有向图设有向图D=D=，V V，称，称 u|uu|u V V u,E E u u 为为 后继元集后继元集，记作记作+D D()，称，称u|uu|u V V ,u E E u u 为为 前驱元集前驱元集，记作，记作-D D()。称。称+D D()-D D()为为 邻域邻域，记作，记作N ND D()。称。称N ND D()为为 闭邻闭邻 域记作域记作闭邻域闭邻域，记作，记作N ND D()。(6)(6)设无向图设无向图G=G=，V V，称，称 u|uu|u V V (u,(u,)E E u u 为为 邻域邻域，记作，记作N NG G()，并称，并称N NG G()为为 闭邻域闭邻域，记作，记作N NG G()。称。称e|ee|e E E e e与与 相关联相关联 为为 关联集关联集，记作，记作I IG G()。第9页105.1 无向图及有向图无向图及有向图四、度定义(定义5.5)设G=为一无向图，V，称 作为边端点次数之和为 度数度数，简称度度，记作dG()，在不发生混同时，简记d()。设D=为有向图，V，称 作为边始点次数之和为 出度出度，记作d+D()，简记作d+()。称 作为边终点次数之和为 入度入度，记作d-D()，简记作d-()。称d+()+d-D()为 度数度数，记作d()。度数为1顶点为悬挂顶点悬挂顶点，它所对应边为悬挂边悬挂边。第10页115.1 无向图及有向图无向图及有向图在无向图G中，令(G)=max(d()|V(G)(G)=min(d()|V(G)称(G)，(G)分别为G最大度最大度和最小度最小度。第11页125.1 无向图及有向图无向图及有向图在有向图D中，令+(D)=max(d+()|V(G)+(G)=min(d+()|V(G)-(D)=max(d-()|V(G)-(G)=min(d-()|V(G)称+(G)，+(G)，(G)，(G)分别为G最大出度、最大出度、最小出度、最大入度和最小入度最小出度、最大入度和最小入度。第12页135.1 无向图及有向图无向图及有向图五、握手定理(定理5.1-5.2)设G=为任意无向图，V=1 1,2 2,n n，|E|=m，则设D=为任意有向图，V=1 1,2 2,n n，|E|=m，则注：任图(有向图和无向图)中，奇度顶点个数是偶数。=-+=niniiiniimddmd111)()(2)(nnn且=niimd12)(n第13页145.1 无向图及有向图无向图及有向图六、度数序列定义设V=1 1,2 2,n n为图G顶点集，称d(1 1),d(2 2),d(n n)为G度数序列。1 2 3 4 5e6e1e2e3e4e5e7(a)3(a)G度数序列为(4,4,2,1,3)e2abcde1e3e4e5e6e7(b)(b)D度数序列为(5,3,3,3)第14页155.1 无向图及有向图无向图及有向图例1：(1)(3,3,2,3),(5,2,3,1,4)能称为图度数序列吗？为何？(2)已知图G中有10条边，4个3度顶点，其余顶点度数 均小于等于2，为G中最少有多少个顶点，为何？第15页165.1 无向图及有向图无向图及有向图七、度数序列是否可图化定理设非负整数列d=d1,d2,dn，则d是可图化当且仅当=niid1)2(mod0第16页175.1 无向图及有向图无向图及有向图八、多重图、简单图定义(定义5.6)在无向图中，关联一对顶点无向边假如多于1条，则称这些边为平行边平行边，平行边条数称为重数重数。在有向图中，关联一对顶点有向边假如多于1条，而且这些边始点与终点相同，则称这些边为平行边平行边。含平行边图称为多重图多重图，既不含平行边也不含环图称为简单图简单图。第17页185.1 无向图及有向图无向图及有向图九、完全图定义（定义5.）设G为n阶无向简单图，若G中每个顶点均与其余n-1个顶点相邻，则称G为n阶无向完全图阶无向完全图，简称n阶完全图阶完全图，记作Kn(n1)。设D为n阶有向简单图，若D中每个顶点均邻接到其余n-1个顶点，又邻接于其余n-1个顶点，则称D是n阶有阶有向完全图向完全图。第18页195.1 无向图及有向图无向图及有向图例2：以下图中是完全图？abdc(1)e 3 1(2)4 2 5(3)(5)（6）(4)第19页205.1 无向图及有向图无向图及有向图十、母图与子图定义（定义5.8）设G=，G=为两个图(同为无向图或同为有向图)，若VV且EE，则G是G子图子图，G为G母母图图，记作GG，又若VV或EE，则称G为G真真子图子图，若V=V，则称G为G生成子图生成子图。第20页215.1 无向图及有向图无向图及有向图例5：以下图中那些图含有子图、真子图、生成子图关系？1e1 2 3 4e2e3e4e5(1)1e4 2e5(2)1e1 2 3 4e3e4(3)2e1 3 1e2e3e4(4)2e1 3 1e3(5)2e1 1(6)第21页225.1 无向图及有向图无向图及有向图十一、补图定义（定义5.9）设G=为n阶无向简单图，以V为顶点集，以全部使G称为完全图Kn添加边组成集合为边集图，称为G补图补图，记作G。第22页235.1 无向图及有向图无向图及有向图十二、图同构定理（定义5.10）设G1=，G2=为两个无向图(两个有向图)，若存在双射函数f:V1V2，对于vi,vjV1,(vi,vj)E1(E1)当且仅当(f(vi)，f(vj)E2(E2)，而且(vi,vj)()与(f(vi),f(vj)()重数相同，则称G1与G2是同构同构，记作G1G2。第23页245.1 无向图及有向图无向图及有向图例3：(1)画出4阶3条边全部非同构无向简单图。(2)画出3阶2条边全部非同构有向简单图。第24页255.1 无向图及有向图无向图及有向图例4：以下图中那些图互为同构？abdc(1)e 3 1(2)4 2 5(3)(4)(5)（6）第25页26第五章第五章 图基本概念图基本概念5.1 无向图及有向图5.2 通路、回路、图连通性5.3 图矩阵表示5.4 最短路径及关键路径第26页275.2 通路、回路、图连通性通路、回路、图连通性一、通路与回路定义(定义5.11)给定图G=.设G中顶点和边交替序列=v0e1v1e2elvl，若满足以下条件：vi-1和vi是ei端点(在G是有向图时，要求vi-1是ei始点，vi是ei终点)，i=1,2,l，则称为顶点v0到vl通路通路。v0和vl分别称为此通路起点和终点，中边数目l称为长度，当v0=vl时，此通路称为回路回路。第27页285.2 通路、回路、图连通性通路、回路、图连通性二、简单通路、简单回路、初级通路、初级回路1)若中全部e1,e2,el互不相同，则称为简单简单通路通路。若回路中全部边互不相同，称此回路为简简单回路单回路。2)若通路全部顶点v0，v1，vl互不相同，则称此通路为初级通路初级通路。若回路中，除v0=vl外，其余顶点个不相同，全部边也各不相同，则称此回路为初级回路初级回路。第28页295.2 通路、回路、图连通性通路、回路、图连通性例1：指出以下图中通路、回路、简单通路、简单回路、初级通路、初级回路？1 2 4 3 0(1)1 2 4 3 0(2)1 2 4 3 0(3)7 8 5 6 1 2 4 3 0(4)7 8 5 6(5)1 0=5 2 3 4(6)1 0=5 2 3 4第29页305.2 通路、回路、图连通性通路、回路、图连通性三、通路相关定理(定理5.3)在n阶图G中，若从顶点vi到vj(vivj)存在通路，则从vi到vj存在长度小于等于(n-1)通路。推理：在n阶图G中，若从顶点vi到vj(vivj)存在通路，则vi到vj一定存在长度小于或等于n-1初级 通路。第30页315.2 通路、回路、图连通性通路、回路、图连通性四、回路相关定理(定理5.4)在n阶图G中，若存在vi到自己回路，则一定存在vi到本身长度小于或等于n回路。推理：在n阶图G中，若存在vi到自己回路，则一定 存在长度小于或等于n初级回路。第31页325.2 通路、回路、图连通性通路、回路、图连通性例2：无向完全图Kn(n3)中有几个非同构圈？例3：无向完全图K3顶点依次标定为a,b,c，在定义意义下K3中有过少个不一样圈？第32页335.2 通路、回路、图连通性通路、回路、图连通性五、两点之间连通性定义(定义5.12)（1）设无向图G=，u,vV，若u,v之间存在通 路，则称u,v是连通是连通，记作uv，vV，规 定vv。注：无向图中顶点之间连通关系 =|u,vV 且 u与v之间有通路 是V上等价关系。第33页345.3通路、回路、图连通性通路、回路、图连通性五、两点之间连通性定义(定义5.12)（2）设有向图D=，若从顶点u到v存在通路，则 称u可达可达v，则记作uv。要求v到本身总是可达 。若uv且vu则称vi与vj是相互可达相互可达，记 作uv，要求vv。注：有向图中顶点之间相互可达关系 =|u,vV uv vu 是V上等价关系。第34页355.2通路、回路、图连通性通路、回路、图连通性六、两点之间距离定义（1）设无向图G=，u,vV，若u,v是连通,则 称u与v之间长度最短通路为u,v之间短程线短程线，短程线长度称为u与与v之间距离之间距离，记作d(u,v)。（2）设有向图D=，u,vV，若u可达v，则称从u 到v长度最短通路为u到v之间短程线短程线，短程线 长度称为u到到v距离距离，记作d。第35页365.2通路、回路、图连通性通路、回路、图连通性注：完全图Kn(n1)都是连通图，而零图Nn(n2)都是分离图。七、连通图定义(定义5.13)（1）若无向图G是平凡图或G中任何两个顶点都是连通 ，则称G为连通图连通图，不然称G为非连通图非连通图。第36页375.2通路、回路、图连通性通路、回路、图连通性例4：指出以下图是否为连通图？1 2 4 3 0(1)1 2 4 3 0(2)7 8 5(4)1 0 2 3 4(3)1 0 2 3 4 7第37页385.2 通路、回路、图连通性通路、回路、图连通性八、连通图定义(定义5.14)（2）若D=为一个有向图。若D基图是连通图，则称D是弱连通图弱连通图，简称为连通图连通图。若vi,vjV，vivj与vjvi最少成立其一，则称D是单向连通单向连通图图。若都有vivj，则称D是强连通图强连通图。第38页395.2 通路、回路、图连通性通路、回路、图连通性例：指出以下图是否为连通图？1 2 4 3 0(1)1 2 4 3 0(2)7 8 5(3)(4)(5)第39页405.2 通路、回路、图连通性通路、回路、图连通性九、连通分支定义设无向图G=，V关于顶点之间连通关系商集V/=V1，V2，Vk，Vi为等价类，称导出子图GVi(i=1,2,k)为G连通分支，连通分支数k常记为p(G)。1 0 2 3 4 7注：若G为连通图，则p(G)=1；若G为非连通图，则p(G)1；在全部n阶无向图中，n阶零图是连通分支最多，p(Nn)=n。第40页415.2 通路、回路、图连通性通路、回路、图连通性十、点割集定义(定义5.15)设无向图G=，若存在顶点子集VV，使G删除V(将V中顶点及其关联边都删除)后，所得子图G-V连通分支数与G连通分支数满足p(G-V)p(G)，而删除V任何真子集V后，都有p(G-V)=p(G),则称V是G一个点割集点割集。若点割集中只有一个顶点v，即V=v，则称v为割点割点。第41页425.2通路、回路、图连通性通路、回路、图连通性例6：3 5 6 4 2 1e6e1e2e3e4e5第42页435.2 通路、回路、图连通性通路、回路、图连通性十一、边割集定义(定义5.15)设无向图G=，若存在边集子集EE，且E，使G删除E(将e中边从G中都删除)后，所得子图连通分支数与G连通分支数满足p(G-E)p(G)，而删除E任何真子集E后，都有p(G-E)=p(G),则称E是G一个边割集边割集。若点割集中只有一个边e，即E=e，则称v为割边或桥割边或桥。第43页445.2通路、回路、图连通性通路、回路、图连通性例：3 5 6 4 2 1e6e1e2e3e4e5第44页45第五章第五章 图基本概念图基本概念5.1 无向图及有向图5.2 通路、回路、图连通性5.3 图矩阵表示5.4 最短路径及关键路径第45页465.3 图矩阵表示图矩阵表示一、无向图关联矩阵定义设无向图G=，V=v1,v2,vn，E=e1,e2,em，令mij为顶点vi与边ej关联次数，则称(mij)nm为G关联矩阵关联矩阵，记作M(G)。1 2 4e1e2e3e4e5 3=1 0 0 0 01 1 0 0 00 0 1 1 00 1 1 1 2)(GM第46页475.3 图矩阵表示图矩阵表示一、无向图关联矩阵性质1.M(G)每列元素之和均为2。1 2 4e1e2e3e4e5 34.第j列与第k列相同，当且仅当ej 和ei是平行边。3.，即M(G)元素之和全部点度数之和m。mmdminimjijnii22)(1111=n=1 0 0 0 01 1 0 0 00 0 1 1 00 1 1 1 2)(GM2.，即M(G)第i行元素 之和为vi度数。)(1imjijdmn=第47页485.3 图矩阵表示图矩阵表示二、无向图关联矩阵性质 1 2 4e1e2e3e4e5 35.，即M(G)第i行元素 之和0 当且仅当vi为孤立点。=1 0 0 0 01 1 0 0 00 0 1 1 00 1 1 1 2)(GM01=mjijm第48页495.3 图矩阵表示图矩阵表示三、有向图关联矩阵定义设有向图D=，中无环存在，V=v1,v2,vn，E=e1,e2,em，令 则称(mij)nm为D关联矩阵关联矩阵，记作M(D)。-=终点为不关联与始点为jijijiijevevevm 1 0 1第49页505.3 图矩阵表示图矩阵表示四、有向图关联矩阵性质1.M(G)每列元素之和均为0，矩阵所 有元素之和为0。3.第i行中，正1个数等于d(vi)，负1个数等于d-(vi)。2.M(D)中，负1个数等于正1个 数，都等于边数m，这正是有向图 握手定理内容。4.平行边所对应列相同。1 2 4e4e1e2e3e5 3=1 1-1-0 0 1-1 0 0 0 0 0 1 1-1 0 0 0 1 1-)(GM第50页515.3 图矩阵表示图矩阵表示五、有向图邻接矩阵定义设有向图D=，V=v1,v2,vn，E=e1,e2,em，令 为D邻接矩阵邻接矩阵，记作A(D)，或简记为A。第51页525.3 图矩阵表示图矩阵表示六、有向图邻接矩阵性质 1 2 4 31.，于是，类似地，而 。=1 1 0 0 1 0 0 0 0 1 0 00 1 2 0)(DAmdaniininjij=+=111)1()(nnidaimiijL,2,1),(1)1(=-=nnidaimjijL,2,1),(1)1(=+=nmdaniininjij=+=111)1()(n第52页535.3 图矩阵表示图矩阵表示六、有向图邻接矩阵性质 1 2 4 32.为D中边总数，也能够 看成是长度为1通路总数。而 即M(G)第i行元素之和为vi度数。为D中环个数，即D中长 度为1回路总数。=1 1 0 0 1 0 0 0 0 1 0 00 1 2 0)(DA=niiia1)1(=ninjija11)1(第53页555.3 图矩阵表示图矩阵表示八、有向图可达矩阵定义设有向图D=，V=v1,v2,vn，令 则称(pij)nn为D可达矩阵可达矩阵，记作P。=不然可达 0 1jiijvvp第55页565.3 图矩阵表示图矩阵表示 1 2 4 3注：能够经过邻接矩阵乘法An-1生 成可达矩阵。=1 1 0 0 1 1 0 0 1 1 1 01 1 1 1P第56页57第七章第七章 图基本概念图基本概念5.1 无向图及有向图5.2 通路、回路、图连通性5.3 图矩阵表示5.4 最短路径及关键路径第57页585.4 最短路径及关键路径最短路径及关键路径一、带权图定义对于有向图或无向图G每条边附加一个实数w(e)，则称w(e)为边e上权权。G连同附加在各边上实数称为带权图带权图。常记带权图为G=。全部边权之和称为图权图权，记作W(G)。当无向边e=(vi,vj)或有向边e=时，w(e)可记为wij。第58页595.4 最短路径及关键路径最短路径及关键路径二、最短路径定义设带权图G=。中每条边带权均大于等于，u,v为G中任意两个顶点，从u到v全部通路中带权最小通路称为u到v最短路径最短路径，求两点之间最短路径问题称为最短路径问题最短路径问题。第59页60三、图带权邻接矩阵定义设图G=，V=v1,v2,vn，E=e1,e2,em，令 则称(mij)n为G带权邻接矩阵带权邻接矩阵，记作M()。=无边为有边到jijiijvvvvm 0 i=j wij5.4 最短路径及关键路径最短路径及关键路径第60页61四、最短路径算法1.S为已找到从v出发最短路径终点集合，它初始状态为空集。从v出发到图上其余各顶点vi可能到达最短路径长度初值为：disti=Mv,vi viV2.选择vj，使得distj=Min(disti|viV-S),vj就是当前求得一条从v出发最短路径终点。令S=Sj3.修改从出发到集合V-S上任一顶点vk可达最短路径长度。假如distj+Mj,kdistk则修改distk=distj+Mj,k4.重复操作2,3共n-1次。求得从v到图上其余各顶点最短路径是依路径长度递增序列。5.4 最短路径及关键路径最短路径及关键路径第61页625.4 最短路径及关键路径最短路径及关键路径五、关键路径相关定义设D=为一个有向图，vV，称+D(v)=x|xVE为v后继元集后继元集；-D(v)=x|xVE为v先驱元集先驱元集。第62页635.4 最短路径及关键路径最短路径及关键路径五、PERT图定义设D=是n阶有向带权图，满足：D是简单图；D中无回路；有一个顶点入度为，称此顶点为发点；有一个顶点出度为，称此顶点为收点；记边带权为wij，它常表示时间；则称D为PERTPERT图图。第63页645.4 最短路径及关键路径最短路径及关键路径六、最早完成时间定义自出发点(记为v1)开始沿最长路径(按权计算)抵达vi所需要时间，称vi最早完成时间最早完成时间，记作TE(vi),i=1,2,n。TE(v1)=0，vi(i1)最早完成时间可按以下公式计算：TE(vi)=maxTE(vj)+wij，i=2,3,n收点vn最早完成时间TE(vn)，就是从v1到vn最长路径权。第64页655.4 最短路径及关键路径最短路径及关键路径七、最晚完成时间定义在确保收点vn最早完成时间不增加条件下，自v1最迟抵达vi时间称为vi最晚完成时间最晚完成时间，记作TL(vi)。TL(vn)=TE(vn)，in时，vi最晚完成时间由下面公式计算：TL(vi)=min(TL(vj)-wij)，i=1,2,n-1第65页665.4 最短路径及关键路径最短路径及关键路径八、缓冲时间定义每个顶点最晚完成时间TL(vi)与最早完成时间TE(vi)差为改点缓冲时间ES(vi)。ES(vi)=TL(vi)-TE(vi)注：关键路径为缓冲时间为顶点。第66页