离散数学图的基本概念

离散数学图的基本概念*第1页，共48页。通路与回路定义给定图G=（无向或有向的），设G中顶点与边的交替序列=v0e1v1e2…elvl：若i(1il),vi1和vi是ei的端点(对于有向图,要求vi1是始点,vi是终点),则称为通路,v0是通路的起点,vl是通路的终点,l为通路的长度.又若v0=vl，则称为回路.理解：通路或回路是点与边的交替序列，边的端点恰好是前后的两个点长度＝边数*第2页，共48页。若通路(回路)中所有顶点(对于回路,除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径,初级回路又称作...

*第1页，共48页。通路与回路定义给定图G=（无向或有向的），设G中顶点与边的交替序列=v0e1v1e2…elvl：若i(1il),vi1和vi是ei的端点(对于有向图,要求vi1是始点,vi是终点),则称为通路,v0是通路的起点,vl是通路的终点,l为通路的长度.又若v0=vl，则称为回路.理解：通路或回路是点与边的交替序列，边的端点恰好是前后的两个点长度＝边数*第2页，共48页。若通路(回路)中所有顶点(对于回路,除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径,初级回路又称作圈.路上各点不重复若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路).路上各边不重复*第3页，共48页。通路与回路(续)说明:在无向图中，环是长度为1的圈,两条平行边构成长度为2的圈.无向简单图中,所有圈的长度3在有向图中，环是长度为1的圈,两条方向相反边构成长度为2的圈.在有向简单图中,所有圈的长度2.*第4页，共48页。通路与回路(续)定理在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的通路.推论在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的初级通路.定理在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于等于n的回路.推论在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于等于n的初级回路.*第5页，共48页。无向图的连通性设无向图G=,u与v连通:u与v之间有通路.规定u与自身总连通.连通关系：R={|u,vV且uv}是V上的等价关系连通图:平凡图,或者任意两点都连通的图连通分支:V关于R的等价类的导出子图设V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的连通分支,连通分支个数记作p(G)=k.G是连通图p(G)=1*第6页，共48页。短程线与距离u与v之间的短程线:u与v之间长度最短的通路u与v之间的距离d(u,v):u与v之间短程线的长度若u与v不连通,规定d(u,v)=∞.性质：d(u,v)0,且d(u,v)=0u=vd(u,v)=d(v,u)（对称性）d(u,v)+d(v,w)d(u,w)（三角不等式)*第7页，共48页。点割集（v－点；V’－点集；e－边；E’－变集）记Gv:从G中删除v及关联的边GV:从G中删除V中所有的顶点及关联的边Ge:从G中删除eGE:从G中删除E中所有边定义设无向图G=,如果存在顶点子集VV,使p(GV)>p(G)，而且删除V的任何真子集V后（VV），p(GV)=p(G),则称V为G的点割集.若{v}为点割集,则称v为割点.理解：删除点后连通分支数可能增加，会减少吗？*第8页，共48页。点割集(续)例{v1,v4},{v6}是点割集,v6是割点.{v2,v5}是点割集吗？*第9页，共48页。边割集定义设无向图G=,EE,若p(GE)>p(G)且EE,p(GE)=p(G),则称E为G的边割集.若{e}为边割集,则称e为割边或桥.下图中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集，e8是桥，{e7,e9,e5,e6}是边割集吗？*第10页，共48页。几点说明：Kn无点割集（完全图）n阶零图既无点割集，也无边割集.若G连通，E为边割集，则p(GE)=2若G连通，V为点割集，则p(GV)2*第11页，共48页。有向图的连通性设有向图D=u可达v:u到v有通路.规定u到自身总是可达的.可达具有自反性和传递性D弱连通(也称连通):基图为无向连通图有向边改为无向边后是连通图D单向连通:u,vV，u可达v或v可达uD强连通:u,vV，u与v相互可达强连通单向连通弱连通*第12页，共48页。有向图的连通性(续)(1)(2)(3)例下图(1)强连通,(2)单连通,(3)弱连通每个顶点有进有出部分顶点有进有出*第13页，共48页。有向图的短程线与距离u到v的短程线:u到v长度最短的通路(u可达v)u与v之间的距离d:u到v的短程线的长度若u不可达v,规定d=∞.性质：d0,且d=0u=vd+dd注意:没有对称性*第14页，共48页。7.3图的矩阵表示无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵*第15页，共48页。无向图的关联矩阵定义设无向图G=,V={v1,v2,…,vn},E={e1,e2,…,em},令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G).性质*第16页，共48页。v1v2v4v3e1e2e3e4e5关联次数为可能取值为0，1，2*第17页，共48页。无向图的相邻矩阵v1v2v4v3e1e2e3e4e5(1)相邻矩阵是对称矩阵。(2)对角元素aii≠0,表示结点vi处有环。(3)如aij＞1,表示vi与vj间有平行边。aij+2*第18页，共48页。V1V2V3V4V5V1V2V3V4V5*第19页，共48页。有向图的关联矩阵定义设无环有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em},令则称(mij)nm为D的关联矩阵，记为M(D).*第20页，共48页。v4v1v2v3e1e2e3e4e5性质:(4)平行边对应的列相同*第21页，共48页。定义设有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()nn为D的邻接矩阵,记作A(D),简记为A.性质有向图的邻接矩阵*第22页，共48页。v2v1v4v3*第23页，共48页。D中的通路及回路数定理设A为n阶有向图D的邻接矩阵,则Al(l1)中元素为D中vi到vj长度为l的通路数，为vi到自身长度为l的回路数，为D中长度为l的通路总数，为D中长度为l的回路总数.*第24页，共48页。D中的通路及回路数(续)例有向图D如图所示,求A,A2,A3,A4,并回答问题：(1)D中长度为1,2,3,4的通路各有多少条？其中回路分别为多少条？(2)D中长度小于或等于4的通路为多少条？其中有多少条回路？推论设Bl=A+A2+…+Al(l1),则Bl中元素为D中长度小于或等于l的通路数，为D中长度小于或等于l的回路数.*第25页，共48页。例(续)长度通路回路合计508181211331414173*第26页，共48页。有向图的可达矩阵定义设D=为有向图,V={v1,v2,…,vn},令称(pij)nn为D的可达矩阵,记作P(D),简记为P.性质:P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.*第27页，共48页。有向图的可达矩阵(续)例右图所示的有向图D的可达矩阵为*第28页，共48页。如何求有向图的可达矩阵设D=为有向图，|V|=n,A为D的邻接矩阵；先求R＝（rij）＝A+A2+...+An再求可达矩阵P＝（pij）*第29页，共48页。7.4最短路径及关键路径对于有向图或无向图G的每条边，附加一个实数w(e)，则称w(e)为边e上的权.G连同附加在各边上的实数，称为带权图.设带权图G=,G中每条边的权都大于等于0.u,v为G中任意两个顶点，从u到v的所有通路中带权最小的通路称为u到v的最短路径.求给定两个顶点之间的最短路径，称为最短路径问题.*第30页，共48页。算法：Dijkstra(标号法)*第31页，共48页。v2v0v1v3v4v5141762253例：求图中v0与v5的最短路径*第32页，共48页。vikv0v1v2v3v4v500141138623843741047959013749v0v1v2v4v3*第33页，共48页。2.关键路径问题PERT图设D=是n阶有向带权图D是简单图D中无环路有一个顶点出度为0，称为发点；有一个顶点入度为0，称为收点记边的权为wij,它常常表示时间*第34页，共48页。Pert图的应用用Pert中有向边→表示工序，边上权表示完成工序的时间；用pert图中结点vi表示某个事项，表示某些工序的完工，同时表示某些工序可以开工。习惯上所有的有向边均从左向右。Pert－ProgramEvaluationandReviewTechnic，计划评审技术*第35页，共48页。关键路径从始点到终点的一条最长路径（发点到收点的一条最长路径）通过求各点的最早完成时间来求关键路径最早完成时间：自发点v1开始，沿最长路径（按权计算）到达vi所需时间，称为vi的最早完成时间，记为TE（vi），i=1,2,…,n。TE(vi)表示在前面所有工序均没有耽误的情况下，该事项最早可能完成的时间，此时前面的工序均必须完成。也是后续工程最早开始的时间。*第36页，共48页。这样从始点出发，TE(v0)＝0，一直计算到收点vn，TE(vn)就是工程的最早完工时间。*第37页，共48页。1234657824423326324026671315节点的最早完工时间*第38页，共48页。2．事项的最晚完成时间TL(vi)：在保证收点vn的最早完成时间不增加的条件下，该事项vi最晚必须完成的时间，称为该点vi最晚完成时间，记为TL(vi)。因为有些工序不在关键路上,这些工序有个缓冲时间,稍迟一些时间动工，不会导致整个工程的完工时间，但这也有个限度，TL(vi)就是不耽误整个工程的最早完工条件下，该工序最迟的开工时间，过了这时间开工将影响整个工程。*第39页，共48页。其算法是从收点开始向后计算：因v0和vn均在关键路上,TE（vn）=TL（vn），TE（v0）=TL（v0）=0*第40页，共48页。12346578244233263240510971315节点的最迟完工时间*第41页，共48页。缓冲时间该事项在不影响整个工程的前提下，可以延滞的时间。TS(vi)＝TL(vi)－TE(vi)*第42页，共48页。关键路径从发点v0出发到收点vn的一条路径，这条路上任何工序的延滞必导致整个工程的延滞。关键路是整个工程计划的主要矛盾。关键路至少一条，也能是不止一条，在关键路上TS（vi）=0*第43页，共48页。节点12345678TE(vi)0426671315TL(vi)04410971315TS(vi)00243000其关键路径是v1,v2,v5,v7,v8*第44页，共48页。v2v7v1v8v5v4v3v612023441344161.最早完成时间：*第45页，共48页。v2v7v1v8v5v4v3v612023441344162.最晚完成时间：*第46页，共48页。v2v7v1v8v5v4v3v612023441344163.缓冲时间：TS(vi)=TL(vi)-TE(vi)TS(v1)=TS(v3)=TS(v7)=TS(v8)=0TS(v2)=2-1=1;TS(v4)=6-4=2;TS(v5)=10-8=2;TS(v6)=11-9=2*第47页，共48页。v2v7v1v8v5v4v3v61202344134416*第48页，共48页。

                    本文档为【离散数学图的基本概念】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

离散数学图的基本概念

你可能还喜欢