离散数学PPT课件2路与回路.ppt
《离散数学PPT课件2路与回路.ppt》由会员分享,可在线阅读,更多相关《离散数学PPT课件2路与回路.ppt(17页珍藏版)》请在咨信网上搜索。
1、2.路与回路 在实际应用中在实际应用中,比如在市内乘出租车去参观一个博览会比如在市内乘出租车去参观一个博览会,一定要司机选一条最短的路一定要司机选一条最短的路.到博览会后到博览会后,最好选一条这最好选一条这样到路径样到路径,使得每个展台都参观一次后使得每个展台都参观一次后,再回到原来存包再回到原来存包处处.这就是路与回路的问题这就是路与回路的问题.一一.路的概念路的概念 1.路的定义路的定义:给定图给定图G=设设v0,v1,v2,vnV,e1,e2,enE 其中其中ei是关联是关联vi-1,vi的边的边,则称结点和边的交叉序列则称结点和边的交叉序列v0 e1v1 e2v2envn是连接是连接v
2、0到到vn的路的路.v0是此路的起点是此路的起点,vn是是此路的终点此路的终点.路中含有的边数路中含有的边数 n称之为路的长度称之为路的长度.例如上图中例如上图中:v0 e2v3 e6v2是一条长度为是一条长度为2的路的路.v3 v2v1 v0e1e2e3e4e5e6如果图是个如果图是个简单图简单图,则路可以只用结点序列表示则路可以只用结点序列表示.如右图中如右图中,路路:abcad如果如果图是个图是个有向图有向图,则路可以则路可以只用边序列表示只用边序列表示.如有向图中如有向图中 e1 e5e2e3 e6 是一条路是一条路.2.回路回路:如果一条路的起点和终点是一个结点如果一条路的起点和终点
3、是一个结点,则称此路则称此路是是一个回路一个回路.如右图中的如右图中的 L1=v0 e1v1 e5v3 e6v2e4v0 L2=v0 e1v1 e5v3e2v03.迹与闭迹迹与闭迹 如果一条路中如果一条路中,所有所有边都不同边都不同,则称此路为则称此路为迹迹.如果一条如果一条回路回路中中,所有所有边都不同边都不同,则称此回路为则称此回路为闭迹闭迹.v3 v2v1 v0e1e2e3e4e5e6 cb a d v3 v2v1 v0e1e2e3e4e5e64.通路与圈通路与圈 如果一条路中如果一条路中,所有所有结点都不同结点都不同,则称此路为则称此路为通路通路.如果一条如果一条回路回路中中,除起点和
4、终点外除起点和终点外,其余其余结点都不同结点都不同,则则称称此回路为此回路为圈圈.例如右图中例如右图中:L1=v0 e1v1 e5v3 e6v2e4v0 L2=v0 e1v1 e5v3e2v0L3=v0 e1v1 e5v3 e2v0 e3v3 e6v2e4v0 L1和和L2是闭迹是闭迹,也是圈也是圈.L3是闭迹是闭迹,而不是圈而不是圈.v3 v2v1 v0e1e2e3e4e5e6定理定理8-2.1 在一个有在一个有n个结点的图中个结点的图中,如果从结点如果从结点vi到到vj存在存在一条路一条路,则从则从vi到到vj必存在一条长度不多于必存在一条长度不多于n-1的路的路.证明证明:设设vi到到v
5、j存在一条路存在一条路:vivi+1vi+2,vj,设此路的长度为设此路的长度为k.假设假设kn-1,则此路中有则此路中有 k+1个结点个结点,k+1n,而而G中只有中只有n个结点个结点,所以此路中必有两个结点相同所以此路中必有两个结点相同,假设假设vs=vt,(ts)于是此路为于是此路为:从图看出从图看出,此路中有一个从此路中有一个从vs到到vt的回路的回路,此回路中此回路中,有有t-s条条边边(t-s1),如果删去这个回路如果删去这个回路,就得到一条就得到一条vi到到vj更短的路更短的路.如果新的路长度还大于如果新的路长度还大于n-1,说明此路中还有回路说明此路中还有回路,再删去再删去回路
6、回路,如此进行下去如此进行下去.最后必可找到长度小于最后必可找到长度小于n-1的路的路.vs-1 vi+1 vt+1 vs=vt vs+1vi vt-1 vj vj-1.应用应用:摆渡人摆渡人Ferryman,狼狼Wolf,羊羊Sheep,干草干草Hay过河问过河问题题.如何摆渡使得它们不能互相伤害如何摆渡使得它们不能互相伤害.实际上实际上,这是个在图上这是个在图上找一条路的问题找一条路的问题.FWSH_ WHFSFS WHFSF WSFH HSFWFHFWFS WFS H HFS WFS FS HW SHFWFWFHF -HWFSFS二二.无向图的连通性无向图的连通性1.两个结点是连通的两个
7、结点是连通的:在无向图中在无向图中,结点结点u和和v之间如果存之间如果存在在一条路一条路,则称则称u与与v是连通的是连通的.我们规定我们规定:对任何结点对任何结点u,u与与u是连通的是连通的.2.结点之间的连通关系是个等价关系结点之间的连通关系是个等价关系.令令G=是无向图是无向图,R是是V上连通关系上连通关系,即即 R=|u和和v是连通的是连通的 显然显然R具有自反、对称和传递性具有自反、对称和传递性.于是可以求商集于是可以求商集V/R.例例1.给定图给定图G1如右上图所示如右上图所示:V/R=a,b,g,c,d,e,f,h例例2.给定图给定图G2如右下图所示如右下图所示:V/R=1,3,5
8、,2,4,6 gh a b ef c d 26 4 51 33.连通分支连通分支:令令G=是无向图是无向图,R是是V上连通关系上连通关系,设设R对对V的商集中有等价类的商集中有等价类V1,V2,V3,Vn,这这n个等价类构个等价类构成成的的n个子图分别记作个子图分别记作G(V1),G(V2),G(V3),G(Vn),并称并称它它们为们为G的连通分支的连通分支.并用并用W(G)表示表示G中连通分支数中连通分支数.下边例中下边例中 W(G1)=3 W(G2)=2 W(G3)=1 4.连通图连通图:如果一个图如果一个图G只有一个连通分支只有一个连通分支(W(G)=1),则称则称G是连通图是连通图.W
9、(G3)=1,G3是连通图是连通图 gh a b ef c d 26 4 51 3G1G2 G3定理定理8-2.2:图图G=是连通的是连通的,当且仅当当且仅当 对对V的任何分的任何分成成V1、V2的划分的划分,恒存在一条边恒存在一条边,使得它的两个端点分别使得它的两个端点分别属于属于V1和和V2.*证明证明:必要性必要性.已知已知G是连通的是连通的.令令V1,V2是是V的一个划的一个划分分.任取任取v1V1,v2V2,由于由于G是连通的是连通的,必存在一条路必存在一条路 v1.v2,在此路上必存在结点在此路上必存在结点u和和v,使得使得uV1,vV2,且且(u,v)是此路中是此路中的一条边的一
10、条边.充分性充分性:已知对已知对V的任何分成的任何分成V1、V2的划分的划分,恒存在一条边恒存在一条边,(反证法反证法)假设假设G不是连通的不是连通的.则则G至少有两个连通分支至少有两个连通分支G1、G2,令令V1=V(G1)V2=V-V(G1),根据连通分支定义知根据连通分支定义知,不不存存在端点分别属于在端点分别属于V1和和V2的边的边,与已知矛盾与已知矛盾.所以所以G是连通是连通的的.V1V2u vv1 v2.三三.割集割集(Cut Set)割集在图论中是个重要概念割集在图论中是个重要概念,在图论的理论和应用中在图论的理论和应用中,都具有重要地位都具有重要地位.比如有交通图比如有交通图:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 PPT 课件 回路
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。