离散数学图论PPT课件图论2

离散数学图论PPT课件图论2null7.2 通路、回路与图的连通性 7.2 通路、回路与图的连通性简单通(回)路, 初级通(回)路, 复杂通(回)路无向连通图, 连通分支弱连通图, 单向连通图, 强连通图点割集与割点边割集与割边(桥) 通路与回路通路与回路定义给定图G=（无向或有向的），设G中顶点与边的交替序列=v0e1v1e2…elvl， (1) 若i(1il), vi1 和 vi是ei的端点(对于有向图, 要求vi1是始点, vi是终点), 则称为通路, v0是通路的起点, vl是通路的终点, l为通路的长...

null7.2 通路、回路与图的连通性 7.2 通路、回路与图的连通性简单通(回)路, 初级通(回)路, 复杂通(回)路无向连通图, 连通分支弱连通图, 单向连通图, 强连通图点割集与割点边割集与割边(桥) 通路与回路通路与回路定义给定图G=（无向或有向的），设G中顶点与边的交替序列=v0e1v1e2…elvl， (1) 若i(1il), vi1 和 vi是ei的端点(对于有向图, 要求vi1是始点, vi是终点), 则称为通路, v0是通路的起点, vl是通路的终点, l为通路的长度. 又若v0=vl，则称为回路. (2) 若通路(回路)中所有顶点(对于回路, 除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径, 初级回路又称作圈. (3) 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路).通路与回路(续)通路与回路(续)说明: 在无向图中，环是长度为1的圈, 两条平行边构成长度为2的圈. 在有向图中，环是长度为1的圈, 两条方向相反边构成长度为2的圈. 在无向简单图中, 所有圈的长度3; 在有向简单图中, 所有圈的长度2. 若无向图G中每个顶点的度数至少为2，则G中包含一个圈通路与回路(续) 通路与回路(续) 定理在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的初级回路. 无向图的连通性无向图的连通性设无向图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短程线与距离短程线与距离u与v之间的短程线: 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=v d(u,v)=d(v,u)（对称性） d(u,v)+d(v,w)d(u,w) （三角不等式)点割集点割集记 Gv: 从G中删除v及关联的边 GV: 从G中删除V中所有的顶点及关联的边 Ge : 从G中删除e GE: 从G中删除E中所有边定义设无向图G=, 如果存在顶点子集VV, 使p(GV)>p(G)，而且删除V的任何真子集V后（ VV），p(GV)=p(G), 则称V为G的点割集. 若{v}为点割集, 则称v为割点.点割集(续)点割集(续)例 {v1,v4}, {v6}是点割集, v6是割点. {v2,v5}是点割集吗？边割集边割集定义设无向图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}是边割集吗？几点说明： Kn无点割集 n阶零图既无点割集，也无边割集. 若G连通，E为边割集，则p(GE)=2 若G连通，V为点割集，则p(GV)2 有向图的连通性有向图的连通性设有向图D= u可达v: u到v有通路. 规定u到自身总是可达的. 可达具有自反性和传递性 D弱连通(连通): 基图为无向连通图 D单向连通: u,vV，u可达v 或v可达u D强连通: u,vV，u与v相互可达强连通单向连通弱连通有向图的连通性(续) 有向图的连通性(续) 有向图的短程线与距离有向图的短程线与距离u到v的短程线: u到v长度最短的通路 (u可达v) u与v之间的距离d: u到v的短程线的长度若u不可达v, 规定d=∞. 性质： d  0, 且d = 0  u=v d + d  d 注意: 没有对称性7.3 图的矩阵表示 7.3 图的矩阵表示无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵无向图的关联矩阵无向图的关联矩阵null关联次数为可能取值为0，1，2有向图的关联矩阵有向图的关联矩阵null有向图的邻接矩阵有向图的邻接矩阵定义设有向图D=, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令为顶点vi邻接到顶点vj边的条数，称( )nn为D的邻接矩阵, 记作A(D), 简记为A. 性质nullD中的通路及回路数D中的通路及回路数D中的通路及回路数(续)D中的通路及回路数(续)例有向图D如图所示, 求A, A2, A3, A4, 并回答问题： (1) D中长度为1, 2, 3, 4的通路各有多少条？其中回路分别为多少条？ (2) D中长度小于或等于4的通路为多少条？其中有多少条回路？例(续)例(续) 长度通路回路合计 50 818 1211 3314 1417 3有向图的可达矩阵有向图的可达矩阵有向图的可达矩阵(续)有向图的可达矩阵(续)例右图所示的有向图D的可达矩阵为null7.4 最短路径及关键路径对于有向图或无向图G的每条边，附加一个实数w(e)，则称w(e)为边e上的权. G连同附加在各边上的实数，称为带权图. 设带权图G=,G中每条边的权都大于等于0.u,v为G中任意两个顶点，从u到v的所有通路中带权最小的通路称为u到v的最短路径. 求给定两个顶点之间的最短路径，称为最短路径问题. null算法：Dijkstra(标号法)null例：求图中v0与v5的最短路径nullv0v1v2v4v3null2.关键路径问题定义：PERT图设D=是n阶有向带权图 D是简单图 D中无环路有一个顶点出度为0，称为发点；有一个顶点入度为0，称为收点记边的权为wij,它常常表示时间 null1. 最早完成时间：自发点v1开始，沿最长路径（权）到达vi所需时间，称为vi的最早完成时间，记为TE（vi），i=1,2,…,nnull2. 最晚完成时间：在保证收点vn的最早完成时间不增加的条件下，自发点v1最迟到达vi所需时间，称为vi的最晚完成时间，记为TL（vi）.null3. 缓冲时间：TS(vi)=TL(vi)- TE(vi) TS(v1)= TS(v3)= TS(v7)= TS(v8)=0 TS(v2)=2-1=1; TS(v4)=6-4=2; TS(v5)=10-8=2; TS(v6)=11-9=2

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

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

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

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

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

立即下载

离散数学图论PPT课件 图论2

你可能还喜欢

离散数学图论PPT课件图论2