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

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

2、2-12-162无向图p由点和边组成的图称为由点和边组成的图称为无向图无向图。2022-12-163无向图2022-12-164环、多重边、简单图、多重图2022-12-165点的次2022-12-166链、圈、连通图2022-12-167子图2022-12-168子图 v12022-12-169有向图 p由点和弧组成的图称为由点和弧组成的图称为有向图有向图。2022-12-1610环、多重弧、简单有向图 2022-12-1611点的出次和入次、路2022-12-1612网络的概念 2022-12-1613图的矩阵表示：关联矩阵 2022-12-1614图的矩阵表示：邻接矩阵 2022-12-

3、1615图的矩阵表示：权矩阵 2022-12-1616树与最小树问题 2022-12-1617树的概念和性质 v1v2v3v4v5v6432172022-12-1618树的概念和性质2022-12-1619支撑树 2022-12-1620用破圈法与避圈法求支撑树2022-12-1621最小树 破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。2022-12-1622最小树 5v1v2v3v4v5v6843752618【例例8.1】用破圈法求下图的最小树。用破圈法求下图的最小树。最小树长为最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的

4、最长边时，不能同时都去掉，只能去当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同度相同 2022-12-1623避圈法避圈法：取图：取图G的的n个孤立点个孤立点v1，v2，vn作为一个支撑作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）条边）v1v2v3v4v5v643521在上图中，如果添加边在上图中，如果添加边v1,v2就形成圈就形成圈v1,v2,v4，这时就应，这时就应避开添加边避开添加边

5、v1,v2，添加下一条最短边，添加下一条最短边v3,v6。破圈法和避圈法。破圈法和避圈法得到树的形状可能不一样，但最小树的长度相等得到树的形状可能不一样，但最小树的长度相等 5v1v3v515v2v4v684375268Min C(T)=152022-12-1624最小树的寻找方法：矩阵法2022-12-1625矩阵法举例2022-12-1626矩阵法2022-12-1627矩阵法举例2022-12-1628矩阵法举例2022-12-1629最短路问题在实际中具有广泛的应用，如管道铺设、线路选择最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结

6、为求最短等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题路问题 求最短路有两种算法：求最短路有两种算法：一是求从某一点至其它各点之间最短离的一是求从某一点至其它各点之间最短离的狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法 另一种是针对网络中有负权的另一种是针对网络中有负权的逐次逼近法。逐次逼近法。最短路问题，就是从给定的网络图中找出一点到各点或任意两最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路点之间距离最短的一条路 最短路问题2022-12-1630610123214675811165图图669【例例8.3】下图中的权下图中的权cij表示表示vi

7、到到vj的距离（费用、时间），从的距离（费用、时间），从v1修一条公路或架设一条高压线到修一条公路或架设一条高压线到v7，如何选择一条路线使距离最，如何选择一条路线使距离最短，建立该问题的网络数学模型。短，建立该问题的网络数学模型。2022-12-1631【解解】设设xij为选择弧为选择弧(i，j)的状态变量，选择弧的状态变量，选择弧(i，j)时时xij1，不，不选择弧选择弧(i，j)时时xij0，得到最短路问题的网络模型：，得到最短路问题的网络模型：(,)12(,)(,)57131467min102,3,610(,)ijiji jEijkii jEk iEijZc xxxxxxixxxi j

8、E或1，2022-12-1632Dijkstra标号法原理 2022-12-1633Dijkstra标号法原理2022-12-1634Dijkstra算法的具体步骤 2022-12-1635Dijkstra算法的具体步骤2022-12-16366101232146758111659(6,v1)(12,v1)(16,v3)(18,v3)(29,v5)【例例8.3】用用Dijkstra算法求下图所示算法求下图所示v1到到v7的最短路及最短路长的最短路及最短路长 v1 到到v7的最短路为：的最短路为：p17=v1,v2,v3,v5,v7，最短路长为，最短路长为L17=29 2022-12-1637D

9、ijkstra算法举例2022-12-1638Dijkstra算法举例2371845661341052759346822022-12-1639逐次逼近法 2022-12-1640逐次逼近法2022-12-1641逐次逼近法举例2022-12-1642逐次逼近法举例2022-12-1643逐次逼近法举例2022-12-1644逐次逼近法举例2022-12-1645最短链问题 2022-12-1646最短链问题2022-12-1647最短链问题举例2022-12-1648最短链问题举例 2022-12-1649最短链问题举例2022-12-1650最短链问题举例2022-12-1651最短链问题举

10、例2022-12-1652最短链问题举例2022-12-1653网络最大流问题 p所谓所谓最大流量问题最大流量问题就是：给一个带收发点的网络（一般就是：给一个带收发点的网络（一般收点用收点用vt表示，发点用表示，发点用vs表示，其余为中间点），其每条表示，其余为中间点），其每条弧的权值称之为容量，在不超过每条弧的容量的前提下，弧的权值称之为容量，在不超过每条弧的容量的前提下，要求确定每条弧的流量，得出从发点到收点的最大流量。要求确定每条弧的流量，得出从发点到收点的最大流量。p在交通运输、物资供应、通讯系统和财政金融等实际工在交通运输、物资供应、通讯系统和财政金融等实际工作中，常会遇到这类最大流

11、问题。作中，常会遇到这类最大流问题。2022-12-1654网络最大流问题2022-12-1655最大流有关概念2022-12-1656可行流与最大流 2022-12-1657增广链的概念2022-12-1658增广链的概念2022-12-1659截集和截量2022-12-1660截集和截量 2022-12-1661截集和截量2022-12-1662满足下例满足下例3个条件的流个条件的流fij 的集合的集合 f=fij 称为称为可行流可行流 1)0(,)ijijfci j（所有弧(3)stsjitvvvff发点发点vs流出的总流量等于流入收点流出的总流量等于流入收点vt的总流量的总流量(2)m

12、mimmjmvvffv所有中间点概念回顾2022-12-1663链：链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。从发点到收点的方向规定为链的方向。前向弧：前向弧：与链的方向相同的弧称为前向弧。与链的方向相同的弧称为前向弧。后向弧：后向弧：与链的方向相反的弧称为后向弧。与链的方向相反的弧称为后向弧。增广链增广链:设设 f 是一个可行流，如果存在一条从是一个可行流，如果存在一条从vs到到vt的链，满足：的链，满足：1.所有前向弧上所有前向弧上fij0则该链称为增广链则该链称为增广链前向弧前向弧后向

13、弧后向弧容量容量流量流量这是一条增这是一条增广链广链84469（5）(2)(3)(4)(6)2022-12-1664寻找网络最大流的Ford-Fulkerson标号法 2022-12-1665算法的步骤 2022-12-1666算法的步骤2022-12-1667算法举例2022-12-1668算法举例2022-12-1669算法举例2022-12-1670算法举例2022-12-1671算法举例2022-12-1672算法举例2022-12-1673算法举例2022-12-1674(14，10)(8，6)(5，3)(6，6)(3，3)(8，7)(3，0)(6，6)(3，1)(10，3)(4，1

14、)(7，7)【例例8.7】求下图发点求下图发点v1到收点到收点v7的最大流及最大流量的最大流及最大流量2022-12-1675无向图最大流标号算法无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已标号另一端已标号另一端vj未标号的边只要满足未标号的边只要满足 Cijfij0 则则vj就可标号就可标号（Cijfij）【例例8.8】求下图求下图v1到则到则v7标的最大流标的最大流(12,10)(9,6)(20,10)(8,8)(5,2)(8,3)(7,7)(6,6)(14,5)(13,13)(9,0)(16,13)

15、0,v1,2v4,2v5,2v6,22v2,276(12,12)(9,6)(20,10)(8,8)(5,4)(8,3)(7,7)(6,6)(14,7)(13,13)(9,2)(16,15)0,v1,3v4,3v5,3v6,112022-12-1677(12,12)(9,7)(20,10)(8,8)(5,4)(8,3)(7,7)(6,6)(14,8)(13,13)(9,3)(16,16)V=290,v1,10v3,5v4,5v5,5v4,178最小费用网络最大流问题 2022-12-1679最小费用最大流问题 2022-12-1680最小费用增广链 2022-12-1681求最小费用流的基本思想

16、 2022-12-1682辅助赋权有向网络的构造方法 2022-12-1683最小费用最大流算法步骤2022-12-1684最小费用最大流算法应用举例 2022-12-1685最小费用最大流算法应用举例2022-12-1686最小费用最大流算法应用举例2022-12-1687最小费用最大流算法应用举例2022-12-1688最小费用最大流算法应用举例2022-12-1689最小费用最大流算法应用举例2022-12-1690最小费用最大流算法应用举例2022-12-1691欧拉图2022-12-1692欧拉链、欧拉圈与欧拉图p欧拉链欧拉链 给定一个连通多重图给定一个连通多重图G，若存在一条链，经

17、过每边一次，若存在一条链，经过每边一次且仅一次，称这条链为欧拉链。且仅一次，称这条链为欧拉链。p欧拉圈欧拉圈 若存在一个简单圈，过每边一次，称这个圈为欧拉圈。若存在一个简单圈，过每边一次，称这个圈为欧拉圈。p欧拉图欧拉图 一个具有欧拉圈的图，称为欧拉图。一个具有欧拉圈的图，称为欧拉图。p上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧上面提到的哥尼斯堡七桥问题就是要在图中寻找一个欧拉圈。拉圈。2022-12-1693定理与推论定理与推论p定理定理1 连通多重图连通多重图G 是欧拉图的充要条件是图中的点全是欧拉图的充要条件是图中的点全为偶点。为偶点。p 定理定理2 连通多重图连通多重图G有欧拉链

18、，当且仅当有欧拉链，当且仅当G中恰有两个中恰有两个奇点。奇点。p上述两个定理可用来识别一个图能否一笔画出。上述两个定理可用来识别一个图能否一笔画出。2022-12-1694中国邮递员问题 p中国邮递员问题由我国学者管梅谷在中国邮递员问题由我国学者管梅谷在1962年首先提出。年首先提出。p所谓中国邮递员问题，是指如下问题：某一邮递员负责某所谓中国邮递员问题，是指如下问题：某一邮递员负责某街区的邮件投递工作，每次都要从邮局出发走遍他负责的街区的邮件投递工作，每次都要从邮局出发走遍他负责的所有街道，再回到邮局，他应如何安排投递路线，使所走所有街道，再回到邮局，他应如何安排投递路线，使所走的总路程最短

19、。的总路程最短。p中国邮递员问题的图论语言描述：给定一个连通图，在每中国邮递员问题的图论语言描述：给定一个连通图，在每边上边上ei上赋予一个非负的权上赋予一个非负的权w(ei),要求一个圈（未必是简单要求一个圈（未必是简单的），过每边至少一次，并使圈的总权最小。的），过每边至少一次，并使圈的总权最小。2022-12-1695中国邮递员问题求解考虑两种情形：考虑两种情形：p如果如果G是欧拉图，则从邮局出发，每边恰好走一是欧拉图，则从邮局出发，每边恰好走一次可回到邮局，这时总权必定最小；次可回到邮局，这时总权必定最小；p如果如果G不是欧拉图，则某些边必然要重复走，我不是欧拉图，则某些边必然要重复走

20、，我们当然要求重复走过的边的总长最小。我们可以们当然要求重复走过的边的总长最小。我们可以用用“奇偶点图上作业法奇偶点图上作业法”解决这一问题。解决这一问题。2022-12-1696“奇偶点图上作业法”相关定理2022-12-1697奇偶点图上作业法2022-12-1698奇偶点图上作业法举例2022-12-1699奇偶点图上作业法举例2022-12-16100奇偶点图上作业法举例2022-12-16101奇偶点图上作业法举例2022-12-16102奇偶点图上作业法举例2022-12-16103【例例】求解下图的中国邮路问题求解下图的中国邮路问题 35v1v2v4v5v6v74752618v341奇偶点图上作业法举例2022-12-16精品课件精品课件！精品课件精品课件！1065v1v2v4v5v6v743752618v34141【解解】最优解如下图最优解如下图14上图为最短欧拉回路，重复经过了上图为最短欧拉回路，重复经过了1，2和和6，7两条边两条边2022-12-16