d图论例子(北邮信通院陈鑫林教授授课PPT)_第1页
d图论例子(北邮信通院陈鑫林教授授课PPT)_第2页
d图论例子(北邮信通院陈鑫林教授授课PPT)_第3页
d图论例子(北邮信通院陈鑫林教授授课PPT)_第4页
d图论例子(北邮信通院陈鑫林教授授课PPT)_第5页
已阅读5页，还剩21页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

若干补充

11.Floyd算法在以下情况可以简化:(1)如有度数为1的端,可把它们去掉再做计算;设为度数为1的端,它只与相连,则与其它端的最短径必经,所以2(2)如有度数为2的端,则按下述方法去掉:设为度数为2的端,它只与相连,若,则可简单地去掉若,也可去掉,但把改成

3不论那种情况,与其它端间的最短径长用下述公式计算:(3)稀疏网的情况下可把全图分成几个部分来计算,然后合并.当网的边数远少于全联网的边数时,称稀疏网.此时往往存在割端或端数较少的割端.对于有割端的网G,去掉后就把G分成几部分(例如三部分G1,G2,G3),用Floyd算法分别求出的最短距离阵及路由阵.若则间最短距离为4例567892.次短径和可用径:若两端间有几条径,其中P1为最短径,而P2与P1无公共边却有公共端,则称P2不共边径或边分离径;若P3与P1除起终点外无公共端(必无公共边),则称P3为不共端径或端分离径.求次短径的方法1)对不共边径从图中去掉最短径的所有边,然后在剩下的图中求最短径;2)对不共端径从图中去掉最短径的所有中间端(当然段的关联边也去掉),然后在剩下的图中求最短径;10这个过程还可继续下去.例:11从到有三条径:12边分离的次短径13端分离的次短径14可用径在某些应用中,要求找一批满足条件的径.当有几个条件时,可先用一个条件求可用径,再在其中筛选出满足其它条件的可用径.今用限制条件为径长的例子来说明算法:仍用上图,要求径的长度小于M(=7)的可用径.1)用F算法求出图的最短径长矩阵W和转接矩阵R;2)若,则无可用径,

若,则找一个的邻接节点,如果则排除,否则就得一可用径15本例的距离矩阵,最短路径和转接矩阵分别如下16是可用径.再看V1与V3能否延续17与V1相连的有V2,与V3相连的有V2.与V2相连的有V4.18193.图的中心和中点从端间最短距离出发可定义网的中心,中点和直径一个端在网内的位置可用最长的最短径表示:

的最小值所对应的端定义为网的中心:网的中点可定义为平均最短径长最小的端:20网的直径:例21

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论