[所有分类]第五章 图论11.ppt

图论 什么是图？ 图论中所谓的图是由一些点(vertices)，和一些连接兩点的边(edges)所形成的 哥尼斯堡七桥问題: 要如何走过每座桥恰一次，再返回出发点？ 图论应用举例 例如，在组织生产中，为完成某项任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。 一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。 各种通信网络的合理架设 交通网络的合理分布等 基本概念 图的矩阵表示 1. 邻接矩阵 Adjacency matrix 表示图中两点之间的相互关系 两点之间有弧或边的，用1表示，否则用0表示，构成一个矩阵A 有向图 矩阵A的元素全为0的行所对应的点称为汇点 上图v8 矩阵A的元素全为0的列所对应的点称为源点 上图v1、v9 树及其性质 树： 既简单又很有用 树：一个无圈的连通图 组织结构图 荣国公 定理 定理1：设G=(V, E)是一个树，p(G)=2，则G中至少 有两个悬挂点。 定理2：图G=(V, E)是一个树的充要条件是G不含圈， 且恰有p-1条边。 定理3：图G=(V, E)是一个树的充要条件是G是连通 图，且q(G)=p(G) -1。 定理4：图G=(V, E)是一个树的充要条件是任意两个 顶点之间恰有一条链。 推论 从一个树中去掉任意一条边，则余下的图是不连通的。 在树中不相邻的两个点间添上一条边，则恰好得到一个圈 图的支撑树 设图T=(V, E )是图G=(V, E)的一个支撑子图，如果T是一个树，则称T是G的一个支撑树 定理5：图G有支撑树的充要条件是图G是连通的。 破圈法：任取一个圈， 从中去掉一条边，再 对余下的图重复直到 不再含图时为止。 破圈法 避圈法 在图中任取一条边，找到一条与之不构成圈的边，再找一条前两边不构成圈的边 重复直到不再能进行为止 取出的边数为p-1条 避圈法 最小支撑树问题 给定图 G=(V, E)，对 G 中的每一条边 [vi, vj] ，相应地有一个数 wij，则称这样的图为赋权图 wij 称为边 [vi, vj]上的权 权是与边有关的数量指标，可以是距离、时间、费用等。 赋权图不仅指出各个点之间的邻接关系，而且同时也表示出各点之间的数量关系 广泛应用于解决工程技术及管理等领域的最优化问题 最小支撑树问题就是赋权图上的最优化问题之一。 设有一个连通图G=(V, E)，每一边 e=[vi, vj] 有一个非负权 w(e)=wij ( wij0) 如果T=(V, E )，是 G 的一个支撑树，称E中所有边的权之和为支撑树 T 的权，记为 w(T) 如果支撑树 T* 的权 w(T*) 是 G 的所有支撑树的权中最小者，则称T*是 G 的最小支撑树 （最小树），即 最小支撑树问题就是要求G的最小支撑树。 方法有二： 避圈法Kruskal 破圈法 常见求赋权图的最小树。 例5.4 某厂内联结六个车间的道路网如下所示，已知每条路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。 避圈法求最小支撑树 破圈法求最小支撑树 矩阵计算方法 矩阵计算结果 例5.6 如图所示的单行线交通网，每弧旁的数字表示这条单行线的距离。现在某人要从 v1 出发，通过这个交通网到达 v8 ，求使总距离最短的旅行线路。 路很多 最短路算法 如果P是D中从 vs 到 vi 的最短路， vi 是P中的一个点，那么从 vs 沿P到 vi 的路是从 vs 到 vi 的最短路。 1. 图形的标号法 2. 所有wij≥0的情形—Dijkstra法1959 先标出离终点最近的一段，然后标号与该点距离最短的点，继续逆推至始点。 2.Dijkstra法 基本思路：从vs出发，逐步地向外探寻最短路。 执行过程中，与每个点对应，记录下一个数 (称为此点的标号)， 它或者表示从vs到该点的最短路的权 (称为P标号) 或者是从vs到该点的最短路的权的上界 (称为T标号) 方法的每一步是修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的点多一个， 如此经过 p-1 步，就可以求出从vs到各点的最短路。 Dijkstra法具体步骤 开始(i=0)，令S0={vs}, P(vs)=0, λ(vs)=0, 对每一个v≠ vs，令 T(v)=+∞, λ(v)=M, 令k=s 1. 如果Si=V，算法终止，这时，对每个v?Si，d(vs, v)= P(v) ；否则转入步骤2 2. 考察每个使(vk, vj)?A且vj?Si的点vj。如果T(v) P(