第3讲 图论最短路问题.ppt

图论的介绍 哥尼斯堡七桥问題(Bridges of Koenigsberg) 欧拉路径解決哥尼斯保七桥问題 实际生活中的图论Graph Model 电路模拟 交通网络 有向图 Social Network 邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线。 最邻近算法： （1）选任意点作为始点，找出一个与始点最近的点，形成一条边的初始路径。然后用第（2）步方法逐点扩充这条路径。 （2）设x表示 最新加到这条路径上的点，从不在路径上的所有点中，选一个与x最邻近的点，把连接x与此点的边加到这条路径中。重复这一步，直至G中所有顶点包含在路径中。 （3）把始点和最后加入的顶点之间的边放入，这样就得出一个回路。 流动推销员需要访问某地区的所有城镇，最后回到出发点，问如何安排旅行路线使总行程最小. 行 遍 性 问 题 （一） 欧 拉 图 （二） 哈 密 尔 顿 图 邮递员问题 推销员问题 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 v3 v4 e1 e2 e4 e5 e3 v1 v2 v3 v4 e1 e2 e4 e5 e6 欧拉图 非欧拉图 返回 推论１　无向连通图G具有一条欧拉路径当且仅当G具有零个或两个奇数次数的 顶点。 在无向图G 中，如果任两结点可达，则称图G是连通的。 返回 哈 密 尔 顿 图 a b e c d 13 9 15 11 10 14 8 12 6 7 a b e c d 13 10 8 6 7 a b e c d 9 11 10 6 7 (a) (b) 返回 (2) a b c d e 2 3 3 5 2 4 2 a c 4 b 3 2 a c 4 5 5 8 d e 2 3 5 b 3 2 a c 4 练习 (1) 对上图用最邻近算法确定一条起始于a点的哈密尔顿回路； (2)若起始于d，重复（1）； (3)对上图确定一条最小哈密尔顿回路。 返回 * * 能不能走过每一个桥刚好一次并且回到原來的地方？ 原來是一笔画问题啊！ 数学家欧拉(Euler, 1707-1783) 于1736年严格的证明了上述哥尼斯堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式 例：Pspice、Cadence、ADS….. Pspice Cadence 航空网络! 捷運路線图！ 网络架构图 计算机网络 有单行道的街道！ 行程表！ High School Dating corporate e-mail Reference: Bearman, Moody and Stovel, 2004 image by Mark Newman Reference: Adamic and Adar, 2004 1、图 论 的 基 本 概 念 2、最 短 路 问 题 及 其 算 法 3、行 遍 性 问 题 图 论 的 基 本 概 念 一、 图 的 概 念 1、图的定义 2、顶点的次数 3、子图 二、 图 的 矩 阵 表 示 1、 关联矩阵 2、 邻接矩阵 返回 定义 有序三元组G=(V,E, )称为一个图. 图的定义 定义 常用术语： 返回 完备图 二 元 图 完 备 二 元 图 顶点的次数 例 在一次聚会中，认识奇数个人的人数一定是偶数。 返回 2 4 2 1 2 3 3 4 2 1 子图 返回 关联矩阵 注：假设图为简单图 返回 邻接矩阵 注：假设图为简单图 返回 最 短 路 问 题 及 其 算 法 一、 基 本 概 念 二、固 定 起 点 的 最 短 路 返回 基 本 概 念 返回 固 定 起 点 的 最 短 路 最短路是一条路径，且最短路的任一段也是最短路． 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树． 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路． 算法步骤： u0 u1 u2 u3 u4 u5 u6 u7 返回