第四章图与网络

第四章图与网络第一页，共五十五页，编辑于2023年，星期五图和网络图论广泛地应用与物理学、化学、控制论、信息、科学管理、电子计算机等领域。很多实际问题可以采用图论的理论和方法来解决。图论的历史最早可以追溯到1736年瑞士数学家E.Euler解决著名的哥尼斯堡七桥问题。第二页，共五十五页，编辑于2023年，星期五哥尼斯堡七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如图1所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。第三页，共五十五页，编辑于2023年，星期五哥尼斯堡七桥问题第四页，共五十五页，编辑于2023年，星期五图与网络的基本概念V1V2V3de2e3e6e4e5V4V5e1V={v1,v2,v3,v4,v5}E={e1,e2,e3,e4,e5}G=(V,E)端点；关联边无向边；有向边（弧）环（自回路）多重边简单图；多重图悬挂点网络第五页，共五十五页，编辑于2023年，星期五连通图点边序列；点边交替序列；在点边交替系列中，顺序排列的任意两条边均为相邻边，则称该点边交替序列为链；点边列中没有重复的点和重复边者称为初等链圈（回路）V1V2V3V4V5V6e1e2e3e4e5e6e7e8e9e10第六页，共五十五页，编辑于2023年，星期五链、路(1)第七页，共五十五页，编辑于2023年，星期五链、路(2)v1a1v2a2v3a7v4v5a4a3a8a9路：在一条链中，每条弧的方向与序列的走向一致，则称该链为路。回路：起点和终点重合与同一节点的路。回路与圈的区别是所有弧的方向一致。第八页，共五十五页，编辑于2023年，星期五图、子图、支撑子图第九页，共五十五页，编辑于2023年，星期五树一个无圈的连通图称为树。第十页，共五十五页，编辑于2023年，星期五树例：五个城市之间架设电话线。要求任何两个城市都可以相互通话（允许通过其他城市），并且电话线的根数最少。V2V1V3V4V5第十一页，共五十五页，编辑于2023年，星期五图的基本概念小结边、弧无向图、有向图无向图:(1)端点、相邻、关联边 (2)环、多重边、简单图(3)悬挂点(4)链、圈、初等链(5)连通图、支撑子图有向图:(1)始点、终点(2)路、回路第十二页，共五十五页，编辑于2023年，星期五割集v2v1v3v4v5v6abcdefghkv1v2v6v3v4v5在一个连通图中割集是一些边的集合，从G中移去这些边，则G不连通，并且不存在这些边的真子集使图不连通第十三页，共五十五页，编辑于2023年，星期五最短路问题设G=(V,E)为连通图，图中各边(vi,vj)有权

lij(lij=∞表示vi,vj之间无边)，vs,vt为图中任意两点，求一条路μ，使它是从vs到vt的所有路中总权数最小的路。第十四页，共五十五页，编辑于2023年，星期五最短路问题123434563234221第十五页，共五十五页，编辑于2023年，星期五EdsgerWybeDijkstra中文名：艾兹格·迪科斯彻家乡：荷兰出生年月：1930年5月11日去世年月：2002年8月6日成就：1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖1989年ACMSIGCSE计算机科学教育教学杰出贡献奖2002年ACMPODC最具影响力论文奖第十六页，共五十五页，编辑于2023年，星期五D氏标号法思路：从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。条件：网络中所有的弧权为非负。第十七页，共五十五页，编辑于2023年，星期五开始给发点标上P(Vs)=0,其余节点标上临时标号T(Vj)=∞，j≠1;设节点Vi是刚得到的P类标号，把与节点Vi有弧直接相连而又属于T类标号的各节点Vj的标号改为：

T(Vj)=min{T(Vj),P(Vj)+dij}在T类标号中选标号最小的节点Vj0，并把它的临时标号T(Vj0)改为P(Vj0)，若终点获得P类标号，则停止，否则转上一步。D氏标号法步骤第十八页，共五十五页，编辑于2023年，星期五最短路问题•••••••v1v2v7v5v4171344452572v3v6第十九页，共五十五页，编辑于2023年，星期五最短路求解图中()内的数表示P标号，[]内的数表示T标号。•••••••v1(0)v2v7v5v411344452572v3[∞]v6[∞][∞][∞][∞][∞]7

(1)首先给v1以P标号,P(v1)=0,其余所有点给T标号,T(vi)=+∞；第二十页，共五十五页，编辑于2023年，星期五最短路算法

(2)由于弧(v1,v2)、(v1,v3)、(v1,v4)属于D，且v2、

v3、

v4为T标号，所以修改这三个点的标号：

T(v2)=min{T(v2),P(v1)+ω12}=min{∞,0+4}=4

T(v3)=min{T(v3),P(v1)+ω13}=min{∞,0+2}=2

T(v4)=min{T(v4),P(v1)+ω14}=min{∞,0+5}=5•••••••v1(0)v2v7v5v411344452572v3[2]v6[4][5][∞][∞][∞]7第二十一页，共五十五页，编辑于2023年，星期五最短路算法(3)比较所有T标号，T(v3)最小，故令P(v3)=2•••••••v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]7第二十二页，共五十五页，编辑于2023年，星期五最短路算法(4)v3为刚得到P标号的点，考察弧(v3,v4)，(v3,v6)的端点v4,v6

T(v4)=min{T(v4),P(v3)+ω34}=min{5,2+2}=4

T(v6)=min{T(v6),P(v3)+ω36}=min{∞,2+7}=9•••••••v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]7第二十三页，共五十五页，编辑于2023年，星期五最短路算法

(5)比较所有T标号，T(v2),T(v4)最小，所以令P(v2)=P(v4)=4•••••••v1(0)v2v7v5v411344452572v3(2)v6[4][4][9][∞][∞]7第二十四页，共五十五页，编辑于2023年，星期五最短路算法•••••••v1(0)v2v7v5v411344452572v3(2)v6(4)(4)[9][∞][∞]7第二十五页，共五十五页，编辑于2023年，星期五最短路算法

(6)v2,v4为刚得到P标号的点,考察弧(v2,v5)，(v4,v5)，(v4,v6)的端点v5,v6

T(v5)=min{T(v5),P(v4)+ω45,P(v2)+ω25} =min{∞,4+3,4+4}=7

T(v6)=min{T(v6),P(v4)+ω46}=min{9,4+4}=8•••••••v1(0)v2v7v5v411344452572(4)(4)[8][7][∞]7v3(2)v6第二十六页，共五十五页，编辑于2023年，星期五最短路算法

(7)比较所有T标号，T(v5)最小，所以令P(v5)=7•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[∞][8]v3(2)v67第二十七页，共五十五页，编辑于2023年，星期五最短路算法•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[14][8]v3(2)v6(8)v5为刚得到P标号的点，考察弧(v5,v6)，(v5,v7)的端点v6,v7

T(v6)=min{T(v6),P(v5)+ω56}=min{8,7+1}=8

T(v7)=min{T(v7),P(v5)+ω57}=min{∞,7+7}=147第二十八页，共五十五页，编辑于2023年，星期五最短路算法

(9)比较所有T标号，T(v6)最小，所以令P(v6)=8•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[14](8)v3(2)v67第二十九页，共五十五页，编辑于2023年，星期五最短路算法

(10)v6为刚得到P标号的点，考察弧(v6,v7)的端点v7

T(v7)=min{T(v7),P(v6)+ω67}=min{14,8+5}=13•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[13](8)v3(2)v67第三十页，共五十五页，编辑于2023年，星期五最短路算法

(11)只有一个T标号T(v7)，令P(v7)=13，停止。•••••••v1(0)v2v7v5v411344452572(4)(4)(7)(13)(8)v3(2)v67

计算结果见上图，v1到v7的最短路为：同时得到v1到其余各点的最短路。第三十一页，共五十五页，编辑于2023年，星期五应用举例例：(设备更新问题)某企业在四年内都要使用某种设备，在每年年初作出是购买新设备还是继续使用旧设备的决策。若购买新设备就要支付购置费；若继续使用旧设备，则需支付维修费用。这种设备在四年之内每年年初的价格以及使用不同时间（年）的设备的维修费用估计为：年份1234年初购价10111213维修费用24714第三十二页，共五十五页，编辑于2023年，星期五应用举例问题：制定一个四年之内的设备更新计划，使得四年之内的设备购置费和维修费用之和最小。可以用求最短路问题的方法来解决总费用最少的设备更新计划问题。第三十三页，共五十五页，编辑于2023年，星期五最短路求法（2）构造长度矩阵L计算

其中第三十四页，共五十五页，编辑于2023年，星期五最短路求法（2）长度矩阵第三十五页，共五十五页，编辑于2023年，星期五最短路求法（2）表示vi到vj两步中距离最短的一条表示vi到vj两步不能到达第三十六页，共五十五页，编辑于2023年，星期五最短路求法（2）第三十七页，共五十五页，编辑于2023年，星期五最短路求法（2）第三十八页，共五十五页，编辑于2023年，星期五最短路求法（2）第三十九页，共五十五页，编辑于2023年，星期五最短路求法（2）求任意两点最短距离均为mxn矩阵第四十页，共五十五页，编辑于2023年，星期五最短路求法（2）矩阵中元素为两点间最顿距离第四十一页，共五十五页，编辑于2023年，星期五最大流引入输油管道网，如何安排各管道的输油量，才能使从vs到vt总油量最大？第四十二页，共五十五页，编辑于2023年，星期五最大流问题管道网络中每边的最大通过能力即容量是有限的，实际流量也并不一定等于容量；如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通常称为最大流问题。第四十三页，共五十五页，编辑于2023年，星期五基本概念容量：G=(V,E)，每条边上有非负数cij称为边的容量；发点（源），收点（汇），中间点；对G中的边（vi,vj）有流量fij,称集合f={fij}为网络G上的流；第四十四页，共五十五页，编辑于2023年，星期五基本概念可行流容量限制：对G中的每条边（vi,vj）,有平衡条件：对中间点vi,有对收点、发点有所谓最大流问题，就是在容量网络中，寻找流量最大的可行流。当fij=cij,则称流对边（vi,vj）是饱和的。第四十五页，共五十五页，编辑于2023年，星期五最大流－最小割第四十六页，共五十五页，编辑于2023年，星期五最大流－最小割在容量网络中割集是由vs到vt的必经之路，无论拿掉哪个割集，vs到vt便不再相通，所以任何一个可行流的流量不会超过任一割集的容量；定理：任一个网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量。第四十七页，共五十五页，编辑于2023年，星期五最