2011年5月9日网络规划.pptVIP

本章内容 问题的提出 “中国邮路问题” 某一邮递员负责某街区的邮件投递工作，每次都要从邮局出发走遍他负责的所有街道，再回到邮局，那么他该如何安排投递路线，使所走过的总路程最短？ “环球旅行”问题 哈密尔顿在1859年提出了一个所谓周游世界问题：用一个正十二面体的20个顶点表示全世界的20个大城市，要从某一城市出发，沿着多面体的棱旅行，并且每个城市恰好经过一次，最后回到出发的城市，问这样的旅行路线是否存在。 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。? 例1（铁路交通图）图1是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。 一、图与网络的基本知识 例2:（球队比赛图）有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队。它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图2所示的有向图反映出来。 1.图的基本概念 例 1: 铁路交通图 例 2: 球队比赛图 1、点: 表示研究对象. 2、连线：表示两个对象之间的某种特定关系。 3、图(Groph):点(vertex)和连线的集合. 4、不带箭头的连线称为边(edge).带箭头的连线称为弧(Arc). 5、无向图：连线不带箭头的图，简称图， 表示为： G=（V，E） V--点集合 E--边集合 例：右图 1.图的基本概念 6、边的端点：e是连接u,v两点的一条边， 则称u,v 是边e的两个端点，并称点 u和v是相邻的。 1.图的基本概念 8.相邻: (1)边相邻:两条边有公共的端点,如图中e1,e2,e5,e6有公共端点v1. (2)点相邻:两点有公共的关联边,如图中v1,v4有公共关联边e5. 1.图的基本概念 9.环:两端点相重的边（若u=v, e是环） 如图中e7. 10.多重边:两条以上边所连的端点相同（两点之间多于一条边）,如图中e1,e2. 1.图的基本概念 11.简单图:无环、无多重边的图(如图b). 1.图的基本概念 12.次(也称为度)(degree): 某一点具有的关联边的数目（以点v为端点的边的个数称为点v 的次）,表示为: d(v) 如图中d(v1)=4， d(v2)=3 ，d(v4)=4(环记两度) 1.图的基本概念 13.孤立点:次为“0”的点,如图中v5; 子图 5.2 树图及图的最小支撑树 树图及图的最小支撑树 网络的支撑树 支撑树的变换 最小支撑树问题 最小支撑树的求法－Kruskal算法 开始将G的所有边按权从小到大的次序排列出来，然后逐边检查。首先把最短的一条边留下来，然后在检查每一条边时，若它不与已留下的边形成圈，就留下来，否则就去掉，直至所有被留下来的边形成支撑树时，计算终止。 最小支撑树的求法－Kruskal算法 最小支撑树的求法－Kruskal算法 最小生成树的求法－ Prim算法 例1.一个乡有9个自然村，其间道路各长度如图所示，各边权表示距离，问如何拉线才能使电话线最短。 v1 v2 v3 v4 v5 v6 v7 v8 v0 4 1 1 5 4 4 2 5 2 5 4 2 1 1 3 3 * 第五章 网络规划 图与网络的基本概念 最小支撑树问题 最短路径问题 网络最大流问题 网络最小费用流问题 德国哥尼斯堡七桥问题 一个人如何一次连续走过七座桥且每座桥只走一次回到出发点? A D B C 在图中某点出发，经过每边一次且仅一次回到出发点（1736）。 在图中找一条经过每边的最短路——类似带权的欧拉回路。 在图中找一条经过每个点一次且仅一次的路——哈密尔顿回路。 “货郎担问题” 一个货郎要去若干城镇售货，已经知道各城镇之间的距离（设各城镇之间都有交通线相联接），那么货郎应如何选择行走路线，使每个城镇恰好经过一次，并回到原出发地，并使总行程最短。这一问题也称旅行售货员问题。 在图中找一条经过每个点一次且仅一次的最短路——带权的哈密尔顿回路。 太原 重庆 武汉 南京 徐州 连云港 上海 郑州 石家庄 塘沽 青岛 济南 天津 北京 图1 v3 v1 v2 v4 v6 v5 图2 太原 重庆 武汉 南京 徐州 连云港 上海 郑州 石家庄 塘沽 青岛 济南 天津 北京 图1 v3 v1 v2 v4 v6 v5 图2 V={v1，v2，v3，v4} E={e1，e2，…,e7} 1.图的基本概念 5’、如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V, A)，其中V 表示有向图D 的点集合，A 表示有向