离散数学图的基本概念精.ppt

《离散数学图的基本概念精.ppt》由会员分享，可在线阅读，更多相关《离散数学图的基本概念精.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第1页，本讲稿共48页通路与回路通路与回路 n定义定义 n给给定定图图G=（无无向向或或有有向向的的），设设G中中顶顶点点与与边边的的交交替序列替序列=v0e1v1e2elvl：若若 i(1 i l),vi 1 和和 vi是是ei的的端端点点(对对于于有有向向图图,要要求求vi 1是是始始点点,vi是是终终点点),则则称称 为为通通路路,v0是是通通路路的的起起点点,vl是是通通路的终点路的终点,l为为通路的长度通路的长度.又若又若v0=vl，则称，则称 为为回路回路.n理理解解：通通路路或或回回路路是是点点与与边边的的交交替替序序列列，边边的的端端点点恰好是前后的两个点恰好是前后的两个点n

2、长度边数长度边数2第2页，本讲稿共48页若若通通路路(回回路路)中中所所有有顶顶点点(对对于于回回路路,除除v0=vl)各各异异，则则称称为为初初级级通通路路(初初级级回回路路).初初级级通通路路又又称称作作路路径径,初初级级回回路路又称作又称作圈圈.n路上各点不重复路上各点不重复若若通通路路(回回路路)中中所所有有边边各各异异,则则称称为为简简单单通通路路(简简单单回回路路),否则称为否则称为复杂通路复杂通路(复杂回路复杂回路).n路上各边不重复路上各边不重复3第3页，本讲稿共48页通路与回路通路与回路(续续)说明说明:n在无向图中，环是长度为在无向图中，环是长度为1 1的圈的圈,两条平行边

3、构成长度为两条平行边构成长度为2 2的的圈圈.无向简单图中无向简单图中,所有圈的长度所有圈的长度 3 3n在有向图中，环是长度为在有向图中，环是长度为1 1的圈的圈,两条方向相反边构成长度为两条方向相反边构成长度为2 2的圈的圈.在有向简单图中在有向简单图中,所有圈的长度所有圈的长度 2.2.4第4页，本讲稿共48页通路与回路通路与回路(续续)n定理定理 在在n阶阶图图G中中，若若从从顶顶点点vi到到vj（vi vj）存存在在通通路路，则则从从vi到到vj存在长度小于等于存在长度小于等于n 1的的通路通路.n推论推论 在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj（vi vj）存在通路，

4、则从）存在通路，则从vi到到vj存在长度小于等于存在长度小于等于n 1的的初级通路初级通路.n定理定理 在一个在一个n阶图阶图G中，若存在中，若存在vi到自身的回路，则一定存在到自身的回路，则一定存在vi到自身长度小于等于到自身长度小于等于n的回路的回路.n推论推论 在一个在一个n阶图阶图G中，若存在中，若存在vi到自身的简单回路，则一定到自身的简单回路，则一定存在长度小于等于存在长度小于等于n的初级回路的初级回路.5第5页，本讲稿共48页无向图的连通性无向图的连通性 n设无向图设无向图G G=,u u与与v v连通连通:u u与与v v之间有通路之间有通路.n规定规定u u与自身总连通与自身

5、总连通.连通关系：连通关系：R R=|u u,v v V V且且u u v v 是是V V上的等价关系上的等价关系连通图连通图:平凡图平凡图,或者任意两点都连通的图或者任意两点都连通的图连连 通通 分分 支支:V V关关 于于R R的的 等等 价价 类类 的的 导导 出出 子子 图图 设设V V/R R=V V1 1,V V2 2,V Vk k,G G V V1 1,G G V V2 2,G G V Vk k 是是G G的的连连通分支通分支,n连通分支个数记作连通分支个数记作p p(G G)=)=k.k.nG G是连通图是连通图 p p(G G)=1)=16第6页，本讲稿共48页短程线与距离短

6、程线与距离nu与与v之间的短程线之间的短程线:u与与v之间长度最短的通路之间长度最短的通路nu与与v之间的距离之间的距离d(u,v):u与与v之间短程线的长度之间短程线的长度若若u与与v不连通不连通,规定规定d(u,v)=.性质：性质：n d(u,v)0,且且d(u,v)=0 u=vn d(u,v)=d(v,u)（对称性）（对称性）n d(u,v)+d(v,w)d(u,w)（三角不等式（三角不等式)7第7页，本讲稿共48页点割集（点割集（v v点；点；V V点集；点集；e e边；边；E E变集）变集）n记 Gv:从G中删除v及关联的边 GV:从G中删除V中所有的顶点及关联的边Ge:从G中删除e

7、GE:从G中删除E中所有边n定义 设 无 向 图 G=,如 果 存 在 顶 点 子 集 VV,使p(GV)p(G)，而且删除V的任何真子集V后（VV），p(GV)=p(G),则称V为G的点割集.若v为点割集,则称v为割点.理解：删除点后连通分支数可能增加，会减少吗？8第8页，本讲稿共48页点割集点割集(续续)例例 v1,v4,v6是点割集是点割集,v6是割点是割点.v2,v5是点割集吗？是点割集吗？9第9页，本讲稿共48页边割集边割集n定义定义 设设 无无 向向 图图 G=,EE,若若 p(G E)p(G)且且 E E,p(G E)=p(G),则称则称E 为为G的的边割集边割集.若若e为边割集

8、为边割集,则称则称e为为割边割边或或桥桥.下下图图中中，e1,e2，e1,e3,e5,e6，e8等等是是边边割割集集，e8是桥，是桥，e7,e9,e5,e6是边割集吗？是边割集吗？10第10页，本讲稿共48页n几点说明：几点说明：Kn无点割集（完全图）无点割集（完全图）n阶零图既无点割集，也无边割集阶零图既无点割集，也无边割集.若若G连通，连通，E 为边割集，则为边割集，则p(G E)=2若若G连通，连通，V 为点割集，则为点割集，则p(G V)211第11页，本讲稿共48页有向图的连通性有向图的连通性 n设有向图设有向图D=u可达可达v:nu到到v有通路有通路.规定规定u到自身总是可达的到自

9、身总是可达的.n可达具有自反性和传递性可达具有自反性和传递性D弱连通弱连通(也称连通也称连通):n基图为无向连通图基图为无向连通图n有向边改为无向边后是连通图有向边改为无向边后是连通图D单向连通单向连通:n u,v V，u可达可达v 或或v可达可达u D强连通强连通:n u,v V，u与与v相互可达相互可达n强连通强连通单向连通单向连通弱连通弱连通 12第12页，本讲稿共48页有向图的连通性有向图的连通性(续续)(1)(2)(3)例例 下图下图(1)强连通强连通,(2)单连通单连通,(3)弱弱连通连通每个顶点有进有出部分顶点有进有出13第13页，本讲稿共48页有向图的有向图的短程线与距离短程线

10、与距离nu到v的短程线:u到v长度最短的通路(u可达v)nu与v之间的距离d:u到v的短程线的长度若u不可达v,规定d=.性质：n d0,且d=0 u=vn d+d d 注意:没有对称性14第14页，本讲稿共48页7.3 图的矩阵表示图的矩阵表示 无向图的关联矩阵无向图的关联矩阵有向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的邻接矩阵有向图的可达矩阵有向图的可达矩阵 15第15页，本讲稿共48页无向图的关联矩阵无向图的关联矩阵定定义义 设设无无向向图图G=,V=v1,v2,vn,E=e1,e2,em,令令mij为为vi与与ej的的关关联联次次数数，称称(mij)n m为为G的关联矩阵的

11、关联矩阵，记为，记为M(G).性质性质16第16页，本讲稿共48页v1v2v4v3e1e2e3e4e5关联次数为可能取值为关联次数为可能取值为0，1，217第17页，本讲稿共48页无向图的相邻矩阵无向图的相邻矩阵v1v2v4v3e1e2e3e4e5(1)相邻矩阵是对称矩阵。(2)对角元素aii0,表示结点vi处有环。(3)如aij 1,表示vi与vj间有平行边。aij+2 18第18页，本讲稿共48页V1V2V3V4V5 V1 V2 V3 V4 V519第19页，本讲稿共48页有向图的关联矩阵有向图的关联矩阵定义定义 设无环有向图设无环有向图D=,V=v1,v2,vn,E=e1,e2,em,令

12、令 则称则称(mij)n m为为D的关联矩阵的关联矩阵，记为，记为M(D).20第20页，本讲稿共48页v4v1v2v3e1e2e3e4e5性质性质:(4)平行边对应的列相同平行边对应的列相同21第21页，本讲稿共48页定义定义 设有向图设有向图D=,V=v1,v2,vn,E=e1,e2,em,令令 为顶点为顶点vi邻接到顶点邻接到顶点vj边的条数，称边的条数，称()n n为为D的邻接矩阵的邻接矩阵,记作记作A(D),简记为简记为A.性质性质有向图的邻接矩阵有向图的邻接矩阵 22第22页，本讲稿共48页v2v1v4v323第23页，本讲稿共48页D中的通路及回路数中的通路及回路数定理定理 设设

13、A为为n阶有向图阶有向图D的邻接矩阵的邻接矩阵,则则Al(l 1)中中元素元素 为为D中中vi到到vj长度为长度为 l 的通路数，的通路数，为为vi到自身长度为到自身长度为 l 的回路数，的回路数，为为D中长度为中长度为 l 的通路总数，的通路总数，为为D中长度为中长度为 l 的回路总数的回路总数.24第24页，本讲稿共48页D中的通路及回路数中的通路及回路数(续续)例例 有向图有向图D如图所示如图所示,求求A,A2,A3,A4,并回答问题：并回答问题：(1)D中长度为中长度为1,2,3,4的通路各有多的通路各有多 少条？其中回路分别为多少条？少条？其中回路分别为多少条？(2)D中长度小于或等

14、于中长度小于或等于4的通路为多的通路为多 少条？其中有多少条回路？少条？其中有多少条回路？推论推论 设设Bl=A+A2+Al(l 1),则则Bl中元素中元素 为为D中长度小于或等于中长度小于或等于l 的通路数，的通路数，为为D中长度小于或等于中长度小于或等于l 的回路数的回路数.25第25页，本讲稿共48页例例(续续)长度长度 通路通路 回路回路 合计合计 50 818 1211 3314 1417 326第26页，本讲稿共48页有向图的可达矩阵有向图的可达矩阵 定义定义 设设D=为有向图为有向图,V=v1,v2,vn,令令 称称(pij)n n为为D的可达矩阵的可达矩阵,记作记作P(D),简

15、记为简记为P.性质性质:P(D)主对角线上的元素全为主对角线上的元素全为1.D强连通当且仅当强连通当且仅当P(D)的元素全为的元素全为1.27第27页，本讲稿共48页有向图的可达矩阵有向图的可达矩阵(续续)例例 右图所示的有向图右图所示的有向图D的可达矩阵为的可达矩阵为28第28页，本讲稿共48页如何求有向图的可达矩阵n设D=为有向图，|V|=n,A为D的邻接矩阵；先求R（rij）A+A2+.+An再求可达矩阵P（pij）29第29页，本讲稿共48页7.4 最短路径及关键路径最短路径及关键路径对于有向图或无向图对于有向图或无向图G的每条边，附加一个实数的每条边，附加一个实数w(e)，则称，则称

16、w(e)为边为边e上的上的权权.G连同附加在各边上的实数，称为连同附加在各边上的实数，称为带权图带权图.设带权图设带权图G=,G中每条边的权都大于等于中每条边的权都大于等于0.u,v为为G中任意两个中任意两个顶点，从顶点，从u到到v的所有通路中带权最小的通路称为的所有通路中带权最小的通路称为u到到v的的最短路径最短路径.求给定两个顶点之间的最短路径，称为求给定两个顶点之间的最短路径，称为最短路径问题最短路径问题.30第30页，本讲稿共48页算法：Dijkstra(标号法)31第31页，本讲稿共48页v2v0v1v3v4v5141762253例：求图中例：求图中v0与与v5的最短路径的最短路径3

17、2第32页，本讲稿共48页 vikv0v1v2v3v4v50 0 141 138623 8437 4104 7959013749v0v1v2v4v333第33页，本讲稿共48页2.关键路径问题关键路径问题PERTPERT图图 设D=是n阶有向带权图1.D是简单图2.D中无环路3.有一个顶点出度为0，称为发点；有一个顶点入度为0，称为收点4.记边的权为wij,它常常表示时间34第34页，本讲稿共48页Pert图的应用n用Pert中有向边表示工序，边上权表示完成工序的时间；n用pert图中结点vi表示某个事项，表示某些工序的完工，同时表示某些工序可以开工。n习惯上所有的有向边均从左向右。nPert

18、Program Evaluation and Review Technic，计划评审技术35第35页，本讲稿共48页关键路径n从始点到终点的一条最长路径（发点到收点的一条最长路径）通过求各点的最早完成时间来求关键路径n最早完成时间：自发点v1开始，沿最长路径（按权计算）到达vi所需时间，称为vi的最早完成时间，记为TE（vi），i=1,2,n。nTE(vi)表示在前面所有工序均没有耽误的情况下，该事项最早可能完成的时间，此时前面的工序均必须完成。也是后续工程最早开始的时间。36第36页，本讲稿共48页n这样从始点出发，TE(v0)0，一直计算到收点 vn，TE(vn)就是工程的最早完工时间。3

19、7第37页，本讲稿共48页1234657824423326324026671315节点的最早完工时间38第38页，本讲稿共48页n2 2事项的最晚完成时间事项的最晚完成时间 TL(vi)：在保证收点v vn n的最早完成时间不增加的条件下的最早完成时间不增加的条件下，该事项vi最晚必须完成的时间，称为该点vi最晚完成时间，记为TL(vi)。因为有些工序不在关键路上,这些工序有个缓冲时间,稍迟一些时间动工，不会导致整个工程的完工时间，但这也有个限度，TL(vi)就是不耽误整个工程的最早完工条件下，该工序最迟的开工时间，过了这时间开工将影响整个工程。39第39页，本讲稿共48页n其算法是从收点开始

20、向后计算其算法是从收点开始向后计算：n因v0和vn均在关键路上,TE（vn）=TL（vn），TE（v0）=TL（v0）=040第40页，本讲稿共48页12346578244233263240510971315节点的最迟完工时间41第41页，本讲稿共48页n缓冲时间该事项在不影响整个工程的前提下，可以延滞的时间。TS(vi)TL(vi)TE(vi)42第42页，本讲稿共48页关键路径从发点v0出发到收点vn的一条路径，这条路上任何工序的延滞必导致整个工程的延滞。关键路是整个工程计划的主要矛盾。关键路至少一条，也能是不止一条，在关键路上TS（vi）=043第43页，本讲稿共48页节点1234567

21、8TE(vi)0426671315TL(vi)04410971315TS(vi)00243000其关键路径是v1,v2,v5,v7,v844第44页，本讲稿共48页v2v7v1v8v5v4v3v612023441344161.最早完成时间最早完成时间：45第45页，本讲稿共48页v2v7v1v8v5v4v3v612023441344162.最晚完成时间最晚完成时间：46第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=247第47页，本讲稿共48页v2v7v1v8v5v4v3v6120234413441648第48页，本讲稿共48页