《图与网络分析》PPT课件.ppt

第6章图与网络分析,图的基本概念与模型树图和图的最小部分树最短路问题网络的最大流最小费用流,1.图的基本概念与模型,运筹学中研究的图用来表明一些研究对象和这些对象之间的相互关系。用点表示研究对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作G=V，E如果给图中的点和边赋以具体的含义和权数，如距离、费用等，称为网络图。,端点、关联边、相邻环、多重边、简单图次、奇点、偶点、孤立点链、圈、路、回路、连通图完全图、偶图子图、部分图,【例】有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如下表所示，打的是各运动员报名参加的比赛项目。问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。,A,C,B,E,D,F,2.树图和图的最小部分树,树图是无圈的连通图。性质1：任何树图中必存在次为1的点；性质2：具体n个顶点的树图的边数恰好为（n-1）条；性质3：任何具有n个点、（n-1）条边的连通图是树图。,2.树图和图的最小部分树,图的最小部分树如果G1是G2的部分树，又是树图，则称G1是G2的部分树（或支撑树）。树图的各条边称为树枝，一般图含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树。定理1：图中任一个点i，若j是与i相邻点中距离最近的，则边i，j一定必含在该图的最小部分树内。推论：把图的所有点分为V和V两个集合，则两集合之间连线的最短边一定包含在最小部分树内。,D,E,避圈法,【例】如下图所示，S、A、B、C、D、E、T代表村镇，它们间连线表明村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使上述村镇全部同上电，应如何架设使总的路线长度为最短。,B,S,A,C,T,2,5,4,1,7,5,2,1,3,5,7,4,D,E,破圈法,【例】如下图所示，S、A、B、C、D、E、T代表村镇，它们间连线表明村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使上述村镇全部同上电，应如何架设使总的路线长度为最短。,B,S,A,C,T,2,5,4,1,7,5,2,1,3,5,7,4,3.最短路问题,最短路问题一般来说就是从给定的网络图中找出任意两点之间距离最短的一条路。这里的距离只是权数的代称，在实际的网络图中，权数可以是时间、费用等。,求解最短路问题有两种算法：求从某一点至其它各点之间最短距离的狄克斯屈拉（Dijkstra）算法；求网络图上任意两点之间最短距离的矩阵算法；,狄克斯屈拉算法,5,7,2,2,1,2,6,6,4,3,7,0,L11=0L1p=minL11+d12,L11+d13=min0+5,0+2=2=L13L1p=minL11+d12,L13+d34,L13+d36=min0+5,2+7,2+4=5=L12L1p=minL12+d25,L12+d24,L13+d34,L13+d36=min5+7,5+2,2+7,2+4=6=L16,2,5,6,狄克斯屈拉算法,5,7,2,2,1,2,6,6,4,3,7,0,L1p=minL12+d25,L12+d24,L13+d34,L16+d64,L16+d65,L16+d67=min5+7,5+2,2+7,6+2,6+1,6+6=7=L14=L15L1p=minL15+d57,L16+d67=min7+3,6+6=10=L17,2,5,6,7,7,10,【练习】,4,6,5,7,1,5,5,2,4,1,6,8,0,4,5,5,9,10,16,矩阵算法,构造一个新矩阵D（1）,该矩阵给出了网络中任意两点之间直接到达和包括一个中间点时的最短距离。矩阵D（1）中每个元素的计算方式为：,一般有矩阵D（k）给出了网络中任意两点之间直接到达，经过一个、两个、到（2k-1）个中间点时比较得到的最短距离。矩阵D（k）中每个元素的计算方式为：,【例】某人购买一台摩托车，准备在今后4年内使用。他可在第一年初购买一台新车，连续使用4年，也可于任何一年末换一台新车。已知各年初的新车购置价如下表1。不同役龄车的年使用维护费及年末处理价如下表2。要求确定该人使用摩托车的最优更新策略，使4年内用于购买、更新及使用维护的总费用为最省。单位：万元。,0.8,0.9,1.1,1.4,1.7,1.8,2,2.8,2.9,4.2,0,0.8,1.7,2.6,3.7,一个邮递员从邮局出发，走遍他负责投递的每一条街道，然后再返回邮局，问应选择什么样的路线，使走的路程为最短。因为这个问题由中国数学工作者提出，故称为中国邮路问题。欧拉回路的定义是：连通图G中，若存在一条回路，经过每边一次且仅一次，称这条回路为欧拉回路。称具有欧拉回路的图为欧拉图。,【例】设某邮递员负责投递的街道如图所示，要求找出该邮递员的最短投递路线。,4,4,5,7,5,4,1,2,4,5,4,2,1,4,4,2,2,连通图G是欧拉图的充分必要条件是图中的点全为偶点。（1）每条边上最多重复一次；（2）在图G的每个回路上，有重复边的长度不超过回路总长的一半。,4,4,5,7,5,4,1,2,4,5,4,2,1,4,4,2,2,4.网络最大流,网络最大流的有关概念有向图与容量网络有向图上的连线是有规定指向的，称作弧；所谓容量网络是指对网络上的每条弧都给出一个最大的通过能力，称为该弧的容量，记为c(vi,vj)或简写cij；在容量网络中通常规定一个发点（记为s）和一个收点（记为t），网络中既非发点又非收点的其它点称为中间点；网络最大流是指网络中从发点到收点之间允许通过的最大流量。,4.网络最大流,流与可行流所谓流是指加在网络各条弧上的一组负载量，记作f(vi,vj)或简写为fij；若网络上所有的fij=0，这个流称为零流；在容量网络上满足以下条件的一组流称为可行流：容量限制条件，对所有弧有中间点平衡条件,4.网络最大流,割和流量割是指将容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。割的容量是组成它的集合中的各弧的容量之和。,9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),4.网络最大流,最大流最小割定理如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为st的弧（称为前向弧，记作+），存在f0，这样的链称为增广链。,4.网络最大流,最大流最小割定理当增广链存在时，找出再令定理：在网络中st的最大流量等于它的最小割集的容量。,4.网络最大流,Ford-Fulkerson标号算法首先给发点s标号。括弧中的第一个数字是使这个点得到标号的前一个点的代号；括弧中的第二个数字表示从上一个标号到这个标号点的流量的最大允许调整值。列出与已标号点相邻的所有未标号点：考虑从已标号点i出发的弧（i，j）：,j点不标号,j点标号,列出与已标号点相邻的所有未标号点：考虑所有指向已标号点i的弧（h，i）：如果某未标号点k有两个以上相邻的标号点，为减少迭代次数，可按I、II中所述规则分别计算出的值，并取其中最大的一个标记。重复第2步，可能出现两种结局：标号过程中断，t得不到标号，说明网络中不存在增广链，给定的流量即为最大流。记已标号点的集合为V,未标号点集合为V，（V，V）为网络的最小割；t点得到标号，反向追踪找出增广链；,h点不标号,h点标号,修改流量，设图中原有可行流为f，按一下方式获得新的可行流f：抹掉图中所有标号，重复第1到第4步，直至图中找不到任何增广链，即出现第3步的结局I为止，这时网络图中的流量即为最大流。,9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),7(6),5(3),9(5),6(0),10(9),最小割最大流：14,5(5),6(4),3(3),5(4),2(0),3(3),3(2),4(4),2(2),2(0),8(6),6(6),5(5),6(5),3(3),5(5),2(0),3(2),3(3),4(4),2(1),2(0),8(7),6(6),最小割最大流：13,【例】某河流中有4个岛屿，从两岸至各岛屿及各岛屿之间的桥梁编号如图所示，在一次敌对的军事行动中，问至少应炸断哪几座桥梁，才能完全切断两岸的交通联系？,A,B,C,D,E,F,2(1),2,1(1),2(1),1,1,1,1(1),3(1),A,B,C,D,E,F,2(1),2,1(1),2(1),1,1,1,1(1),3(1),A,B,C,D,E,F,2(2),2,1(1),2(2),1,1,1(1),1(1),3(2),最小割：(D,F),(D,E),(A,E),5.最小费用流,最小费用流问题对于容量网络，除考虑各条弧上的流量、容量外，还需考虑弧上通过单位流量时的费用（bij），保证最终给出的流量或最大流也是费用最少的。关键点：确定“最小费用增广链”。,【例】各弧旁数字为(cij,bij)，试求图中从st的最小费用最大流。,从原容量网络的零流f0开始；对原容量网络的可行流fk构造加权网络W(fk):对0fijcij的弧(i,j)，在加权网络的i点和j点之间分别绘制弧(i,j)和(j,i)，其权数分别为bij和-bij；对fij=cij的弧，在加权网络的i点和j点之间绘制弧(j,i)，其权数为-bij；对fij=0的弧，在加权网络的i点和j点之间绘制弧(i,j)，其权数为bij。确定最小费用增广链等价于求解加权网络st之间的最短路。找出增广链之后调整原容量网络的流量；重复2、3步骤，直到st之间找不出最短路为止，此时求得原容量网络的最小费用最大流。,5.最小费用流,8,7,5,9,9,2,4,0,7,8,10,14,8,7,5,9,9,4,-8,-2,-4,7,5,9,9,4,-8,-2,-4,-9,7,5,9,9,-8,-2,-4,-9,-7,-9,7,-5,9,-8,-2,-4,-9,-7,-9,