《广工管理运筹学第八章 图与网络分析.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 ? ? ? Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4 6 5 4 4 7 7 9 6 5 5 4 1 0 4 9 6 8 13 14 ? 4 6 5 4 4 7 7 9 6 5 5 4 1 0 4 9 6 8 13 14 17 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4 6 5 4 4 7 7 9 6 5 5 4 1 0 4 9 6 8 13 14 15 4 6 5 4 4 7 7 9 6 5 5 4 1 0 4 9 6 8 13 14 15 最短路线见图 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 5 2 4 3 6 3 4 5 9 4 4 4 第二步：调整可行方案。使重复边最多重复一次 5 2 4 3 6 3 4 5 9 4 4 4 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 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 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第三步要求检查每个初等圈，这一步可能是相当繁琐的。例如上例中的图就包括下图所示的初等圈。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 As