离散数学图的基本概论.ppt

图的基本概念,第 八 章,计算机科学广泛应用于运筹学，信息论，控制论，网络理论，化学生物学，物理学。原因在于这些学科的许多实际问题和理论问题可以概括为图论。第八、九章介绍与计算机科学关系密切的图论内容及其在实际中的应用。,8.1 无向图及有向图,称a,b|aAbB 为A与B的无序积，记作：A&B。,习惯上，无序对a,b改记成(a,b),有序组(a,b)均用,无序积：设A，B为二集合，,一、基本图类及相关概念,1.无向图,无向图：无向图G是一个二元组，其中,(1)V是一个非空集 顶点集V(G)，每个元素为顶点或结点；,(2)E是无序积V&V的可重子集(元素可重复出现)，E 边集E(G)，E中元素称为无向边。,v4,实际中，图是画出来的，画法：用小圆圈表示V中的每一个元素，如果(a,b)E，则在顶点a与b之间连线段。,如：,a,d,c,b,e1,e1,e2,e3,e4,e5,e6,e1,e2,e3,e4,e5,e6,v1,v2,v3,v5,有向图：有向图D是一个二元组，其中,(1)V是非空集 顶点集 V(D),(2)E是笛卡尔积VV的可重子集，其元素为有向边,实际中，画法同无向图，只是要根据E中元素的次序，由第一元素用方向线段指向第二元素。,2.有向图,有限图：V，E均为有穷集合,零 图：E,平凡图：E 且|V|=1,(n,m)图：|V|=n 且|E|=m,顶与边关联：如果ek=(vi,vj)E，称ek与vi关联，或ek与vj关联。,3.相关概念,顶与顶相邻：如果ek=(vi,vj)E，称vi与vj相邻；,环：ek=中，若 vi=vj，则ek称为环。,边与边相邻：如果ek和ei至少有一个公共顶点关联，则称ek与ei相邻。,若ek为有向边，则称vi邻接到vj,vj邻接于vi。,孤立点：无边关联的顶点。,平行边：无向图中，关联一对结点的无向边多于一条，平行边的条数为重数；,多重图：包含平行边的图。,有向图中，关联一对顶点的无向边多于一条，且始、终点相同。,简单图：既不包含平行边又不包含环的图。,度：(1)在无向图G=中，与顶点v(vV)关联的边的数目(每个环计算两次)，记作：d(v)。,二、度,(2)在有向图D=中，以顶点v(vV)作为始点的边的数目，称为该顶点的出度，记作：d+(v)；,出度与入度之和，称为顶点v的度：,度是图的性质的重要判断依据。,d(v)=d+(v)+d(v),以顶点v作为终点的边的数目，称为该顶点的入度，记作：d(v)。,最大度：(G)=max d(v)|vV,最小度：(G)=min d(v)|vV,度与边数的关系：在任何图中，顶点度数的总和等于边数之和的两倍。,握手定理的推论：任何图中，度为奇数的顶点个数一定为偶数。,(握手定理),出度与入度的关系：在有向图中，各顶点的出度之和等于各顶点的入度之和。,度数序列：设V=v1,v2,vn为图G的顶点集，,称(d(v1),d(v2),d(vn)为G的度数序列。,度数序列之和必为偶数(?)。,例8.1(3,3,2,3)，(5,2,3,1,4)能成为图的度数序列吗？为什么？,解：由于这两个序列中，奇数个数均为奇数，由握手定理知，它们不能成为图的度数序列。,例8.2 已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？为什么？,解：图中边数 m=10，由握手定理知，G中各顶点度数之和为20，,4个3度顶点占去12度，还剩8度，,若其余全是2度顶点,则需要4个顶点来占用8度，所以G至少有8个顶点。,正则图：各顶点的度都相同的图为正则图；,各顶点的度均为k的图为k次正则图。,完全图：,(1)设G=是n阶的无向简单图，如果G中任何一个顶点都与其余n1个顶点相邻，则G为无向完全图，记作：Kn。,三、正则图与完全图,(2)设D=是n阶的有向简单图，如果D中任意顶点u，vV(uv)，即有有向边，又有有向边，则称D为n阶有向完全图。,如：,四、子图与母图：,(1)G=，G=,若VV，EE，则G是G的母图，G是G的子图，记作：G G。,(2)若GG 且 V=V，则G是G的生成子图。,(3)设V1V，且V1，以V1为顶点集，以2端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图。,(4)设E1E，且E1，以E1为顶点集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。,例8.3 列举下图的一些子图、真子图、生成子图、导出子图。,e3,e1,e2,e4,e5,v3,v4,v1,v2,解：自己对照定义做一做！,(1)子图：子图的定义？举例,(2)真子图：举例,(3)生成子图：定义？举例,(4)导出子图：定义？举例,补图：给定一个图G=，以V为顶点集，,以所有能使G成为完全图的添加边组成边集的图。记作：G,五、补图,如:,相对补图：设GG,如果另一个图G=，满足(1)E=E E,(2)V中仅包含E中的边所关联的结点。,则G是子图G相对于G的补图。,图同构：对于G=，G=，如果存在 g:VV 满足：,(1)任意边e=(vi,vj)E，当且仅当e=(g(vi),g(vj)E,(2)e与e的重数相同,则说G G,由于同构图顶点之间一一对应，边之间一一对应，关联关系对应相同，所以可以看成同一个图。,六、同构图,例8.4 画出4个顶点3条边的所有可能非同构的无向简单图。,解：直观上容易看出，下面三个图是4个顶点3条边的所有非同构的无向简单图。,例8.5 画出3个顶点2条边的所有可能非同构的有向简单图。,解：3个顶点2条边的无向简单图只有一个：,由这个图可派生出下列4个非同构的有向简单图：,课堂练习：画出4个顶点4条边的无向简单图。,8.2 通路、回路、图的连通性,通路与回路：给定图G=，,设G中顶点与边的交替序列=v0 e1 v1 e2 el vl 满足：vi1vi是ei的端点，(G为有向图时,要求vi1,vi分别为ei的始点、终点)，i=1,2,l，则为顶点v0到vl的通路。,中边的数目l称为的长度。,v0=vl时，称为回路。,一、通路与回路的概念,简单通路：=v0 e1 v1 e2 ek vk为通路且边e1 e2 ek 互不相同，又称之为迹，可简用v0 v1 vk 来表示。,简单回路(v0=vk)又称为闭迹。,初级通路或基本通路：=v0 e1 v1 e2 ek vk为通路且顶点v0 v1 vk 互不相同。,初级通路一定是简单通路，但简单通路不一定是一条初级通路。,基本回路：v0=vk。,例8.6 就下面两图列举长度为5的通路，简单通路，回路，简单回路，再列举长度为3的基本通路和回路。,v1,e1,e4,v2,v3,v4,v5,e3,e5,e2,e7,e6,(1),(2),v5,v1,e2,e5,v2,v3,v4,e1,e7,e3,e8,e6,e4,解：试对照定义，自己做一做！如：,v1,(1)中 v1e1v2e2v5e3v1e1v2e4v3 为v1到v3的通路；,v1e1v2e4v3e5v4e7v5e3v1 为v1到v1的一条简单回路；,v1e1v2e4v3e5v4e6v2e2v5 为v1到v5的一条简单通路。,e1,e4,v2,v3,v4,v5,e3,e5,e2,e7,e6,(1),(2)中 v1e2v2e5v3e7v4 v1到v4的长度为 了的基本通路；,v1e2v2e3v5e1v1 是v1到v1的长度为了的基本回路。,(2),v5,v1,e2,e5,v2,v3,v4,e1,e7,e3,e8,e6,e4,二、通路与回路的性质：,(1)在一个n阶图中，如果从顶点vi到vj(vivj)存在通路，则从vi到vj存在长度小于或等于n1的通路。,如果Ln1，则此通路的顶点数L+1n，从而必有顶点vs，它在序列中不止出现一次，即有序列vi vs vs vj。,证明：设vi vk vj为vi到vj的长度为L的一条通路，则序列中必有L+1个顶点。,在路中去掉vs到vs的这些边，至少去掉一条边后仍是vi到vj的一条通路。,此通路比原来,如此重复下去，必可得到一条从vi到vj的不多于n1条边的通路。,通路的长度至少少1。,(2)在n阶图中，如果从vi到vj(vivj)存在通路，则必存在从vi到vj 的长度小于等于 n1的基本通路。,(3)在n阶图中，如果存在从vi到自身的回路，则从vi 到自身存在长度等于n的回路。,(4)在n阶图中，如果从vi到自身存在一条简单回路，则从vi 到自身存在长度等于n的初级回路。,两顶点连通：u,v为无向图G的两个顶点，u到v存在一条通路。,连 通 图：G 中任何两个顶点是连通的；否则是分离图。,三、图的连通性,连通性的性质：无向图中顶点之间的连通关系是顶点集V上的等价关系。,(1)自反性：由于规定任何顶点到自身总是连通的；,证明：,(2)对称性：无向图中顶点之间的连通是相互的；,(3)传递性：由连通性的定义可知。,连通分支：无向图G中每个划分块称为G的一个连通分支，p(G)表示连通分支的个数。p(G)=1为连通图。,点割集：无向图G=为连通图，如果VV，且在G中删除V中所有顶点(包括与该顶点关联的边)后所得子图是不连通的或是平凡图，而删除V中任何真子集中的顶点时，所得子图仍连通，则V是G的点割集。,如果点割集中只有一个顶点，该点为割点。,四、连通图的连通度,点连通度：G为无向连通图，记k(G)=min|V|V是G的点割集，称k(G)为G的点连通度。,由定义知，点连通度即使G不连通的需删除顶点的最少数目。,完全图Kn的连通度k(G)=n1。,存在割点的连通图连通度为1，,分离图的连通度为0；,边割集：设无向图G=连通，边集EE，在G中删除E中所有边后所得子图不连通，而删除E中的任何子集中的边后，所得子图仍连通，则E为G的边割集。,如果边割集中只有一边时，该边为割边(或桥),边连通度：设G为无向连通图，记(G)=min|E|E是G的边割集，(G)为G的边连通度。,连通度的性质：k(G)(G)(G),五、有向图的连通性：,(1)如果有向图 D=中所有有向边的方向去掉后所得图为无向连通图，则说D为弱连通图。,(2)u,vV，如果存在u到v的一条通路，则说u可达v。,(3)弱连通图中，任何一对顶点之间，至少有一顶点可达另一个顶点，则 是单向连通的；,任何两个顶点之间互相可达，称强连通。,有向连通图的性质：,(1)强连通一定单向连通，单向连通一定弱连通。反过来都不成立。,(2)有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次。,(充分性)如果D中存在回路C，它经过D中的每个顶点至少一次，则D中的任意两个顶点都在回路中，所以，D中任意两个顶点都是可达的，因而D是强连通的。,证明：,因为vi可达vi+1,i=1,2,，n1，让这些通路首尾相连，,(2)有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次。,(必要性)D是强连通的，则D中任何两个顶点都是可达的。,则得一回路。显然每个顶点在回路中至少出现一次。,证明：,所以vi到vi+1存在通路，,不妨设D中的顶点,为v1,v2,vn，,且vn到v1也存在通路，,8.3 图的矩阵表示,邻接矩阵：设G=是一个简单图，它有n个顶点，V=v1,v2,vn，令,aij=,1 E(或(vi,vj)E),0 E(或(vi,vj)E),称A(G)=(aij)为G的邻接矩阵。,一、邻接矩阵及其性质,邻接矩阵的特性：在无向图中：,(1)邻接阵是对称阵；,(2)同一行或者同一列的元素和为对应顶点的度数,(3)矩阵中所有元素的和为边数的2倍,在有向图中：,(1)同一行的元素和为对应顶点的出度,(2)同一列的元素和为对应顶点的入度,(3)aij=2 m(边的数目),邻接矩阵可推广到多重图或带权图，这时令aij为vi到vj的边的重数或边上的权值W(vi,vj)。,邻接阵多用于有向图。,关联矩阵：,(1)设G=为(n,m)无向图,V=v1,v2,vn,E=e1,e2,em,令：,mij=,1,0,称M(G)=(mij)nxm为G的关联矩阵。,vi 关联 ej,vi 不关联 ej,二、关联矩阵及其性质,(2)设D=是有向图且无环，令：,mij=,1,0,则称M(D)=(mij)nxm为D的关联矩阵。,1,D中 vi 是 ej 的始点,vi 与 ej 不关联,vi 是 ej 的终点,无向图的关联矩阵的性质：,(握手定理),有向图的关联矩阵的性质：,由mij的定义知,通路数与回路数的矩阵算法：,(1)设A是有向图D的邻接矩阵，V=v1,v2,vn，Al(l1)中元素aij(l)为vi到vj长度为l的通路数,通路总数,回路数,三、应用,1.求通路数与回路数,(2)设A是有向图D的邻接矩阵，B1=A，B2=A+A2,，Br=A+A2+Ar，则Br中元素bij(r)为D中vi到vj长度小于等于 r 的通路数，,2.求可达矩阵,可达矩阵：,设D=为一有向图，V=v1,v2,vn，令,pij=,1,0,i j,pii=1 i=1,2,n,称(pij)nxn 为D的可达矩阵。,vi 可达 vj,否则,例.求下图的可达矩阵，判断它是否为强连通图？,V1,V4,V2,V3,V5,解：1.写出邻接矩阵,2.计算 A2,A3,A4,A5.,3.计算 B=A+A2+A3+A4+A5,并求出,可达矩阵的求法：由邻接矩阵A计算A2,A+A2,A+A2+A(n1)=B=(bij(n1)nn,pij=,1 bij(n1)0,0 bij(n1)=0,则 i j,pii=1,即得可达矩阵 P(D)=(pij)nxn,8.4 最短路径问题,带权图：对于有向图或无向图的每条边附加一个实数w(e)，则得带权图。,如果G1是带权图G的子图，称,w(e)为边e上的权(当e=时，权记作wij)，记作：G=,一、带权图及其最短路径问题,G=为带权图，且G中各边带的权均大于等于0，从顶点u到顶点v的所有通路中求带权最小的通路问题，称为最短路径问题。,最短路径问题：,如果v1v2 vn1vn是v1到vn的最短路径，则v1v2 vn1也必然是v1从到vn1的最短路径。,求最短路径的标号法的基本思想：,标号法：(1)符号说明,(i)li(r)*为顶点v1到顶点vi最短路径的权,(ii)lj(r)为v1到vj最短路径权的上界，如果vj获得lj(r)，称vj在第r步获得t标号lj(r)(r0),如果顶点vi获得了标号li(r)*，称vi在第r步获得p标号li(r)*,(iii)Pr=v|v已获得p标号，称之为第r步通过集(r0),(iv)Tr=V Pr 称之为第r步未通过集(r0),二、求最短路径问题的标号法,(2)算法：,开始，r0，v1获p标号：l1(0)*=0，P0=v1，T0=Vv1，vj(j1)的t标号：,lj(0)=w1j=,w1j 0 v1与vj相邻,v1与vj 不相邻,修改通过集和未通过集：Pr=Pr1vi，Tr=Tr1vi，,step1.求下一个p标号顶点,顶点vi处，表明vi获得p标号。,查Tr：若Tr=，则算法结束，否则转step2,将lj(r)*标在相应,step2.修改Tr中各顶点的t标号,lj(r)=minlj(r1),li(r)*+wij，li(r)*是刚刚获得p标号顶点的p标号。,令r r+1，转step1。,例8.7 求下图中顶点v0与v5之间的最短路径,v0,v2,v1,v4,v3,v5,1,2,1,4,7,5,3,2,6,解：利用标号法算法解此题,开始，r0，v0获 p标号：l0(0)*=0,l1(0)=w01=1,通过集P0=v0，未通过集T0=v1，v2，v3，v4，v5，,l2(0)=w02=4,l4(0)=l5(0),l3(0)=w03=,未通过集的 t 标号：,第一步：r=1，计算=l1(1)*=1，所以i=1，,P1=v0,v1，T1=v2,v3,v4,v5,修改未通过集的t标号：,l2(1)=minl2(0),l1(1)*+w12=min4,3=3,l3(1)=minl3(0),l1(1)*+w13=min,8=8,l4(1)=minl4(0),l1(1)*+w14=6,l5(1)=minl5(0),l1(1)*+w15=,vi获 p标号l1(1)*，,修改通过集与未通过集:,修改通过集与未通过集 P2=v0,v1,v2，T2=v3,v4,v5,修改未通过集的t标号：,l3(2)=minl3(1),l2(2)*+w23=min8,3+=8,l4(2)=minl4(1),l2(2)*+w24=min6,3+1=4,l5(2)=minl5(0),l2(2)*+w25=min,3+=,修改通过集与未通过集 P3=v0,v1,v2,v4,T3=v5,v3,修改未通过集的t标号：,l3(3)=minl3(2),l4(3)*+w43=min8,4+3=7,l5(3)=minl5(2),l4(3)*+w45=min,4+6=10,修改通过集与未通过集 P4=v0,v1,v2,v4,v3,T4=v5,修改未通过集的t标号：,l5(4)=minl5(3),l3(4)*+w35=min10,7+2=9,修改通过集与未通过集 P5=v0,v1,v2,v4,v3,v5,T5=,由于T5=，过程结束，得v0到v5的最短路径为：,=v0,v1,v2,v4,v3,v5，且w()=9,标号法的说明：,(1)标号法可求任何顶点Vs到其它任一顶点之间的最短路径，只是算法的“开始”步中，先给顶点Vs加p标号0，即ls(0)*=0，然后算法往下计算。,(2)若已经求出从vi到vj的最短路径，则从vi到此路径上其余各顶点的最短路径也都求出了。,8.5 欧拉图与哈密尔顿图,如果存在一条通路，它经过G的每条边一次且仅一次，则称该通路为欧拉通路；,具有欧拉回路的图 欧拉图。,欧拉图：给定无孤立顶点的图G，,存在一条回路，它经过G的每条边一次且仅一次，则此回路为欧拉回路。,如果,欧拉图的判定定理：,(1)无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有顶点的度数全为偶数；,(2)有向图D具有单向欧拉回路，当且仅当D是连通的，并且每个顶点的入度等于出度。,(3)无向图G有欧拉通路，当且仅当它连通且有零个或两个奇数度顶点；,(4)有向图D有欧拉通路，当且仅当它连通且除两个顶点外，各顶点的入度均等于出度。,证明较复杂(略)。,哈密尔顿图：给定图G，如果存在一条经过G的每个顶点一次且恰好一次的通路(回路)，则称该通路(回路)为哈密尔顿通路(回路)。,具有哈密尔顿回路的图称为哈密尔顿图。,哈密尔顿图的充分必要条件至今仍未解决。,例8.8 下列图哪些为欧拉图：,(1),(2),(3),(4),小结与学习要求,1.本章围绕图中元素间的邻接与关联关系讨论了图论中几个基本问题：图的连通性问题，道路问题，可达性问题，最短路径问题。2.要仔细领会和掌握下列基本概念和相关结论：子图、度、通路、回路、支、割点，割边，独立点，权，补图，同构图等。3.熟练掌握标号法。,