运筹学课件及课后答案6图论

运筹帷幄之中决胜千里之外运筹学课件图与网络分析NetworkAnalysis第一节图的基本概念与模型定义：称G=(N,E)是一个图，如果有（1）N是非空有限集；（2）E是N中元素对所组成的集合。且，称N的元素为顶点，E的元素为边。记号：图G=(N,E)简记为G图G的顶点集简记为N(G)或N无向图的基本概念G的点集合：（例如：图（1）中的N=（1，2，3，4，5）是一个无向图的点的集合）G的边集合：E={eij}且eij={ni,nj}为右图无序二元组eij的端点：有eij={ni,nj}，则称ni和nj为eij的端点，且称eij

连接点ni和nj

环：两个端点重合为一点的边（例如右图中的e11）孤立点：不与任何边关联的点（例如右图中的n5）34512度V3V1V2V4V5各顶点度数为：d(V1)=4d(V2)=2d(V3)=1d(V4)=2d(V5)=？

无向图G有向图DV1V2V3V4各顶点度数为：d(V1)=d+(V1)+d-(V1)=3+0=3d(V2)=d+(V2)+d-(V2)=1+1=2度的有关定理定理1（握手定理）

设G=<V,E>为任意图(无向的或者有向的),V={v1,v2,…,vn}，边的条数|E|=m，则*推论

任何图(无向的或者有向的)中，次数为奇数的顶点个数是偶数。定理2

设D=<V,E>为有向图,V={v1,v2,…,vn}，边的条数|E|=m，则续（1）关联：一条边的端点称为这条边的关联邻接：与同一条边关联的端点称为是邻接的，同时如果两条边有一个公共端点，则称这两条边是邻接的有限图：点和边都是有限集合的图空图：没有任何边的图平凡图：只有一个点的图简单图：既没有圈也没有两条边连接同一对点的图完全图：每一对点之间均有一条边相连的图续（2）偶图(二分图):

若N(G)能分解为N1与N2合于N1N2=N(G),N1N2=,且Ni自身的顶点互不相邻（i=1,2）则称G是偶图；记为G=(N1,N2,E)完全偶图:

不在同一顶点子集的任二顶点都相邻的简单偶图；完全二分图

G=(S,T,E)：S中的每个点与T中的每个点都相连的简单二分图网络的基本概念有向图G：一个有序二员组(N,A)，记为G=(N,A)

G的弧集合：A={aij}且aij={ni,nj}为有序二元组，若aij={ni,nj}，则称aij从ni连向nj，

ni称为aij的尾，nj为

aij的头，ni称为nj的先辈，nj称为

ni的后继有向图G的基本图：对于G的每条弧用一条边代替后得到的无向图（有向）网络G：对（有向）图G的每条边（弧）都赋予一个实数，并称为边（弧）的权，则连同它边（弧）上的权称为（有向）网络。关联矩阵关联矩阵示例右图的关联矩阵是

右图的关联矩阵是

134521342邻接矩阵示例图（7）的邻接矩阵是

图（8）的邻接矩阵是

134521342子图定义：（通道、闭通道、开通道）图G的顶点与边的交错序列通道。起点与终点重合的通道称为闭通道。起点与终点不重合的通道称为开通道。无向图的路起点与终点不重合的迹称为开迹。没有重复顶点的开通道称为路。起点与终点重合的路称为圈。注：迹是通道；路是开迹；圈是闭迹，反之不一定定义：（迹、闭迹、开迹、路、圈）没有重复边的通道称为迹。起点与终点重合的迹称为闭迹。连通性点i和j点是连通的：G中存在一条（i，j）路G是连通的：G中任意两点都是连通的连通分支：G的极大连通子图命题:

设G有p个连通分支，则G的邻接矩阵可以表示成分块矩阵

第二节树图与图的最小部分（支撑）树最小树最小树及其性质求最小树的Kruskal算法(避圈法)

算法步骤

算例

破圈法算法

算法步骤

算例

定义：（树、生成树、最小生成树）定理1：设T是(n,m)非平凡图，则下列命题等价：（1）T是树；（2）T无圈，m=n-1；（3）T连通，m=n-1；（4）T无圈，任加一边有唯一圈；（5）T连通，任去一边不再连通；（6）T的任二顶点恰有一条路连通；无圈连通图称为树；图的生成子图若是树，则称为该图的生成树；树枝总和最小的生成树叫最小生成树注：由以上定理知：1。树是边数最少的连通图；2。连通图的极大无圈生成子图是生成树；3。连通图的极小连通生成子图是生成树。Kruskal算法步骤算例

计算的迭代过程例1：已知任两城市间修建直通高速公路的费用，如何修建连通n个城市的高速公路网使总修建费用最少？解：1。模拟图：以n个城市为顶点，以任意两城市u,v间修建高速公路的费用为边e=(u,v)的权，记为w(u,v)或w(e)，得赋权完全图G=(N,E)。2。问题等价于：求G的最小生成树，即边的权之和最小的生成树；3。求解：

思路：用避圈法，可选择权相对最小的边作为“加边”，如此便得到最小生成树。例2：用kruskal法求下图的最小生成树。破圈法：任取一个圈，从圈中去掉一条权最大的边，在余下的图中重复此步骤。练习：求下图的最小生成树:以上是一种算法，另外还可用“破圈法”:第三节

最短路问题

综上，从S到T的最短输油管线路有两条，如下图所示简化的图上操作方法下求到的最短路：1）从出发，向走。首先，从到的距离为0，给标号（0）。画第一个弧。（表明已标号，或已走出）从出发，只有两条路可走，其距离为2）①可能最短路为①给划成粗线。③划第二个弧。②给标号（4）。①②表明走出后走向的最短路目前看是，最优距离是4。现已考察完毕第二个圈内的路，或者说，已完成的标号。①②3）接着往下考察，有三条路可走：可选择的最短路为①给划成粗线。③划第3个弧。②给标号（6）。③①②4）接着往下考察，有四条路可走：可选择的最短路为①给划成粗线。③划第4个弧。②给标号（8）。①②③④5）接着往下考察，有四条路可走：可选择的最短路为①给划成粗线。③划第5个弧。②给标号（9）。①②③④⑤6）接着往下考察，有四条路可走：可选择的最短路为①给划成粗线。③划第6个弧。②给标号（13）。①②③④⑤⑥7）接着往下考察，有四条路可走：可选择的最短路为①同时给划成粗线。②分别给标号（14）。最后，从逆寻粗线到，得最短路：长度为15。

最短路问题的两个应用最短路问题在图论应用中处于很重要的地位，下面举两个实际应用的例子。设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要负购买费。试确定一个5年计划，使总支出最小若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表1所示.项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210表1解：把这个问题化为最短路问题。用点表示第i年初购进一台新设备，虚设一个点，表示第5年底。边表示第i年购进的设备一直使用到第j年初（即第j-1年底）。边上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买费、维修的全部费用（可由表8-2计算得到）。这样设备更新问题就变为：求从到的最短路问题.⑴①⑵给划成彩线。②⑶①②给划成彩线。⑷③给划成彩线。④⑸①②③④给划成彩线。⑤①②③④⑤⑹给划成彩线。计算结果：最短路①②③④⑤最短路路长为49。即：在第一年、第三年初各购买一台新设备为最优决策。这时5年的总费用为49。例(选址问题)已知某地区的交通网络如图所示，其中点代表居民小区，边代表公路，为小区间公路距离，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？解求中心的问题。解决方法：先求出到其它各点的最短路长如再求即为所求。比如求⑴⑵给划成彩线。⑶给划成彩线。给标号20。⑷给划成彩线。给标号30。⑸分别给划成彩线。分别给标号33。⑹给划成彩线。给标号63。其它计算结果见下表：

小区号030506393456093300203363153063502002050254050633320030183363936350300486393451525184801548603040336315063表2由于最小，所以医院应建在，此时离医院最远的小区距离为48。三.Floyd（佛洛伊德）算法这里介绍的Floyd算法（1962年）可直接求出网络中任意两点间的最短路。令网络中的权矩阵为其中当其他算法基本步骤为：⑴输入权矩阵例：求右图中任意两点间的最短路⑵计算其中例如：中不带角标的元素表示从到的距离（直接有边），带角标的元素表示借为中间点时的最短路长。中不带角标的元素表示从到的距离（直接有边），带角标的元素表示借为中间点时的最短路长。在放开的基础上，再放开注意到：在放开点的基础上，再放开考察最短路。注意到：说明所有点经过并没有缩短路程。只有一个新增元素表示任意两点间的最短路长及其路径。逐次逼近算法注：本算法可用于网络中有带负权的边，求某指定点到网络中任意点的最短路。算法思想：如果到的最短路总沿着该路从先到某一点，然后再沿边到达，则到达的这条路必然也是到达到达的最短路。若令表示从到达的最短路长，表示从到达的最短路长，则必有用迭代法解此方程：首先，令即是说，用到达

的直接距离做初始解，

并且，若他们之间无边，则记他们间的最短路为从第二步起用公式：求，当进行到第t步，若出现则停止，即为到各点的最短路长。算例求到达

的最短路第一次迭代第二次迭代第三次迭代达到最优，回代得最短路：例求v1到v8的最短路第一次迭代第二次迭代第三次迭代继续下去。。。。。。达到最优，回代后得最短路为：1．给标号（0）。画弧。①简化的表上求解方法①①给划成彩线。③划第二个弧。②给标号（-3）。②①①给划成彩线。③划第三个弧。②给标号（1）。②③①①给划成彩线。③划第四个弧。②给标号（2）。②③④①①给划成彩线。④划第五个弧。②给再次标号（0）。②③④⑤③去掉彩线。①①分别给划成彩线。③划第六个弧。②分别给标号（6）。②③④⑤⑥(4)由于权为－3，所以，将的距离改为3①①给划成彩线。③划第七个弧。②给标号（10）。②③④⑤⑥⑦①①给划成彩线。到达已经无负权，路程不可能再减少。②给标号（9）。②③④⑤⑥⑦①②③④⑤⑥⑦最短路径为：距离：10。第四节中国邮路问题例1：18世纪，在东普鲁士哥尼斯堡有座桥，如下图，一个散步者能否走遍七座桥，每座桥只走过一次，最后回到出发点？BCD定义：（Euler开（闭）迹、Euler迹、可一笔画）解：1。模拟图：以顶点表陆地，以边表桥，得4个顶点的模拟图。2。问题等价于：能否有一条闭迹包含模拟图的所有边，即：模拟图含有Euler闭迹吗？3。求解：假设图G含Euler闭迹。因为闭迹是连通的，所以图G也连通。又因为每个顶点既能到达也能离开，所以图G的每个顶点度都是偶数。即：图G含Euler闭迹的必要条件：连通且没有奇度顶点。所以，“七桥问题”是不可能的。若有一条开（闭）迹含图G的所有顶点和边，则称其为Euler开（闭）迹，Euler开（闭）迹统称Euler迹。可一笔画：从起点到终点一笔画完。定理1：图G含Euler闭迹的充要条件是G连通且没有奇顶点。定理2：图G可一笔画的充要条件是G连通且奇顶点数是0或2。邮路问题：若一个邮递员在下图所示的街道上投递邮件，问如何投递才使得他走遍每一条街道，再返回邮局，且总路程最短？11111111问题分析：据上面定理知，若街道图中没有奇点，则他就可以从邮局出发，走过每条街道一次，且仅一次，最后回到邮局，如此他所走的路程即是最短路程。而对于有奇点的图，必须在某些街道上重复走一次或多次。（假定N1为邮局）这样，路线可有多种，例：总权为12总权为11可见，按第一条路线，在边上各重复走了一次，而按第二条路线，在边上各重复走了一次。因此，我们想到，可在一个有奇点的图中，增加一些重复边，使得新图不含奇点，且要求重复边的总权最小。注释：增加重复边使图无奇点的过程称为可行方案。使总权最小的可行方案称为最小方案第一步（找初始可行方案）：找到图中的奇点，把奇点两两相连，（因为，在任何图中奇点个数必为偶数）。第二步（调整可行方案）：调整时遵循两个原则：（a）在最优方案中，图的每一条边上最多有一条重复边；（b）在最优方案中，图的每一个圈上重复边的总权不大于该圈总权的一半。（若把图中某个圈上的重复边去掉，而给原来没有重复边的的边上加上重复边，图中仍没有奇点）第三步（判断最优方案）：检查条件（a），（b）是否满足，若是，则为最优。得求解步骤：例：求解下面问题。255964343444解：奇点有：连接且连接得：255964343444因为圈的总权为24，但重复边的总权为14，大于该圈总权的一半，故需要调整，以上的重复边代替上的重复边，使重复边总长下降为17，255964343444同理，调整圈

后，得最优方案：255964343444注：此法称为奇偶点图上作业法，此法困难在于要检查所有圈，问题特复杂时应用它法。第五节网络最大流可行流的流量：3。饱和、非饱和弧，0流、非0流弧，前向、后向弧若则为饱和弧，若则为非饱和弧.若则为0流弧，若则为非0流弧.寻求一条s→t的路，作为参照物。这条路经过的网络图的弧中前向弧：凡是和此路方向相同的弧称为前向弧。反向弧：凡是和此路方向相反的弧称为反向弧。割集有：截量为4截量为5截量为4网络最大流算法的理论依据只有找不到增广链时，网络才能达到最大流这是因为：有增广链时，能找到一个若令得到了，一个流量更大的可行流最小割与最大流的关系最小割最大流定理割集有：截量为4截量为5截量为4算例求下图的最大流解：（1）先给标号（0，）；（2）从出发的弧（3）从到的弧（4）从出发的弧（5）从到的弧（6）从到的弧有了标号，也得到了一条增广链如图调整后得到下图继续标号如下：（1）给标号（0，）；（2）从出发的弧下面无法进行，所以达到最大流。此时的最大流量为所以为最小割。最大流问题的应用1.最大匹配问题⑴二部图（也叫二分图）图G=(V,E),若V=X∪Y且X∩Y=ф，使得E中每一条边的两个端点必有一个属于X，另一个属于Y，则称G为二部图。记G=（X，Y，E），或G=（X，E，Y）。匹配：对给定的二部图G=（X，Y，E），若有M包含于E，且M中任意两条边都没有公共端点，则称M为G的一个匹配（也称对集）。既满足：一个人最多做一件工作，每件工作最多由一人来做。即为工作集与工人集之间的一个匹配。最大匹配问题：Q表示G中所有的匹配集，即Q=｛M|M为G的匹配集｝|M|表示M的边数，若存在M0使对任意的M∈Q，有则称M0是G的最大匹配。注：G中最大匹配方案可能不唯一。饱和点：M中任意边的端点称为（关于M的）饱和点（即已经有匹配的顶点），G中其他顶点称为非饱和点。例：多端网络问题设有5位待业者，5项工作，他们各自能胜任工作的情况如图所示，要求设计一个就业方案，使尽量多的人能就业。其中表示工人。表示工作。二部图中最大匹配问题，可以转化为最大流问题求解。在二部图中增加两个新点分别作为发点，收点。并用有向边把它们与原二部图中顶点相连，令全部边上的容量均为1。当网络流达到最大时，如果上的流量为1，就让作工作，此即为最大匹配方案。第一次标号。调整第二次标号。再调整。第三次标号。调整。第四次标号。调整第五次标号。标号过程已无法再继续。流量为1的画彩线。工人分别作故最多安排四个人工作。应用2：货物运输问题例：现有5批货物，每批只需一条船装运，要由，所在地域运往，，地域。至于货物从，运向，，三点何处都一样，每批货物出发日期如表1，船航行所需天数如表2。船只空载和重载时航行时间相同。要求制定一个计划，在半个月内用最少的船只把5批货物运过去。地点510

/

/121，8地点232112表1（出发日期）表2（航行天数）解：设，分别表示每项运输任务的出发日期及完成日期（i=1，2，3，4，5）则由表1和表2知：任务路线①57②1013③1213④13⑤810任务路线①57②1013③1213④13⑤810要想用较少的船只在1～15天内完成任务，关键是自上一任务到达的时间加上返回的时间能否赶上下一个任务出发的时间。若能，则一只船就能完成两批货物的运输任务。以下试运行：任务路线①57②1013③1213④13⑤810①5号①7号8号回⑤10号地点232112表2（航行天数）⑤8号12号回③13号③14号回任务路线①57②1013③1213④13⑤810②10号④3号地点232112表2（航行天数）④1号②13号④5号回共两只船在13号以前就把5批货物全部运了出去。是否最优？一只船可行否？如何解决？作一个二部图，点集｛X｝和｛Y｝都表示这5项任务，两点间有连线的条件是第i件任务完成后可赶上作第j件任务。有连线即有匹配，连线越多（匹配数越大）一只船重复使用次数多，使用船只数就越少。最大的匹配就是用最少的船。任务路线①57②1013③1213④13⑤810任务路线①57②1013③1213④13⑤810地点232112表8-6（航行