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

《《离散数学》图的基本概念.ppt》由会员分享，可在线阅读，更多相关《《离散数学》图的基本概念.ppt（48页珍藏版）》请在金锄头文库上搜索。

1、7.2 通路、回路与图的连通性通路、回路与图的连通性 简单通简单通(回回)路路, 初级通初级通(回回)路路, 复杂通复杂通(回回)路路无向连通图无向连通图, 连通分支连通分支弱连通图弱连通图, 单向连通图单向连通图, 强连通图强连通图点割集与割点点割集与割点边割集与割边边割集与割边(桥桥) 1通路与回路通路与回路 n定义定义 n给给定定图图G=（无无向向或或有有向向的的），设设G中中顶顶点点与与边边的的交交替序列替序列 =v0e1v1e2elvl： 若若 i(1 i l), vi 1 和和 vi是是ei的的端端点点(对对于于有有向向图图, 要要求求vi 1是是始始点点, vi是是终终点点),

2、则则称称 为为通通路路, v0是是通通路路的的起起点点, vl是是通通路路的的终终点点, l为为通通路路的的长长度度. 又又若若v0=vl，则则称称 为为回路回路.n理理解解：通通路路或或回回路路是是点点与与边边的的交交替替序序列列，边边的的端端点点恰好是前后的两个点恰好是前后的两个点n长度边数长度边数2若若通通路路(回回路路)中中所所有有顶顶点点(对对于于回回路路, 除除v0=vl)各各异异，则则称称为为初初级级通通路路(初初级级回回路路).初初级级通通路路又又称称作作路路径径, 初初级级回路又称作回路又称作圈圈.n路上各点不重复路上各点不重复若若通通路路(回回路路)中中所所有有边边各各异异

3、, 则则称称为为简简单单通通路路(简简单单回回路路), 否则称为否则称为复杂通路复杂通路(复杂回路复杂回路).n路上各边不重复路上各边不重复3通路与回路通路与回路( (续续) )说明说明: :n在无向图中，环是长度为在无向图中，环是长度为1 1的圈的圈, , 两条平行边构成长两条平行边构成长度为度为2 2的圈的圈. .无向简单图中无向简单图中, , 所有圈的长度所有圈的长度 3 3n在有向图中，环是长度为在有向图中，环是长度为1 1的圈的圈, , 两条方向相反边构两条方向相反边构成长度为成长度为2 2的圈的圈. .在有向简单图中在有向简单图中, , 所有圈的长度所有圈的长度 2. 2. 4通路

4、与回路通路与回路( (续续) ) n定理定理 在在n阶阶图图G中中，若若从从顶顶点点vi到到vj（vi vj）存存在在通通路路，则则从从vi到到vj存在长度小于等于存在长度小于等于n 1的的通路通路.n推论推论 在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj（vi vj）存在通路，则从存在通路，则从vi到到vj存在长度小于等于存在长度小于等于n 1的的初级通路初级通路.n定理定理 在一个在一个n阶图阶图G中，若存在中，若存在vi到自身的回路，则一定存在到自身的回路，则一定存在vi到自身长度小于等于到自身长度小于等于n的回路的回路.n推论推论 在一个在一个n阶图阶图G中，若存在中，若存在v

5、i到自身的简单回路，则一定到自身的简单回路，则一定存在长度小于等于存在长度小于等于n的初级回路的初级回路. 5无向图的连通性无向图的连通性 n设设无向图无向图G G=,u u与与v v连通连通: : u u与与v v之间有通路之间有通路. .n规定规定u u与自身总连通与自身总连通. .连通关系：连通关系：R R=| | u u, ,v v V V且且u u v v 是是V V上的等价关系上的等价关系连通图连通图: : 平凡图平凡图, , 或者任意两点都连通的图或者任意两点都连通的图连连 通通 分分 支支 : : V V关关 于于R R的的 等等 价价 类类 的的 导导 出出 子子 图图 设设

6、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短程线与距离短程线与距离nu与与v之间的短程线之间的短程线: u与与v之间长度最短的通路之间长度最短的通路nu与与v之间的距离之间的距离d(u,v): u与与v之间短程线的长度之间短程线的长度若若u与与v不连通不连通, 规定规定d(u,v)=.性质：性质：n d(u,v)

7、 0, 且且d(u,v)=0 u=vn d(u,v)=d(v,u)（对称性）对称性）n d(u,v)+d(v,w) d(u,w) （三角不等式三角不等式)7点割集（点割集（v v点；点；V V点集；点集；e e边；边；E E变集）变集） n记 Gv: 从G中删除v及关联的边 GV: 从G中删除V中所有的顶点及关联的边Ge : 从G中删除eGE: 从G中删除E中所有边n定义 设 无 向 图 G=, 如 果 存 在 顶 点 子 集 VV, 使p(GV)p(G)，而且删除V的任何真子集V后（ VV），p(GV)=p(G), 则称V为G的点割集. 若v为点割集, 则称v为割点.理解：删除点后连通分支数

8、可能增加，会减少吗？8点割集点割集( (续续) )例例 v1,v4, v6是点割集是点割集, v6是割点是割点. v2,v5是点割集吗？是点割集吗？ 9边割集边割集n定义定义 设设 无无 向向 图图 G=, EE, 若若 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是边割集吗？是边割集吗？10n几点说明：几点说明：Kn无点割集（完全图）无点割集（完全图）n阶零图既

9、无点割集，也无边割集阶零图既无点割集，也无边割集.若若G连通，连通，E 为边割集，则为边割集，则p(G E )=2若若G连通，连通，V 为点割集，则为点割集，则p(G V ) 211有向图的连通性有向图的连通性 n设有向图设有向图D=u可达可达v: nu到到v有通路有通路. 规定规定u到自身总是可达的到自身总是可达的.n可达具有自反性和传递性可达具有自反性和传递性D弱连通弱连通(也称连通也称连通): n基图为无向连通图基图为无向连通图n有向边改为无向边后是连通图有向边改为无向边后是连通图D单向连通单向连通: n u,v V，u可达可达v 或或v可达可达u D强连通强连通: n u,v V，u与

10、与v相互可达相互可达n强连通强连通单向连通单向连通弱连通弱连通 12有向图的连通性有向图的连通性( (续续) ) (1)(2)(3)例例 下图下图(1)强连通强连通, (2)单连通单连通, (3) 弱弱连通连通每个顶点有进有出部分顶点有进有出13有向图的有向图的短程线与距离短程线与距离nu到v的短程线: u到v长度最短的通路 (u可达v)nu与v之间的距离d: u到v的短程线的长度若u不可达v, 规定d=.性质：n d0, 且d=0 u=vn d+d d 注意: 没有对称性147.3 图的矩阵表示图的矩阵表示 无向图的关联矩阵无向图的关联矩阵有向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向

11、图的邻接矩阵有向图的可达矩阵有向图的可达矩阵 15无向图的关联矩阵无向图的关联矩阵定定义义 设设无无向向图图G=, V=v1, v2, , vn, E=e1, e2, , em, 令令mij为为vi与与ej的的关关联联次次数数，称称(mij)n m为为G的关联矩阵的关联矩阵，记为，记为M(G). 性质性质16v1v2v4v3e1e2e3e4e5关联次数为可能取值为关联次数为可能取值为0，1，217无向图的相邻矩阵无向图的相邻矩阵v1v2v4v3e1e2e3e4e5(1)相邻矩阵是对称矩阵。(2)对角元素aii0,表示结点vi处有环。(3)如aij 1,表示vi与vj间有平行边。aij +2 1

12、8V1V2V3V4V5 V1 V2 V3 V4 V519有向图的关联矩阵有向图的关联矩阵定义定义 设无环有向图设无环有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 则称则称(mij)n m为为D的关联矩阵的关联矩阵，记为，记为M(D).20v4v1v2v3e1e2e3e4e5性质性质: (4) 平行边对应的列相同平行边对应的列相同21定义定义 设有向图设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 为顶点为顶点vi邻接到顶点邻接到顶点vj边的条数，边的条数，称称( )n n为为D的邻接矩阵的邻接矩阵, 记作记作A(D),

13、 简记为简记为A. 性质性质有向图的邻接矩阵有向图的邻接矩阵 22v2v1v4v323D中的通路及回路数中的通路及回路数定理定理 设设A为为n阶有向图阶有向图D的邻接矩阵的邻接矩阵, 则则Al(l 1)中中元素元素 为为D中中vi到到vj长度为长度为 l 的通路数，的通路数， 为为vi到自身长度为到自身长度为 l 的回路数，的回路数， 为为D中长度为中长度为 l 的通路总数，的通路总数， 为为D中长度为中长度为 l 的回路总数的回路总数. 24D中的通路及回路数中的通路及回路数(续续)例例 有向图有向图D如图所示如图所示, 求求A, A2, A3, A4, 并回答问题：并回答问题：(1) D中

14、长度为中长度为1, 2, 3, 4的通路各有多的通路各有多 少条？其中回路分别为多少条？少条？其中回路分别为多少条？(2) D中长度小于或等于中长度小于或等于4的通路为多的通路为多 少条？其中有多少条回路？少条？其中有多少条回路？ 推论推论 设设Bl=A+A2+Al(l 1), 则则Bl中元素中元素 为为D中长度小于或等于中长度小于或等于l 的通路数，的通路数， 为为D中长度小于或等于中长度小于或等于l 的回路数的回路数.25例例(续续) 长度长度 通路通路 回路回路 合计合计 50 818 1211 3314 1417 326有向图的可达矩阵有向图的可达矩阵 定义定义 设设D=为有向图为有向

15、图, V=v1, v2, , vn, 令令 称称(pij)n n为为D的可达矩阵的可达矩阵, 记作记作P(D), 简记为简记为P. 性质性质: P(D)主对角线上的元素全为主对角线上的元素全为1. D强连通当且仅当强连通当且仅当P(D)的元素全为的元素全为1.27有向图的可达矩阵有向图的可达矩阵( (续续) )例例 右图所示的有向图右图所示的有向图D的可达矩阵为的可达矩阵为28如何求有向图的可达矩阵n设D=为有向图，|V|=n, A为D的邻接矩阵；先求R（rij）A+A2+.+An再求可达矩阵P（pij）297.4 最短路径及关键路径最短路径及关键路径对于有向图或无向图对于有向图或无向图G的每

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

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

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

19、事项的最晚完成时间 TL(vi)：在保证收点v vn n的最早完成时间不增加的条件下的最早完成时间不增加的条件下，该事项vi最晚必须完成的时间，称为该点vi最晚完成时间，记为TL(vi)。因为有些工序不在关键路上,这些工序有个缓冲时间,稍迟一些时间动工，不会导致整个工程的完工时间，但这也有个限度，TL(vi)就是不耽误整个工程的最早完工条件下，该工序最迟的开工时间，过了这时间开工将影响整个工程。39n其算法是从收点开始向后计算其算法是从收点开始向后计算：n因v0和vn均在关键路上,TE（vn）=TL（vn），TE（v0）=TL（v0）= 0401234657824423326324051097

20、1315节点的最迟完工时间41n缓冲时间该事项在不影响整个工程的前提下，可以延滞的时间。TS(vi)TL(vi)TE(vi)42关键路径从发点v0出发到收点vn的一条路径，这条路上任何工序的延滞必导致整个工程的延滞。关键路是整个工程计划的主要矛盾。关键路至少一条，也能是不止一条 ，在关键路上TS（vi）=043节点12345678TE(vi)0426671315TL(vi)04410971315TS(vi)00243000其关键路径是v1, v2, v5, v7, v844v2v7v1v8v5v4v3v612023441344161. 最早完成时间最早完成时间：45v2v7v1v8v5v4v3v612023441344162. 最晚完成时间最晚完成时间：46v2v7v1v8v5v4v3v612023441344163. 缓冲时间缓冲时间：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=247v2v7v1v8v5v4v3v6120234413441648