《图与网络》.ppt

该【《图与网络》 】是由【相惜】上传分享，文档一共【55】页，该文档可以免费在线阅读，需要了解更多关于【《图与网络》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第四章图与网络精选课件图和网络图论广泛地应用与物理学、化学、控制论、信息、科学管理、电子计算机等领域。很多实际问题可以采用图论的理论和方法来解决。。精选课件哥尼斯堡七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥,将河中的两个岛和河岸连结,如图1所示。城中的居民经常沿河过桥散步,于是提出了一个问题:能否一次走遍7座桥,而每座桥只许通过一次,最后仍回到起始地点。这就是七桥问题,一个著名的图论问题。精选课件哥尼斯堡七桥问题精选课件图与网络的根本概念V1V2V3de2e3e6e4e5V4V5e1V={v1,v2,v3,v4,v5}E={e1,e2,e3,e4,e5}G=(V,E)端点;关联边无向边;有向边〔弧〕环〔自回路〕多重边简单图;多重图悬挂点网络精选课件连通图点边序列;点边交替序列;在点边交替系列中,顺序排列的任意两条边均为相邻边,那么称该点边交替序列为链;点边列中没有重复的点和重复边者称为初等链圈〔回路〕V1V2V3V4V5V6e1e2e3e4e5e6e7e8e9e10精选课件链、路(1)精选课件链、路(2)v1a1v2a2v3a7v4v5a4a3a8a9路:在一条链中,每条弧的方向与序列的走向一致,那么称该链为路。回路:起点和终点重合与同一节点的路。回路与圈的区别是所有弧的方向一致。精选课件图、子图、支撑子图精选课件树一个无圈的连通图称为树。精选课件