第6章图与网络分析ppt课件.ppt

《第6章图与网络分析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图与网络的基本概念2021/8/121图及其分类图是点与线的集合。一个图由一些点及一些点之间的联线(不带箭头或带箭头)所组成。为了区别起见。把两点之间的不带箭头的连线称为边，带箭头的连线称为弧。用图来描述事物间的联系，不仅直观清晰，便于统观全局，而且网络图的画法简便，不必拘泥于比例和曲直。总之，这里所讲的图是反映对象之间关系的一种工具。2021/8/122无向图由点和边组成的图称为无向图。2021/8/123无向图2021/8/124环、多重边、简单图、多重图2021/8/125点的次2021/8

2、/126链、圈、连通图2021/8/127子图2021/8/128子图v1●2021/8/129有向图由点和弧组成的图称为有向图。2021/8/1210环、多重弧、简单有向图2021/8/1211点的出次和入次、路2021/8/1212网络的概念2021/8/1213图的矩阵表示：关联矩阵2021/8/1214图的矩阵表示：邻接矩阵2021/8/1215图的矩阵表示：权矩阵2021/8/1216树与最小树问题2021/8/1217树的概念和性质v1v2v3v4v5v6432172021/8/121

3、8树的概念和性质2021/8/1219支撑树2021/8/1220用破圈法与避圈法求支撑树2021/8/1221最小树破圈法：任取一圈，去掉圈中最长边，直到无圈。2021/8/1222最小树5v1v2v3v4v5v6843752618【例8.1】用破圈法求下图的最小树。最小树长为C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同2021/8/1223避圈法：取图G的n个孤立点｛v1，v2，…，vn}

4、作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n－1条边）v1v2v3v4v5v643521在上图中，如果添加边[v1,v2]就形成圈｛v1,v2,v4｝，这时就应避开添加边[v1,v2]，添加下一条最短边[v3,v6]。破圈法和避圈法得到树的形状可能不一样，但最小树的长度相等5v1v3v515v2v4v684375268×MinC(T)=152021/8/1224最小树的寻找方法：矩阵法2021/8/1225矩阵法举例2021/8/1226矩阵法2021/8/1227矩阵法举

5、例2021/8/1228矩阵法举例2021/8/1229最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题求最短路有两种算法：一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法另一种是针对网络中有负权的逐次逼近法。最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路最短路问题2021/8/1230①②③④⑤⑥⑦610123214675811165图6－69【例8.3】下图中的权cij表示vi

6、到vj的距离（费用、时间），从v1修一条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网络数学模型。2021/8/1231【解】设xij为选择弧(i，j)的状态变量，选择弧(i，j)时xij＝1，不选择弧(i，j)时xij＝0，得到最短路问题的网络模型：2021/8/1232Dijkstra标号法原理2021/8/1233Dijkstra标号法原理2021/8/1234Dijkstra算法的具体步骤2021/8/1235Dijkstra算法的具体步骤2021/8/1236②③

7、④⑤⑥⑦6101232146758111659(6,v1)①(12,v1)(16,v3)(18,v3)(29,v5)【例8.3】用Dijkstra算法求下图所示v1到v7的最短路及最短路长v1到v7的最短路为：p17=｛v1,v2,v3,v5,v7｝，最短路长为L17=292021/8/1237Dijkstra算法举例2021/8/1238Dijkstra算法举例2371845661341052759346822021/8/1239逐次逼近法2021/8/1240逐次逼近法2021/8/1241逐

8、次逼近法举例2021/8/1242逐次逼近法举例2021/8/1243逐次逼近法举例2021/8/1244逐次逼近法举例2021/8/1245最短链问题2021/8/1246最短链问题2021/8/1247最短链问题举例2021/8/1248最短链问题举例2021/8/1249最短链问题举例2021/8/1250最短链问题举例2021/8/1251最短链问题举例2021/8/1252最短链问题举例2021/8/1253网络最大流问题所谓最大流量问题就是：给一个带收发点的网络（一般收