管理运筹学 课件 08图与网络分析

运筹学

OPERATIONSRESEARCH第8章图与网络分析授课教师：黄永涛哥尼斯堡是位于波罗的海东岸一座古老而美丽的城市，布勒格尔河的两条支流在这里汇合，然后横贯全城，流入大海。河心有一个小岛。河水把城市分成了４块，于是，人们建造了７座各具特色的桥，把哥尼斯堡连成一体。

一天又一天，７座桥上走过了无数的行人。不知从什么时候起，脚下的桥梁触发了人们的灵感，一个有趣的问题在居民中传开了。导课：哥尼斯堡七桥问题问题：如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。导课：哥尼斯堡七桥问题哥尼斯堡七桥问题引起了大数学家欧拉的兴趣。他知道，如果沿着所有可能的路线都走一次的话，一共要走5040次。就算是一天走一次，也需要13年多的时间。导课：哥尼斯堡七桥问题欧拉的想法是：两岸的陆地与河中的小岛，都是桥梁的连接点，它们的大小、形状均与问题本身无关。因此，不妨把它们看作是4个点。7座桥是7条必须经过的路线，它们的长短、曲直，也与问题本身无关。因此，不妨任意画7条线来表示它们。导课：哥尼斯堡七桥问题这样，欧拉将七桥问题抽象成了一个“一笔画”问题，从而否定了问题的答案。导课：哥尼斯堡七桥问题导课：哥尼斯堡七桥问题欧拉的推理：凡是一笔画中出现的交点处，线一出一进总应该通过偶数条（偶点），只有作为起点和终点的两点才有可能通过奇数条（奇点）。欧拉这种处理问题的方法标志着图论的诞生8运筹学中研究的图用来表明一些研究对象

和这些对象之间的相互关系。9运筹学中研究的图用来表明一些研究对象

和这些对象之间的相互关系。应用领域：物理化学控制论信息论计算机科学经济与管理§6.1图的基本概念与模型§6.2树图和图的最小部分树§6.3最短路问题第六章图与网络分析§6.5网络的最大流主要内容：§6.4中国邮路问题§6.1．图的基本概念与模型

1、图：由点以及连接点的边构成的集合。一、基本概念记做G={V,E}，V是点的集合，E是边的集合。运筹学中的图与几何学中图的区别

图中的点用

v

表示，边用

e表示，每条边可用它所联结的点表示：e1=[v1,v1]，e2=[v1,v2]或e2=[v2,v1]

2、网络图：给图中的点和边赋以具体的含义和权值。3、端点，关联边，相邻

若边e可表示为e

=[vi,vj]，称vi

和vj是边e的端点，同时称边e为点vi

和vj的关联边，若点vi,vj与同一条边关联，称点vi

和vj相邻；若边ei与ej有公共端点，称边ei

和ej相邻；

如果边e

的两个端点相重，称该边为环，如果两个点之间的边多于一条，称为具有多重边，对无环、无多重边的图称为简单图。4、环，多重边，简单图5、次，奇点，偶点，孤立点

与某个点相关联的边的数目，称为该点的次，记作d(v)。次为奇数的点称为奇点，次为偶数的点称为偶点，次为零的点称为孤立点。如图：奇点为v5，v3偶点为v1,v2,

v4,

v6孤立点为

v66、链，圈，路，回路，连通图起点和终点重合的链称为圈如：如：图中有些点和边的交替序列μ={v0,e1,v1,e2,…,

ek

,vk}，若其各边e1,e2,…,ek

各不相同，且任意

vi,t-1,vit(2≤t≤k)都相邻，称μ为链。6、链，圈，路，回路，连通图如果链中所有的顶点v0,v1,…,vk也

不相同，这样的链称为路。如：起点和终点重合的路称为回路。若在一个图中，每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图为不连通的。7、完全图，偶图

一个简单图中若任意两点之间均有边相连，称这样的图为完全图，含有

n

个顶点的完全图，其边数有条。7、完全图，偶图如果图的顶点能分成两个互不相交的非空集合V1和V2,使在同一集合中任意两个顶点均不相邻，称这样的图为偶图。

如果偶图的顶点集合V1和V2

之间的每一对顶点都有一条边相连，称这样的图为完全偶图，

若完全偶图中V1含m个顶点，V2有n个顶点，则其边数共m·n条。8、子图，部分图

图G1={V1,E1}和G2={V2,E2}，如果有和，称G1是G2的一个子图；若有，则称G1是G2的一个部分图。子图：部分图一、基本概念图、网络图端点、关联边、相邻环、多重边、简单图次、奇点、偶点、孤立点链、圈、路、回路、连通图完全图、偶图子图、部分图§6.1．图的基本概念与模型§6.1．图的基本概念与模型二、图的模型BACD

图的模型：比赛顺序的表示【例】有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如下表所示，打√的是各运动员报名参加的比赛项目。问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。ACBEDFABCDEF甲√√√乙√√丙√√√丁√√√戊√√√己√√√比赛顺序ABECDF§6.2树图和最小部分树

树图（简称树，记作T(V,E)）是无圈的连通图。

（无圈，无多重边）6.2.1树的性质性质1.任何树中必存在次为1的点。

性质2.具有

n

个顶点的树恰有（n-1）条边。

性质3.任何具有n个点、(n-1)条边连通图是树。6.2.2图的最小部分树如果G1是G2的部分图，又是树图，则称G1是G2

的部分树；树图的各条边称为树枝(假定各边均有权重)；树枝总长最小的部分树，称为该图的最小部分树。6.2.2图的最小部分树定理1.图中任一个点i，若j

是与i相邻点中距离最近的，则边[i,j]一定包含在该图的最小部分树中。推论.把图的所有点分成V和两个集合，则两集合之间连线的最短边一定包含在最小部分树内。6.2.3避圈法和破圈法例：如图所示，S、A、B、C、D、E、T代表村镇，连线表明各村镇间现有道路交通情况，连线旁数字代表道路的长度。要求沿图中道路架设电线，使村镇全部通上电，应如何架设线路使线路的总长度为最短。27一、避圈法求图的最小树1.从图中任选一点vi，让vi

∈V，

图中其余点均包含在中；2.从V

与的连线中找出最小边，这条边一定包含在最小部分树中，不妨设这条边为[vi,vj]将其加粗，标记为最小部分树中的边。3.令V∪vj→V，-vj→4.重复2、3两步，直到图中所有点均包含在V中。例：如图所示，S、A、B、C、D、E、T代表村镇，连线表明各村镇间现有道路交通情况，连线旁数字代表道路的长度。要求沿图中道路架设电线，使村镇全部通上电，应如何架设总的线路长度为最短。一、避圈法求图的最小树解：用避圈法构造下图的最小部分树。1.在点集中任选一点，不妨取S，令V={S

}

2.找到和S

相邻的边中，权值最小的[S,A]。3.V={S,A

}4.重复第2，3步，找到下一个点。练习(1)-用避圈法求最小部分树78242321746615433练习(2)-用避圈法求最小部分树52232125332242236.2.3避圈法和破圈法例：如图所示，S、A、B、C、D、E、T代表村镇，连线表明各村镇间现有道路交通情况，连线旁数字代表道路的长度。要求沿图中道路架设电线，使村镇全部通上电，应如何架设总的线路长度为最短。二、破圈法求图的最小树6.2.3避圈法和破圈法二、破圈法求图的最小树步骤：从图N中任取一回路，去掉这个回路中边权最大的

边，得到原图的一个子图N1。从剩余的子图中任找一回路，同样去掉回路中边权最大

的一条边，得一新的子图；3.重复第2步，直到图中不再含有回路为止。用破圈法求解上例：任意找到一回路，不妨取DETD，

去掉边权最大的边[T,E];从剩余的子图中任找一回路，去掉回路中

边权最大的边，得新的子图；依次类推。78242321746615433练习(1)-用破圈法求最小部分树5223212533224223练习(2)——用破圈法求最小部分树§6.1图的基本概念与模型§6.2树图和图的最小部分树§6.3最短路问题第六章图与网络分析§6.5网络的最大流主要内容：§6.4中国邮路问题§6.3最短路问题一、定义：最短路问题是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。距离只是权数的代称，在实际的网络图中，权数可以是时间、费用等。选址问题管道铺设选线问题设备更新问题投资问题可以归结为最短路问题§5.3最短路问题一、定义：最短路问题是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。二、最短路的求法：1.从某一点至其它各点之间最短距离的狄克斯屈拉(Dijksrta)算法——标号法2.求网络图中任意两点之间的最短距离的矩阵算法。距离只是权数的代称，在实际的网络图中，权数可以是时间、费用等。一、标号法基本思路：如果v1→v2→v3→v4是v1→v4

的最短路径，则v1→v2→v3

一定是v1→v3

的最短路径。v2→v3→v4

一定是v2→v4的最短路径。§5.3.1标号法二、举例例.求下图中从v1到v7的最短路。例.求下图中从v1到v7的最短路。1.对起始点v1，因L11

=0，将0标注在v1

旁的小方框内，表示v1点已标号；2.从点v1出发，找出与v1

相邻的点中距离最小的一个，设为r，将L1r=L11+d1r的值标注在r旁的小方框内，表明点r也已标号，将[v1，vr]加粗；步骤：设Lsi表示从s点到i

点的最短距离。例.求下图中从v1到v7的最短路。3.从已标号的点出发，找出与这些点相邻的所有未标号点p，若有L1p=min{L11+d1p,L1r+drp}，则对p点标号，并将L1p的值标注在p点旁的小方框内；4.重复第3步，直到

t

点得到标号为止。步骤：设Lsi表示从s点到i

点的最短距离。解：(1)

从v1点出发，对v1点标号，

将L11=0标注在旁的小方框内，

令v1∈V，其余点属于；(2)

同v1相邻的未标号点有v2、v3，L1p=min{0+d12

,0+d13

}=min{5,2}=2=L13(2)

同v1相邻的未标号点有v2、v3，对

v3

标号，将L13的值标注在v3旁的小方框内；将(v1,v3)加粗，并令V∪v3→V，(3)

同v1,v3相邻的未标号点有v2、v4、v6，L1p=min{L11+d12

,L13+d34,L13+d36

}=min{0+5,2+7,2+4}=5=L12(3)

同v1,v3相邻的未标号点有v2、v4、v6，对

v2

标号，将L12的值标注在v2旁的小方框内；将(v1,v2)加粗，并令V∪v2→V，。(4)

同v1,v2

,v3相邻的未标号点有v4、v5、v6。L1p=min{L12+d25

,L12+d24,

L13+d34

,L13+d36

}=min{5+7,5+2,2+7,2+4}=6=L16。(4)

同v1,v2

,v3相邻的未标号点有v4、v5、v6。对

v6

标号，将L16的值标注在v6旁的小方框内；将(v3,v6)加粗，并令V∪v6→V，(5)

同v1,v2

,v3,

v6相邻的未标号点

有v4、v5、v7，L1p=min{L12+d25

,L12+d24,L13+d34

,L16+d64,L16+d65,L16+d67

}=min{5+7,5+2,2+7,6+2,6+1,6+6}=7=L14=L15(5)

同v1,v2

,v3,

v6相邻的未标号点

有v4、v5、v7，对v4,v5同时标号，将L14=L15的值标注在v4,v5旁的小方框内；将(v2,v4),(v6,v5)加粗，并令V∪v4∪v5→V，(6)同v1,v2

,v3,v4,v5,

v6

相邻的未标号点只有v7，L1p=min{L15+d57

,L16+d67

}=min{7+3,6+6}=10=L17(6)同v1,v2

,v3,v4,v5,

v6

相邻的未标号点只有v7，对

v7

标号，将L17的值标注在v7旁的小方框内；将(v5,v7)加粗。图中粗线表明从点v1到网络中其它各点的最短路，各点旁的数字就是点v1到各点的最短距离。9858127374310练习(1)-用标号法求v1至各点的最短路。§6.1图的基本概念与模型§6.2树图和图的最小部分树§6.3最短路问题第六章图与网络分析§6.5网络的最大流主要内容：§6.4中国邮路问题§5.3最短路问题一、定义：最短路问题是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。二、最短路的求法：1.从某一点至其它各点之间最短距离的狄克斯屈拉(Dijksrta)算法——标号法2.求网络图中任意两点之间的最短距离的矩阵算法。距离只是权数的代称，在实际的网络图中，权数可以是时间、费用等。14226153072010151051042067302054练习(2)-用标号法求v1至各点的最短路。§6.3最短路问题§6.3.2矩阵算法57343286437例：如下图，用矩阵计算法求各点之间的最短距离。用于求任意两点间的最短距离。矩阵算法57343286437构造一个新矩阵D（1）,该矩阵给出了网络中任意两点之间直接到达和包括一个中间点时的最短距离。矩阵D（1）中每个元素的计算方式为：

构造一个新矩阵D（1）,该矩阵给出了网络中任意两点之间直接到达和包括一个中间点时的最短距离。矩阵D（1）中每个元素的计算方式为：一般有矩阵D（k）给出了网络中任意两点之间直接到达，经过一个、两个、…、到（2k-1）个中间点时比较得到的最短距离。矩阵D（k）中每个元素的计算方式为：设网络图有P个点，则一般计算到不超过D(k),k的值按下式计算：本例中：，故计算到D(3),若计算中出现D(m+1)=D(m)时，计算也可结束，矩阵D(m)中的各个元素值即为各点间的最短距离。矩阵算法求各点之间的最短路：57343286437例：假定上述问题中v1,v2,v2,v3,v5,v6,v7为7个村子，决定要联合办一所小学。已知各村的小学生人数分别为v1—30,v2—40,v3—25,v4—60，v5—50,v6—40,v7—40，则小学应建在哪个村子，使小学生上学走的总路程为最短。

57343286437解：由矩阵法得每个村到其他各村最短距离：已知各村的小学生人数：v1—30,v2—40,v3—25,v4—60，v5—50,v6—40,v7—40。v1v2V3v4v5v6v7v1015060270270180360v22000280160280280400v3501750175175100250v45402404200360180540v54503503503000150150v62403601601201200240v74804004003601202400合计1960167516701385132511301940小学建于各村时小学生走的总路程§6.3最短路问题——应用最短路问题是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。距离只是权数的代称，在实际的网络图中，权数可以是时间、费用等。选址问题管道铺设选线问题设备更新问题投资问题可以归结为最短路问题【例】某人购买一台摩托车，准备在今后4年内使用。他可在第一年初购买一台新车，连续使用4年，也可于任何一年末换一台新车。已知各年初的新车购置价如下表1。不同役龄车的年使用维护费及年末处理价如下表2。要求确定该人使用摩托车的最优更新策略，使4年内用于购买、更新及使用维护的总费用为最省。（单位：万元）第一年第二年第三年第四年年初的购置价2.52.62.83.1摩托车役龄0~1年1~2年2~3年3~4年年使用维护费0.30.50.81.2该役龄年末处理价2.01.61.31.1第一年第二年第三年第四年年初的购置价2.52.62.83.1摩托车役龄0~1年1~2年2~3年3~4年年使用维护费0.30.50.81.2该役龄年末处理价2.01.61.31.10.80.91.11.41.71.822.82.94.200.81.72.63.7【例】设某邮递员负责投递的街道如图所示，要求找出该邮递员的最短投递路线。44575412454214422§6.4中国邮路问题问题：如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。哥尼斯堡七桥问题【例】设某邮递员负责投递的街道如图所示，要求找出该邮递员的最短投递路线。44575412454214422§6.4中国邮路问题欧拉回路的定义是：连通图G中，若存在一条回路，经过每边一次且仅一次，称这条回路为欧拉回路。称具有欧拉回路的图为欧拉图。哥尼斯堡七桥问题欧拉的推理：凡是一笔画中出现的交点处，线一出一进总应该通过偶数条（偶点），只有作为起点和终点的两点才有可能通过奇数条（奇点）。连通图G是欧拉图的充分必要条件是图中的点全为偶点。（1）每条边上最多重复一次；（2）在图G的每个回路上，有重复边

的长度不超过回路总长的一半。445754124542144221、若图为欧拉图——寻找欧拉回路2、否则——将图中奇点两两相连，转化为欧拉图。求解：3、为使重复走的路线长度最短，需做到：（1）每条边上最多重复一次；（2）在图G的每个回路上，有重复边

的长度不超过回路总长的一半。求解：1、若图为欧拉图——寻找欧拉回路2、否则——将图中奇点两两相连，转化为欧拉图。445754124542144223、为使重复走的路线长度最短，需做到：§6.5网络的最大流§6.5网络的最大流1.有向图与容量网络有向图——

D(V,A)弧——(vi,vj)弧的容量——cij一.网络最大流的有关概念1.有向图与容量网络容量网络：定义了弧容量的网络。发点s收点t中间点网络的最大流：

发点到收点允许通过的最大流量。§6.5网络的最大流一.网络最大流的有关概念1.有向图与容量网络§6.5网络的最大流一.网络最大流的有关概念对有多个发点和多个收点的网络，可以另外虚设一个总发点和一个总收点，并将其分别与各发点、收点连起来，就可以转换为只含一个发点和一个收点的网络。2.流与可行流流——

fij

零流：

网络上所有的fij=0

§6.5网络的最大流可行流：容量网络上满足以下条件的一组流(1)容量限制条件(2)中间点平衡条件一.网络最大流的有关概念二.割和流量割(集）是指将容量网络中的发点和收点分割开，并使s→t

的流中断的一组弧的集合（截集）称弧的集合:(V,)={(v1,v3),(v2,v4)}是一个割。割的容量是组成它的集合中的各弧的容量之和。2024/6/13916/13/2024二.割和流量割割的容量SV1,V2,V3,V4,t(s,1)(s,2)15S,V1V2,V3,V4,t(s,2)(1,2)(1,3)21S,V2V1,V3,V4,t(s,1)(2,4)17S,V1,V2V3,V4,t(1,3)(2,4)18S,V1,V3V2,V4,t(s,2)(1,2)(3,2)(3,t)19S,V2,V4V1,V3,t(s,1)(4,3)(4,t)24S,V1,V2,V3V4,t(2,4)(3,t)14S,V1,V2,V4V3,t(1,3)(4,3)(4,t)25S,V1,V2,V3,V4t(3,t)(4,t)15二.割和流量割的意义“割”是研究网络流”瓶颈”的有效工具。最大流最小割定理f（V，）——割（V，）中所有V→方向弧的流量的总和，f（，V）——割（V，）中所有

→V方向弧的流量的总和最大流最小割定理从s→t

的流量：用v*(f)表示网络中从s→t

的最大流，则有根据割的概念，应小于等于网络中最小一个割的容量最大流最小割定理定理2：在网络中s→t

的最大流量等于

它的最小割集的容量，即前向弧与后向弧三.增广链对于网络上的发点和收点之间的一条链：所有指向为s→t的弧称为前向弧，记作µ+所有指向为t→s的弧称为后向弧，记作µ-

三.增广链如果在网络的发点和收点之间能找到一条链：链上所有前向弧：f<c；链上所有后向弧：f>0。增广链当增广链