《运筹学-图与网络.ppt》由会员分享，可在线阅读，更多相关《运筹学-图与网络.ppt（58页珍藏版）》请在三一办公上搜索。
1、第五章图与网络分析,基本要求：了解图论的相关概念；掌握最短路问题及其求解方法；掌握最大流问题及其求解方法。掌握最小费用流问题及其求解方法。,1、1736年，瑞士数学家欧拉发表了一篇题为“依据几何位置的解题方法”的论文，有效地解决了哥尼斯堡七桥难题。,图论的发展,2、1847年，基尔霍夫将图论引进到了工程技术领域。,3、1936年匈牙利数学家康尼格写的“有限图与无限图的理论”。第一本图论的专著。,5、中国邮路问题,4、1857年英国的Cayley(凯莱)提出了树的概念。,哥尼斯堡七桥难题,哥尼斯堡七桥问题,A,B,C,D,例1：右图是我国北京、上海等十个城市之间的铁路交通图，反映了这十个城市间的
2、铁路分布情况。这里用点代表城市，用点和点之间的联线代表这两个城市之间的铁路线。,第一节图的基本概念,例2：有甲、乙、丙、丁、戊五个球队，它们之间比赛情况，也可以用图表示出来，已知甲队和其它队都比赛过一次，乙队和甲丙队比赛过，丙队和乙、丁队比赛过，丁队和丙、戊比赛过，戊队和甲、丁队比赛过。为了反映这个情况，可以用点v1,v2,v3,v4,v5分别代表这五个队，某两个队之间比赛过，就在这两个队所相应的点之间联一条线，这条线不过其它的点。如图,v1,v2,v3,v4,v5,第一节图的基本概念,第一节图的基本概念,图：图就是由一些点及一些点之间的联线（不带箭头或带箭头）所组成的。把两点之间的不带箭头的
3、联线称为边，带箭头的联线称为弧。,无向图：如果一个图G是由点及边所构成的，则称之为无向图(也简称为图)，记作G(V，E)，式中V，E分别是G的点集合和边集合。一条联结点vi，vj的边记为vi，vj(或 vj，vi)。,有向图：如果一个图D是由点及弧所构成的，则称为有向图，记为D(V，A)，式中V，A分别表示D的点集合和弧集合。一条方向是从vi，vj的弧记为(vi，vj)。,第一节图的基本概念,端点、关联边、相邻：若e=u,v，则称u,v是e的端点，也称u,v是相邻的。称e是点u、v的关联边。,环、多重边、简单图：若边若图G中，某个边的两个端点相同，则称e是环；若两点之间有多于一条的边，称这些边
4、为多重边。一个无环、无多重边的图称为简单图。,次、奇点、偶点、孤立点、悬挂点、悬挂边：以点v为端点的边的个数称为v的次，记为d(v)；端点次数为奇数的点称作奇点；次数为偶数的点称作偶点；次为零的点称为孤立点；次为1的点称为悬挂点，悬挂点的关联边称为悬挂边。,第一节图的基本概念,Vv1,v2,v3,v4,v5,v6，Ee1,e2,e3,e4,e5,e6,e7,e8其中e1=v1,v2e2=v1,v2e3=v2,v3e4=v3,v4e5=v1,v4e6=v1,v3e7=v4,v4e8=v3,v5,图一,第一节图的基本概念,图二,Vv1,v2,v6Aa1,a2,a9其中a1=v1,v2a2=v2,v
5、3a3=v1,v3a4=v4,v1 a5=v3,v4a6=v4,v3a7=v3,v5a8=v4,v5a9=v5,v6,第一节图的基本概念,链、圈、路、回路、连通图：图中有些点和边交替序列v0,e1,v1,e2,ek,vk,若其中各边e1,e2,ek互不相同，且任意vt-1和vt均相邻，称为链，其中v0称为链的起点，vk称为链的终点。如果链中所有顶点v0,v1,vk也不相同，这样的链称为路。对起点和终点上重合的链称作圈，起点与终点重合的路称作回路。若一个图的任意两点之间均至少有一条链，则称这个图为连通图，否则称作不连通图。,v1,v2,v3,v4,e1,e2,e6,e3,e4,e5,e7,v5,
6、v6,e8,权：给定一个图，对图中的每一条边(弧)vi,vj，相应地有一个数wij，则称这样的图为赋权图（网络）。wij称为边(弧)上的权。,第一节图的基本概念,完全图、偶图：一个简单图中若任意两点之间均有边相连，称这样的图为完全图。如果图的顶点能分成两个互不相交的非空集合V1和V2，使在同一集合中任意两个顶点均不相邻，称这样的图为偶图（也称二分图）。如果偶图的顶点集合V1、V2之间的每一对不同顶点都有一条边相连，称这样的图为完全偶图。,子图、部分图：图G1=V1,E1和图G2=V2,E2，如果有V1V2和E1E2，称G1是G2的一个子图。若有V1V2，E1E2，则称G1是G2的一个部分图。,
7、a,b,第一节图的基本概念,图的矩阵表示,第一节图的基本概念,v1,v2,v3,v4,v5,7,4,4,9,2,3,8,5,6,第一节图的基本概念,邻接矩阵：对于图G=(V，E)，|V|=n，构造一个矩阵A=(aij)n n，其中：,则称矩阵A为图G的邻接矩阵。,第一节图的基本概念,v1,v2,v3,v4,v5,例：有甲、乙、丙、丁、戊、己6名运动员报名参加A，B，C，D，E，F6个项目的比赛。下表中打*的是各运动员报名参加的比赛项目。问6个项目比赛顺序如何安排，做到每名运动员不连续参加两项比赛。,第一节图的基本概念,第二节树图和图的最小部分树,一、树的概念及性质,定义：连通且不含圈的无向图称
8、为树。树中次为1的点称为树叶，次大于1的点称为分枝点，树中的各条边称为树枝。应用举例,性质：1、任何树中必存在次为1的点。2、具有n个顶点的树的边数恰好为(n-1)条。3、任何具有n个点、(n-1)条边的连通图是树图。4、树中的任意两点间有唯一的链相连。5、树中任舍去一条边就不连通。,第二节树图和图的最小部分树,经济管理学院组织机构图,第二节树图和图的最小部分树,乒乓球单打比赛抽签图,运动员,第二节树图和图的最小部分树,二、图的部分树,部分树：若图G的部分图是一棵树，则称该树为G的部分树（支撑树）。或简称为图G的树。,最小部分树：连通图G=(V，E)，每条边上有非负权L(e)。一棵部分树所有树
9、枝上权的总和，称为这个部分树的权。具有最小权的部分树称为最小部分树(最小支撑树)，简称最小树。,定理：图中任一点i，若j是与i相邻点中距离最近的，则边i,j一定必含在该图的最小部分树内。,第二节树图和图的最小部分树,例：如图所示，S、A、B、C、D、E、T代表村镇，它们间连线表明各村镇间现在道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使上述村镇全部能上电，应如何架设使总的线路长度为最短。,S,A,C,B,E,D,T,2,2,5,4,1,4,3,5,1,7,5,7,第二节树图和图的最小部分树,求最小部分树的避圈法,4、重复2、3两步，一直到图中所有点均包含在V中为止。,第二
10、节树图和图的最小部分树,S,A,C,B,E,D,T,2,2,5,4,1,4,3,5,1,7,5,7,第二节树图和图的最小部分树,求最小部分树的破圈法,基本思想：从网络图N中任取一回路，去掉这个回路中权数最大的一条边，得一子网络图N1，在N1中再任取一回路，再去掉回路中权数最大的一条边，得N2。如此继续下去，一直到剩下的子图中不再含回路为止。该子图就是N的最小部分树。,S,A,C,B,E,D,T,2,2,5,4,1,4,3,5,1,7,5,7,第二节树图和图的最小部分树,第三节最短路问题,给定一个赋权有向图D=(V，A)，对每一个弧a=(vi,vj)，相应地有权w(a)=wij，又给定D中的两个
11、顶点vs，vt。设P是从vs到vt的一条路，定义路P的权是P中所有弧的权之和，记为w(p)。最短路问题就是要在所有从vs到vt的路中，求一条权最小的路，即求一条从vs到vt的路P0，使,一、什么是最短路问题,例：求下图中v1到v8的最短距离,第三节最短路问题,第三节最短路问题,基本思想：从vs出发，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从vs到该点的最短路的权（称为P标号）、或者是从vs到该点的最短路的权的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具有T标号的点改变为具P标号的点。从而使D中具有P标号的顶点数多一个，这样，至
12、少经过P-1步，就可以求出从vs到各点的最短路。,二、狄克斯拉（Dijkstra）算法,第三节最短路问题,(1)给vs以P标号，P(vs)=0,其余各点均给T标号，T(vj)=+。,(2)若vi点为刚得到P标号的点，考虑这样的点vj:(vi,vj)属于E，且vj为T标号。对vj的T标号进行如下的更改：T(vj)=minT(vj)，P(vi)+wij,(3)比较所有具有T标号的点，把最小者改为P标号，即：P(vi)=minT(vi)当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号则停止。否则用vi代vi转回（2）。,步骤：GO,T(v2)=min+，0+3=3，k(v2)=v1T(v
13、3)=min+，0+5=5，k(v3)=v1T(v4)=min+，0+6=6，k(v4)=v1,将具有最小T标号的v2点改为P标号：P(v2)=3,T(v3)=min5，3+1=4，k(v3)=v2T(v5)=min+，3+7=10，k(v5)=v2T(v6)=min+，3+4=7，k(v6)=v2,解：标p(v1)=0，其余点标T(vi)=+，(i=2,3,4,5,6,7,8),0,3,将具有最小T标号的v3点改为P标号：P(v3)=4,0,3,T(v4)=min6，4+1=5，k(v4)=v3T(v6)=min7，4+2=6，k(v6)=v3,将具有最小T标号的v4点改为P标号：P(v4)
14、=5,T(v6)=min6，5+3=6T(v7)=min+，5+5=10，k(v7)=v4,4,5,T(V3)=4T(V4)=6T(V5)=10T(V6)=7T(V7)=+T(V8)=+,0,3,4,5,将具有最小T标号的v6点改为P标号：P(v6)=6,T(v5)=min10，6+2=8，k(v5)=v6T(v7)=min10，6+1=7，k(v7)=v6T(v8)=min+，6+9=15，k(v8)=v6,6,将具有最小T标号的v7点改为P标号：P(v7)=7,T(v8)=min15，7+5=12，k(v8)=v7,7,T(V5)=10T(V6)=6T(V7)=10T(V8)=+,0,3,
15、4,5,6,7,将具有最小T标号的v5点改为P标号：P(v5)=8,8,T(v8)=min12，8+6=12,将具有最小T标号的v8点改为P标号：P(v8)=12,12,最短路径为v1v2v3v6v7v8；最短距离为12。,T(V5)=8T(V8)=12,第三节最短路问题,例：用狄式算法v1点到v7点的最短路,第三节最短路问题,例：求下图G中任意两点间的最短路。,第三节最短路问题,三、Floyd算法,适用：求网络网中任意两点间的最短路。,步骤：（1）输入权矩阵D(0)=D；（2）计算D(k)=(dij(k)nn(k=1,2,n)其中dij(k)=mindij(k-1),dik(k-1)+dkj
16、(k-1)（3）D(n)=(dij(n)nn中元素dij(n)就是vi到vj的最短路长。,第三节最短路问题,v1,v2,v3,v4,v5,v1,v2,v3,v4,v5,第三节最短路问题,213,214,412,413,第三节最短路问题,213,214,412,413,125,325,521,213,214,412,413,125,325,521,213,214,412,413,132,1325,4132,531,第三节最短路问题,213,214,325,413,第三节最短路问题,132,1325,4132,531,213,214,325,413,132,1325,213,214,325,413
17、2,413,531,第三节最短路问题,132,1325,4132,531,213,254,325,413,132,1325,213,214,325,4132,413,531,第三节网络最大流问题,一、问题的提出(什么是网络最大流问题),如右图所示是联结某产品产地vi和销地vj的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数字表示这和运输线的最大通过能力。产品经过交通网从v1输送到v6。现在要求制定一个运输方案使从v1运到v6的产品数量最多。,二、基本概念与基本定理(1)网络与流定义1：设有向连通图D(V，A)，D的每条弧(Vi,Vj)上有非负权Ci
18、j称为弧的容量，仅有一个入次为0的点Vs称为发点(源)，一个出次为0的点称为收点(汇)，其余点为中间点，这样的网络D称为容量网络，常记做D=(V，A，C)。流量：所谓网络上的流，是指定义在弧集合A上的一个函数f=f(vi,vj)，并称f(vi,vj)为弧(vi,vj)上的流量。(有时也简记作fij),第三节网络最大流问题,第三节网络最大流问题,定义2：满足下述条件的流f称为可行流：a.容量限制条件：对每一弧(vi,vj)A有0fijcijb.平衡条件：对于中间点，流出量=流入量，即对每个Vi(is,t)有对于收、发点vt，vs，有从vs点发出的总流量等于vt点输入的总流量。即,最大流：最大流问
19、题就是求一个可行流fij，使流量W达到最大。,(2)可行流与最大流,第三节网络最大流问题,三、最大流最小割定理,定理：在网络中的最大流等于它的最小割集的容量。,第三节网络最大流问题,增广链若给一个可行流f=fij，我们把网络中使fij=cij的弧称为饱和弧，使fij0的弧称为非零流弧。若u是网络中联结发点vs和收点vt的一条链。我们定义链的方向是从vs到vt，则链上的弧被分为两类：一类是弧的方向与链的方向一致，叫作前向弧。前向弧的全体记为u+。另一类弧与链的方向相反，称为后向弧。后向弧的全体记为u-。定义3：设f是一个可行流，u是从vs到vt的一条链，若u满足下述条件，称之为(关于可行流f的)
20、一条增广链。在弧(vi,vj)u+上，0fijcij，即u+中每一弧是非饱和链。在弧(vi,vj)u-上，0fijcij，即u-中每一弧是非零流链。,(3,3),(2,1),(5,1),(5,3),(1,1),(4,3),(2,2),(1,1),(3,0),vs,v1,v2,v3,v4,vt,定理1：可行流f*是最大流，当且仅当不存在关于f*的增广链。,第三节网络最大流问题,四、求最大流的标号法在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点。每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的
21、。,第三节网络最大流问题,(3,3),(2,1),(5,1),(5,3),(1,1),(4,3),(2,2),(1,1),(3,0),vs,v1,v2,v3,v4,vt,例：用标号法求下图所示网络的最大流。弧旁的数是（cij,fij）,第三节网络最大流问题,（1）标号过程标号过程开始，先给vs标上(0，+)，这时vs是标号而未检查的点，其余都是未标号点。一般地，取一个标号而未检查的点vi，对一切未标号点vj：GOa.若在弧(vi，vj)上，fij0，则给vj标号(-vi,l(vj)，这里l(vj)=minl(vi),fij。这时点vj成为标号而未检查的点。于是vi成为标号而已检查过的点。重复上
22、述步骤，一旦vt被标上号，表明得到一条从vs到vt的增广链u，转入调整过程。若所有标号都是已检查过，而标号过程进行不下去时，由算法结束，这时的可行流就是最大流,第三节网络最大流问题,(2)调整过程GO首先按vt及其它点的第一个标号，利用“反向追踪”的办法，找出增广链u。令调整量是l(vt)，即vt的第二个标号。,去掉所有的标号，对新的可行流f=fij，重新进入标号过程。,(3,3),(2,1),(5,1),(5,3),(1,1),(4,3),(2,2),(1,1),(3,0),vs,v1,v2,v3,v4,vt,(0,+),解：标号过程：(1)首先给vs标上(0,+)(2)检查vs，在弧(vs
23、,v2)上，fs2=cs2=3，不满足标号条件。弧(vs,v1)上，fs1=1，cs1=5，fs1cs1，则v1的标号为(vs,l(v1)其中l(v1)=minl(vs),(cs1-fs1)=+,5-1=4(3)检查v1,(vs,4),(-v1,1),(4)检查v2(5)在v3，v4中任选一个进行检查调整过程：按点的第一标号找到一条增广链。即：vtv3v2v1vs调整量=1,(3,3),(2,1),(5,1),(5,3),(1,1),(4,3),(2,2),(1,1),(3,0),vs,v1,v2,v3,v4,vt,(0,+),(vs,4),(-v1,1),(v2,1),(-v2,1),(v3
24、,1),(5,2),(1,0),(1,0),(2,2),(vs,3),标号进行不下去,当前可行流是最大流。,最大流W=5。,第三节网络最大流问题,练习：用标号法求下图所示网络的最大流。Vs、Vt分别为发点和收点，弧旁数字为(cij,fij)。（哈工程2004年考研真题）,第三节网络最大流问题,s1,s2,v1,v2,t1,t2,3,7,2,2,4,4,3,7,7,6,练习：如下图所示，发点s1，s2分别可供应10和15个单位，收点t1，t2可以接收10和25个单位，求最大流，弧旁数字为cij。,s,t,10,15,10,25,(10,0),第四节应用举例,例某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费试制定一个年更新计划，使总支出最少若已知设备在各年的购买费，及不同机器役龄时的残值与维修费如下表所示,表,第四节应用举例,例设有位待业者，项工作，他们各自能胜任工作情况如图所示，要求，设计一个就业方案，使尽量多的人能就业,欧拉（Leonhard Euler，17071783）：瑞士数学家、力学家、天文学家、物理学家，变分法的奠基人，复变函数论的先驱者，理论流体力学的创始人。欧拉的专著和论文多达800多种。,欧拉简介,
