广工管理运筹学第八章 图及网络分析.ppt

第八章 图与网络分析 引例 第1节 图与网络的基本知识 图与网络的基本概念（1） 图与网络的基本概念（2） 图与网络的基本概念（3） 图与网络的基本概念（4） 图与网络的基本概念（5） 图与网络的基本概念（6） 图与网络的基本概念（7） 图与网络的基本概念（8） 图中顶点次的性质 图与网络的基本概念（9） 图与网络的基本概念（10） 连通图（1） 连通图（2） 连通图（3） 连通图（4） 图的矩阵表示—邻接矩阵 图的矩阵表示—权矩阵 欧拉回路（1） 欧拉回路（2） 欧拉回路（3） 中国邮路问题 中国邮路问题解法（1） 中国邮路问题解法（2） 中国邮路问题解法（3） 中国邮路问题解法（4） 中国邮路问题解法（5） 中国邮路问题解法（6） 中国邮路问题解法（7） 树—树的概念 树—树的性质 定理6 T=(V, E), |V|=n, |E|=m, 则下列关于树的说法是等价的。 （1）T是一个树（即T是不含圈的连通图） 树—树的性质 （2）T无圈，且m=n-1 树—树的性质 （3）T连通，且m=n-1 树—树的性质 （4）T无圈，但每加一新边就得到唯一的一个圈 树—树的性质 （5）T连通，但任舍去一边就不连通 树—树的性质 （6）T中任意两点有唯一一条链相连 生成树—概念 生成树—解法（1） 避圈法的另一种表述 先去掉图G中所有边，只留下点，每次任意放回一条边，使之与已经放回的边不构成圈，反复进行，直到有（n-1）条边为止。 生成树—解法（2） 最小生成树—概念 最小生成树—解法1（Kruskal算法） 避圈法另一种表述 先去掉图G的所有边，只留下顶点，每次放回一条权最小的边，使之与已经放回的边不构成圈，反复进行，直到有（n-1）条边为止。 最小生成树—解法（2） 破圈法举例 根树 根树的应用 二叉树 最优二叉树（霍夫曼树） 霍夫曼算法 最短路问题 Dijkstra算法 Dijkstra算法步骤 例（p251） 4 6 5 4 4 7 7 9 6 5 5 4 1 0 4 9 6 8 ? ? ? 4 6 5 4 4 7 7 9 6 5 5 4 1 0 4 9 6 8 ? ? ? 5 2 4 3 6 3 4 5 9 4 4 4 第二步：调整可行方案。使重复边最多重复一次 5 2 4 3 6 3 4 5 9 4 4 4 5 2 4 3 6 3 4 5 9 4 4 4 第三步：检查图中每个初等圈是否满足定理条件（2），若不满足则进行调整。 5 2 4 3 6 3 4 5 9 4 4 4 5 2 4 3 6 3 4 5 9 4 4 4 第三步要求检查每个初等圈，这一步可能是相当繁琐的。例如上例中的图就包括下图所示的初等圈。 定义14 连通且不含圈的无向图称为树。树中次为1的点称为树叶，次大于1的点称为分枝点。 A B C D E F G H I J K L M N 厂长 人事科 财务科 总工程师 生产副厂长 新产品开发科 技术科 生产科 设备科 供应科 动力科 经营副厂长 销售科 检验科 T是边数最多的无圈图 T是边数最少的连通图 定义15 若图G的生成子图是一棵树，则称该树为图G的生成树（支撑树），或简称为图G的树。 定理7 图G有生成树的充分必要条件是图G是连通的 避圈法 这种方法是每步从连通图中选出一条边，使得它与已经选出的边不构成圈，直到选够n-1条边为止。 一个图的生成树不是唯一的。 5个顶点， 4条边 破圈法 这种方法是每步从连通图中选一个圈，并去掉该圈的一条边，直到图中不含圈为止。 另一种解法 定义16 连通图G=(V, E), 每条边上有非负权L(e)，一棵生成树上各边的权之和，称为这棵生成树的权，具有最小权的生成树，称为最小生成树（最小支撑树），简称最小树。 例如 如何用造价最省的电话线网将各有关单位连起来的问题，就归结为求最小生成树的问题。 3 5 4 3 6 7 1 2 4 非最小树 避圈法： 这种方法每步从图中挑选一条边，满足：（1）它与已经选出的边不构成圈；（2）它是满足条件（1）的权最小的边，直到选够n-1条边为止。 1 4 1 2 1 3 1 4 4 5 5 3 2 4 5 2 1 4 1 2 1 3 1 4 4 5 5 3 2 4 5 2 9个顶点，8条边 9 4 8 2 3 3 3 7 9 1 4 2 3 3 1 6个顶点，5条边 破圈法： 这种方法每步从图中任选一个圈，然后去掉该圈中权最大的边，直到图中没有圈为止。 1 4 1 2 1 3 1 4 4 5 5 3 2 4 5 2 9个顶点，8条边 9 4 8 2 3 3 3 7 9 1 9 4 8 2 3 3 3 7 9 1 6个顶点，5条边 破圈法举例 v4 v2 v3 v1 6 2 1 5 8 4 6 最小生成树的权= 9 // v4 v2