离散数学第七章图.doc

第七章 图在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。图论起源于18世纪，它是研究由线连成的点集的理论。一个图中的结点表示对象，两点之间的连线表示两对象之间具有某种特定关系(先后关系、胜负关系、传递关系和连接关系等)。事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。7.1图的基本概念7.1.1图的定义7.1.1.1无向图定义7.1.1设A，B是任意集合。集合(a,b)|aA且bB称为A和B的无序积，记为AB。在无序积中，两个元素间的顺序是无关紧要的，即(a,b)(b,a)。定义7.1.2无向图G是一个二元组，记作G，其中V是一个非空有限集合，其元素称为结点(顶点)。E是一个VV的多重子集，其元素称为边(无向边)。我们可用平面上的点来表示顶点，两点间的连线表示边，从而将任一个无向图用图形表示出来。例7.1.1无向图G，其中V=a，b，c，d，e，f，E=(a,b)，(a,c)，(a,d)，(b,b)，(b,c)，(b,c)，(b,d)，(c,d)。7.1.1.2有向图定义7.1.3有向图G是一个二元组，记作G，其中V是一个非空有限集合，其元素称为顶点，E是一个VV的多重子集，其元素称为有向边或弧，简称为边。注：1)在有向图G中，若e=u，v，则称u和v为e的起点和终点；2)自回路既可看成是有向边又可看成是无向边；3)去掉有向图中边的方向得到的图称为该有向图的基图。例7.1.2有向图G，其中V=a，b，c，E=，。7.1.1.3相关概念在无向图或有向图中，1）有限图与无限图；2）n阶图；|V|=n;3) 零图 E=；4）平凡图（|V|=n ，E=）；5)对于无向图， 若边e=(u,v)，则称u和v是边 e的端点，称边 e关联于u和v，若u=v，则称此为环，边与顶点的关联次数是0，1，2；至少有一条边相连的两个顶点相邻；至少一个公共顶点的两条边相邻6)对于有向图， 若边e=，则称u和v是边 e的端点，称u是边 e的始点，v是边 e的终点，称u邻接到v。7)关联于同一个顶点的边称为环（自回路）；若关联于同一对顶点的边多于一条时，称这些边为平行边，平行边的条数称为边的重数；8)不与任何顶点邻接的顶点称为孤立点；含有平行边的图称为多重图，不含有平行边，也不含环的图称为简单图；7.1.2顶点的度数，握手定理定义7.1.4(1)在无向图G=V，E中，vV。与v关联的边数称为v的度数，记为deg(v)；(2) 在有向图G=V，E中，vV。以v为始点的边数称为v的出度，记为deg(v)；以v为终点的边数称为v的入度，记为deg(v)；称deg(v)= deg(v)+ deg(v)称为v的度(数)。例7.1.3求例7.1.1中无向图每个顶点的度数；求例7.1.3中有向图每个顶点的出度、入度和度。注：若结点有自回路，则结点的度数因此而增加2；若有向图的结点v有自回路，则它的出度和入度分别因此而增加1。孤立结点的度数为0。 定理7.1.1 (Euler握手定理) 在图G=中, deg(v)=2|E|。推论7.1.1 任何图中度数为奇数的结点为偶数个。定理7.1.2在有向图G=中有 deg(v)= deg(v)=|E|。度序列，出度序列，入度序列：定理7.1.3：度序列可图化的充要条件是度序列之和是偶数。例7.1.4（1）3，2，3，3 5，2，3，1，4，7可图化吗？（2）一知一个图有10条边，4个3度顶点，其余顶点的度数均小于等于2，问该图至少有几个顶点？7.1.3子图定义7.1.5设图G=和G=，（1） 若V，则称是的子图，记为GG；（2） 若GG且V或，则称是的真子图，记为GG；（3） 若GG且V=V，则称是的生成子图；（4） VV，V，以V为顶点集，以所有端点均在V中的G的边为边集的图称为由V诱导出的的子图；（5） EE，E，以E为边集，以E中的边的端点点为顶点集的图称为由E诱导出的的子图；例7.1.5求例7.1.1中无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。7.1.4完全图、补图和图的同构定义7.1.6在无向简单图G=V，E中，|V|=n。若每对结点都邻接(即每对结点之间都有边)，则称之为无向完全图，记为Kn。类似地，可以定义有向完全图。例7.1.6K2，K3，K4，K5及2、3、4、5个顶点的有向完全图。定义7.1.7 设G=是简单图，|V|=n，H=。若E=且E=E(Kn)，则称图H是G的补图，记为。G和互为补图。例7.1.7 求补图。定义7.1.8设图G1=，G2=。若存在双射f：V1V2，满足：u，vV1，u,vE1f(u),f(v) E2且u,v的重数和f(u),f(v)的重数相等 (u,v指(u,v)或u,v)，则称G1和G2同构，记为G1G2。由于一个图是由其顶点集和边集所决定的，而同构的两个图中顶点集之间存在一一对应关系，且这种对应关系保持顶点间的邻接关系及边的重数，故抽象地看，两个同构的图本质上是一样的。两个图同构的必要条件：顶点数相等; 边数相等; 所有顶点度数之和相等；度数相同的顶点数相等。自补图7.2通路、回路、图的连通性7.2.1通路和回路定义7.2.1给定图G=V，E，设v0,v1,vnV，e1,e2,enE，顶点和边交替出现的序列v0e1v1e2en vn称为从顶点v0到vn的通路，v0和vn 分别称为该通路的起点和终点；称通路上的边数为该通路的长度。当v0和vn相等时，称该通路为回路或圈。若通路(回路)的所有边都各不相同，则称该通路(回路)为简单通路(回路)；若通路(回路)的所有顶点都各不相同，则称该通路(回路)为初级通路(回路)。例7.2.1求下图的通路、回路、简单通路、简单回路、初级通路、初级回路每一初级通路(回路)一定是简单通路(回路)；反之则不然。在简单图中，可以用顶点序列来表示通路(回路)，当然在不产生二义性的前提下也可以用边的序列来表示通路(回)路。定理7.2.1给定图G=，|V|=n，u,vV。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的通路。推论7.2.1给定图G=，|V|=n，u,vV。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的初级通路。定理7.2.2给定图G=，|V|=n，uV。若存在经过u的一条回路，则必有一条经过u的长度不超过n的回路。注： 在一个具有n 个顶点的图中，（1）任何初级通路的长度均不大于n-1；（2）任何初级回路的长度均不大于n。7.2.2图的连同性定义7.2.2给定图G=V，E，u,vV。若存在从u到v的通路，则称从u到v是可达的或称u可达v。规定任一个顶点总是可达自身。定义7.2.3给定无向图G=V，E。若G的任何两个顶点是相互可达的，则称G是连通图，否则称G是非连通图。在无向图G=V，E中，定义关系R为： u,vV，uRv u可达v。则R是V上的一个等价关系，从而可以决定V的一个划分，我们称每一个由划分块诱导出的G的子图为G的连通分支，用p(G)表示G的连通分支数。每个顶点在且仅在一个连通分支中。若p(G)1，则G是连通图。例7.2.2给出连通图、非连通图；图的连通分支。定义7.2.4给定有向图G=V，E。对任何两顶点u,vV，（1）若u和v相互可达，则称G是强连通的；（2）若u和v至少有一个可达另一个，则称G是单向连通的；（3）若其基图是连通的，则称G是弱连通的。例7.2.3给出强连通图、单向连通图和弱连通图。强连通图 = 单向连通图 = 弱连通图。定理7.2.3有向图G是强连通的G中有一回路，它至少通过每个顶点一次。定义7.2.5给定图G=V，E，u,vV。若u可达v，则称从u到v的长度最短的通路为u与v之间的短程线，其长度称为u到v的距离，记为d(u,v)。7.2.3点割集，割点，边割集，桥 (1)点割集和割点定义7.2.6设无向图G=V，E若存在顶点子集VV，使G删除V后，所得子图G-V的连通分支数P(G-V)P(G),而删除V的任何真子集后,P(G-)=P(G),则 V为G的点割集,如果V只有一个顶点v,则称v为割点（2）边割集和桥定义7.2.7设无向图G=V，E若存在边子集EV，使G删除E后，所得子图G-E的连通分支数P(G-E)P(G),而删除E的任何真子集后,P(G-)=P(G),则 E为G的边割集,如果E只有一个顶点e,则称e为桥.7.3图的矩阵表示7.3.1无向图的关联矩阵7.3.1设有向图G=，V=v1，v2，vn，E=e1,e2,em,则nm阶方阵A=(aij)称为G的关联矩阵，记为M(G)=(mij),其中mij为vi与边ej 关联的次数(0,1,2)。(1)M的每列元素之和等于2;(2)M的第i行元素之和等于d(vi);(3) M的所有元素之和2m;(4) 若M的第i行元素之和等于0,则vi是孤立点;7.3.1有向图的关联矩阵定义7.3.2设无环有向图G=，V=v1，v2，vn，E=e1,e2,em,则nm阶矩阵A=(aij)称为G的关联矩阵，记为M(G)=(mij),其中mij=(1)M的每列元素之和等于0,M的所有元素之和0.(2) M的所有值为1元素之和=值为-1元素之和=m.7.3.3有向图的邻接矩阵定义7.3.3设有向图G=，V=v1，v2，vn，则n阶方阵A=(aij)称为G的邻接矩阵，其中aij为vi邻接vj 的边数。 在不考虑结点编序的情形下，图的邻接矩阵是唯一的；一个邻接矩阵可以完全确定一个有向图。在一个简单有向图G中,deg+(vi)=aij=第行中元素的和 deg-(vi)=第i列中元素的和=akj例7.3.1求下图的邻接矩阵。 定理7.3.1设A有向图G=的邻接矩阵，V=v1，v2，vn，则Ak()的第i行第j列元素等于从vi到vj长为k的通路数，等于经过vi长为k的回路数。例7.3.2求下图的顶点b到其他顶点长为3的通路数。7.3.4有向图的可达矩阵定义7.3.4设有向图G=，V=v1，v2，vn，则n阶方阵P=(pij)称为G的可达矩阵，其中 pij= 可达矩阵的元素的值表明图中任两个顶点间是否存在通路，以及经过某个结点是否存在回路。若记BAA1An-1=(bij)nn，则对i,j=1,2,n且ij，若 bij 0，则pij=1，否则 pij=0。pii=1，i=1,2,n。例7.3.3求下图的可达矩阵。类似地，我们可以定义无向图的邻接矩阵和可达矩阵。无向图的邻接矩阵和可达矩阵一定是对称矩阵。7.4最短路径和关键路径7.4.1赋权图和最短通路问题定义7.4.1对于有向图或无向图，给每一条边都赋予权(正实数)的图称为赋权图，记为G=，称W(e)=Wij为边e的权, 称W(G)=为图G的权。在赋权图中，通路的边的权权重之和叫通路的权重。7.4.2最短路经单源点的最短路径问题：给定带权有向图（或无向）G和源点vV，求从v0到G中其余各顶点的最短路径。问题解决算法。即由迪杰斯特拉（Dijkstra）提出的一个按路径长度递增的次序产生最短路径的算法。该算法的基本思想是：设置两个顶点的集合S和TVS，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S是空集，从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。Dijkstra算法的实现。（1）S为已找到从v0出发的最短路径的终点的集合，它的初始状态为空集，T=V-S,。引进一个辅助向量D，它的每个分量Di 表示始点v0到每个终点vi 的最短路径的长度。它的初态为：若从v0到vi有弧（边），则Di为弧上的权值；否则置 Di为。(2)顶点选取，Du=MinDi| viT, S=S+ vu T=T-vu; （3）修改Dj Dj=MinDj, Du+Wuj VjV-S 其中，Di 或者弧（v, vj）上的权值，或者是Du和弧（Vu, Vj）上的权值之和。 (4)重复操作、共n-1次。由此求得从v 到图上其余各顶点的最短路径例7.4.1求下列赋权图中v1到其他顶点的距离。7.4.3关键路径若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续的时间），则此带权的有向图称为AOE网(PERT图)。 利用AOE网进行工程管理时要需解决的主要问题是： （1） 计算完成整个工程的最短路径。 （2）确定关键路径，以找出哪些活动是影响工程进度的关键。3. 关键路径的确定 后继元集：前导元集 为了在AOE网中找出关键路径，需要定义几个参量，并且说明其计算方法。（1）事件的最早发生时间TEVi TEVi是指从源点到顶点的最大路径长度代表的时间。这个时间决定了所有从顶点发出的有向边所代表的活动能够开工的最早时间。计算vk发生的最早时间的方法如下： TEVl=0 TEVi=maxTEVj+Wji,。（2）事件的最迟发生时间TLVi计算vk发生的最早时间的方法如下： TLVn=最长路经长度 TLVi=minTLVj-Wij,。 （3缓冲时间ES(Vi)=TL(Vi)-TE(Vi)例7.4.2求下列PERT图得关键路径9