第六章 图论与网络模型.ppt

图论概述 Euler——伟大的数学家 每对顶点之间的最短路问题 Dijkstra算法：求出图中一个顶点到其他各顶点的最短路。 在许多实际问题中，需要求出任意两点之间的最短路，如全国个城市之间的最短的航线、选址问题等。 若将图中每一个顶点依次视为起点，然后使用Dijkstra算法也可以解决，但需要大量的计算。 较好的算法：Floyd算法。 算法的基本思想 算法原理—— 求距离矩阵的方法 算法原理—— 求路径矩阵的方法 在建立距离矩阵的同时可建立路径矩阵R． 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径． i j 算法原理—— 查找最短路路径的方法 pk p2 p1 p3 q1 q2 qm 则由点i到j的最短路的路径为： 算法步骤 本问题可以调用Floyd算法程序。见文件 road2.m 应用举例：选址问题 为一个或几个服务设施在一定区域内选定它的位置，使其某一个指标达到最优值。 1、中心问题 有些公共服务设施（如急救中心、消防站等）的选址，要求网络中最远的被服务点离服务设施的距离尽可能小。 例3：某城市要建立一个消防站，为该市所属的七个区服务，如 图，问应设在哪个区，才能使它至最远区的路径最短。 Matlab程序代码见：road3.m 2、重心问题 有些公共服务设施（如邮局、学校等）的选址，要求设施到所有的服务对象点的距离总合最小。 例4：某城区要建立一所实验小学，要求覆盖该区的7个居民区，各居民区之间的距离如图所示，问学校建立在哪个居民区，才能使学生来往的平均路程最短。 Matlab程序代码见：road4.m 最 小 生 成 树 及 其 算 法 一、 基 本 概 念 二、 Prim(普利姆)算法 三、Kruskal(克鲁斯卡尔)算法 问题：现需从自来水厂接自来水管道到各个城镇，自来水厂到各城镇之间铺设自来水管道价格如下，问如何铺设最经济？ 水厂 8 5 3 1 9 10 7 6 A B C D E 分析： 1.显然，铺设的自来水管道要连接各个顶点； 2.若铺设的管道网中有回路，则去掉一条边仍可行。 故所铺设的管道是连接各个顶点且没有回路的图形，称为图的生成树。 树：任意两点之间只有一条路径的图。 性质： ⑴树中必不存在回路；树中任意两个不相邻顶点之间添一条 边后，就恰好含一个圈。 ⑵在树中任意去一条边，将会不连通。 ⑶具有n个结点的树的边恰好有n-1条；反之，要将n个点的树连接起来至少需要n-1条边。 最小生成树：在一个赋权图中，权 (树的所有边的权之和)最小的那棵树称为最小生成树。 一个连通图的最小生成树不唯一，但总权和一定相同。 求最小生成树的算法 Prim(普利姆)算法 kruskal(克鲁斯卡尔)算法 Prim(普利姆)算法 算法基本思路：设图 G=( V, E ) ①从顶点集V中任选一个顶点v1，将其涂红，其余顶点为白色。 ②在一个端点为红色，另一个端点为白色的边中，找一条权最小的边涂红，并把该边的白端点也涂成红色。 ③如此，每次将一条边和一个端点涂成红色，直到所有顶点都成红色为止。 例5：用prim算法求下图的最小生成树。 程序见prim.m Kruskal(克鲁斯卡尔)算法 算法基本思路：设赋权连通图 G，边集为E，顶点数为n。 开始时，G中的所有边均为白色。 ① 将所有顶点涂成红色。 ② 在白色边中，挑选一条权最小的边，使其与红色边不形成环，将该白色边涂成红色。 ③ 重复进行②中的步骤，直到有n-1条红色边，这n-1条红色边便构成最小生成树的边集合。 例6：用Kruskal算法求下图的最小生成树。 程序见Kruskal.m 行 遍 性 问 题 一、中 国 邮 递 员 问 题 二、推 销 员 问 题 （一） 欧 拉 图 （二） 中 国 邮 递 员 问 题 （一） 哈 密 尔 顿 图 （二） 推 销 员 问 题 V7 e3 v1 v2 v3 v4 e1 e2 e4 e5 V5 V6 e6 e7 e8 e9 割边 G的边e是割边的充要条件是e不含在G的圈中． 割边的定义：设G连通，e E(G),若从G中删除边e后，图G-{e}不连通，则称边e为图G的割边． e3 v1 v2 v3 v4 e1 e2 e4 e5 e6 欧 拉 图 e3 v1 v2 v3 v4 e1 e2 e4 e5 巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1 欧拉道路：v1e1v2e2v3e5v1e4v4e3v3 欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1 e3 v1 v2