演示文稿运筹学基础及应用第五

演示文稿运筹学基础及应用第五版本文档共68页；当前第1页；编辑于星期三\12点10分运筹学基础及应用第五版胡运权ppt课件本文档共68页；当前第2页；编辑于星期三\12点10分

图是一种模型，如公路铁路交通图，水或煤气管网图，通讯联络图等。

图是对现实的抽象，用点和线的连接组合表示。§6.1图的基本概念和模型

图不同于几何图形。本文档共68页；当前第3页；编辑于星期三\12点10分一、基本概念1、图(graph)：由V,E构成的有序二元组，用以表示对某些现实对象及其联系的抽象，记作G=｛V,E｝。 其中V称为点集，记做V=｛v1,v2,···,vn｝

E称为边集，记做E=｛e1,e2,···,em｝点(vertex)：表示所研究的对象，用v表示；边(edge)：表示对象之间的联系，用e表示。网络图(赋权图)：点或边具有实际意义(权数)的图，记做N。零图：边集为空集的图。本文档共68页；当前第4页；编辑于星期三\12点10分v1v2v3v4v5e1e2e3e4e5e6e7e8特别的，若边e的两个端点重合，则称e为环。

若两个端点之间多于一条边，则称为多重边。2、图的阶：即图中的点数。例如右图为一个五阶图3、若图中边e=[vi,vj],则vi,vj称为e的端点，

e称为vi,vj的关联边。若vi与vj是一条边的两个端点，则称vi与vj相邻；若边ei与ej有公共的端点，则称ei与ej相邻。简单图：无环、无多重边的图。例如：e6=[v2,v3]本文档共68页；当前第5页；编辑于星期三\12点10分4、点v的次（或度，degree）与点v关联的边的条数，记为dG(v)或d(v)。v1v2v3v4e1e2e3e4e5e6e7v5

悬挂点次为1的点，如v5

悬挂边悬挂点的关联边，如e8e8

孤立点次为0的点

偶点次为偶数的点，如v2

奇点

次为奇数的点,如v5本文档共68页；当前第6页；编辑于星期三\12点10分5、链：图中保持关联关系的点和边的交替序列，其中点可重复，但边不能重复。路：点不能重复的链。圈：起点和终点重合的链。回路：起点和终点重合的路。连通图：任意两点之间至少存在一条链的图。完全图：任意两点之间都有边相连的简单图。

n阶完全图用Kn表示，边数=注意：完全图是连通图，但连通图不一定是完全图。本文档共68页；当前第7页；编辑于星期三\12点10分v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9如图(v1,e1,v2,e2,v3,e3,v4,e5,v5,e6,v3,e7,v6,e8,v7)是一条链,但不是路(v1,e1,v2,e2,v3,e7,v6,e8,v7)是一条路(v1,e1,v2,e2,v3,e3,v4,e4,v1)是一个回路(v4,e4,v1,e1,v2,e2,v3,e6,v5,e9,v7,e8,v6,e7,v3,e3,v4)是一个圈本图是一个连通图。本文档共68页；当前第8页；编辑于星期三\12点10分7、已知图G1=｛V1,E1｝,G2={V2,E2},若有V1V2，E1E2，则称G1是G2的一个子图；若V1=V2，E1E2且

E1≠E2

，则称G1是G2的一个部分图。6、偶图（二分图）：若图G的点集V可以分为两个互不相交的非空子集V1和V2，而且在同一个子集中的点均互不相邻，则图G称为偶图。完全偶图：V1中的每个点均和V2中的每个点相邻的偶图。若完全偶图中V1有m个点，V2有n个点，则该图共有mn条边。注意：部分图是子图，子图不一定是部分图。本文档共68页；当前第9页；编辑于星期三\12点10分二、应用例有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如表中所示，打“√”的项目是各运动员报名参加比赛的项目。问：六个项目的比赛顺序应如何安排，才能做到使每名运动员不连续地参加两项比赛？甲乙丙丁戊己项目人A B C D E F√√√√√√√√√√√√√√√√本文档共68页；当前第10页；编辑于星期三\12点10分解：构造一个六阶图如下：

点：表示运动项目。边：若两个项目之间有同一名运动员报名参加，则对应的两个点之间连一条边。ABCDEFA—C—B—F—E—D为满足题目要求，应该选择不相邻的点来安排比赛的顺序：或D—E—F—B—C—A本文档共68页；当前第11页；编辑于星期三\12点10分§6.2树图和图的最小部分树1、树（tree）：无圈的连通图称为树图，简称为树,用T(V,E)或T表示。一、树图的概念本文档共68页；当前第12页；编辑于星期三\12点10分2、树的性质（1）树中必有悬挂点。证明（反证法）：设树中任何点的次均不为1.

因为树无孤立点，所以树的点的次≥2.

不妨设树有n个点，记为v1,v2,…,vn

因为d(v1)≥2,不妨设v1与v2,v3相邻。又因为树没有圈，且d(v2)≥2,可设v2与v4相邻，…,依次下去，vn必然与前面的某个点相邻，图中有圈，矛盾！注意：树去掉悬挂点和悬挂边后余下的子图还是树。本文档共68页；当前第13页；编辑于星期三\12点10分（2）n阶树必有n-1条边。证明（归纳法）：当n=2时，显然；设n=k-1时结论成立。当n=k时，树至少有一个悬挂点。去掉该悬挂点和悬挂边，得到一个k-1阶的树，它有k-2条边，则原k阶树有k-1条边。即n=k时结论也成立。综上，n阶树有n-1条边。

本文档共68页；当前第14页；编辑于星期三\12点10分（3）任何有n个点、n-1条边的连通图是树。证明（反证法）：假设n个点，n-1条边的连通图中有圈，则在该圈中去掉一条边得到的子图仍连通，若子图仍有圈，则继续在相应圈中去掉一条边，…，直到得到无圈的连通图，即为树。但是该树有n个点，边数少于n-1,矛盾！

注意：①树是边数最多的无圈图。②树是边数最少的连通图。在树中不相邻的两个点之间添上一条边，则恰得到一个圈。

从树中去掉一条边，则余下的图不连通。本文档共68页；当前第15页；编辑于星期三\12点10分3、图的最小部分树（1）部分树：若G1是G2的一个部分图，且G1为树，则称G1是G2的一个部分树（或支撑树）。G2：ABCD547365576G1：ACBD注意：图G有部分树的必要条件是G是连通图。部分树不是唯一的。本文档共68页；当前第16页；编辑于星期三\12点10分（2）最小部分树（或最小支撑树）图G为网络图，若T是部分树中权和最小者，则称T是G的最小部分树(或称最小支撑树).本文档共68页；当前第17页；编辑于星期三\12点10分二、最小部分树的求法1、原理（1）图中与点v关联的最短边（即权最小的边）一定包含在最小部分树中。（2）将图中的点分成两个互不相交的非空子集，则两个子集之间连线的最短边一定包含在最小部分树中。本文档共68页；当前第18页；编辑于星期三\12点10分SABCDET252414317557即求图中的最小部分树例：要在下图所示的各个位置之间建立起通信网络，试确定使总距离最小的方案。本文档共68页；当前第19页；编辑于星期三\12点10分2、求法方法一：避圈法将图中所有的点分V为V两部分，

V——最小部分树中的点的集合

V——非最小部分树中的点的集合⑴任取一点vi，令vi∈V，其他点在V中 ⑵在V与V相连的边中取一条最短的边(vi,vj)，加粗(vi,vj)，令vj∈V ，并在V中去掉vj⑶重复⑵，至所有的点均在V之内。“取小边”本文档共68页；当前第20页；编辑于星期三\12点10分

避圈法另一种做法：1.在所有各边中找到边权最小的一条，将其作为最小部分树中的第一边；在剩余的边中，仍然找到边权最小的作为最小部分树的第二条边；2.在剩余的边中，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则在最小部分树中添加该边，如果形成了圈，则不再考虑该边；

3.重复进行第二步，直到找到第n-1条边为止。（因为有n个顶点的树中一定有n-1条边）本文档共68页；当前第21页；编辑于星期三\12点10分

例：分别用两种避圈法构造下图的最小部分树。

第一种解法：

1.在点集中任选一点，不妨取S，令V={S}

2.找到和S相邻的边中，权值最小的[S,A]。本文档共68页；当前第22页；编辑于星期三\12点10分

3.V={S,A}

4.重复第2，3步，找到下一个点。本文档共68页；当前第23页；编辑于星期三\12点10分

第二种做法求解过程：本文档共68页；当前第24页；编辑于星期三\12点10分

方法二：破圈法求解步骤：

1.从图N中任取一回路，去掉这个回路中边权最大的边，得到原图的一个子图N1。

2.从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；3.重复第2步，直到图中不再含有回路为止。

用破圈法求解上例：

1.任意找到一回路，不妨取DETD，去掉边权最大的边[T,E];本文档共68页；当前第25页；编辑于星期三\12点10分

2.从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；依次类推。本文档共68页；当前第26页；编辑于星期三\12点10分

破圈法的另一种解法：

1.从剩余图中找到边权最大的一条边，如果将其删除后图仍然是连通的，则删除此边，否则不再考虑此边；

2.重复上述步骤，直到剩余边数为n-1为止。

用此法求解上述问题：本文档共68页；当前第27页；编辑于星期三\12点10分

注意：

1.一个图的最小部分树不唯一，该题中用几种解法得到的结果都是相同的，是特殊情况；

2.不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。本文档共68页；当前第28页；编辑于星期三\12点10分§6.3最短路问题1、最短路问题从已知的网络图中找出两点之间距离最短（即权和最小）的路。2、相关记号（1）dij表示图中两个相邻点i和j之间的距离（即权）。易见dii=0

约定：当i和j不相邻时，dij=∞（2）Lij表示图中点i和j之间的最短距离（即最小权和）。易见Lii=0本文档共68页；当前第29页；编辑于星期三\12点10分

即在已知的网络图中，从给定点s出发，要到达目的地t。问：选择怎样的行走路线，可使总行程最短？3、狄克斯屈拉（Dijkstra）标号算法（1）适用范围用于求某两个点之间的最短距离。（2）原理最短路上任何片段是最短路。v1v2v3v4v5（3）思想按离出发点s的距离由近至远逐步标出最短距离Lsi以及最佳行进路线。本文档共68页；当前第30页；编辑于星期三\12点10分SABCDET252414317557例求图中S到T的最短路及最短距离。本文档共68页；当前第31页；编辑于星期三\12点10分（4）步骤在网络图中求s到t的最短路。第一步从s出发，将Lss=0标记在s旁边的方框内（表示点s已标记）；第二步找出与s相邻且距离最小的点，设为r，计算Lsr=Lss+dsr，并将结果标记在r旁边的方框内（表示点r已标记），同时标记边sr；第三步从已标记的点出发，找出这些点的所有未标记邻点，分别计算已标记点的方框数与其邻点的距离之和，利用“叠加最小”的原则确定下一个被标记点，设为p，并将最小的和标记在p旁边的方框内（表示点p已标记）,同时标记相应边；第四步重复第三步，直到t得到标记为止。本文档共68页；当前第32页；编辑于星期三\12点10分SABCDET25241431755702447891413594最短路：SABEDT最短距离：LST=13例求图中S到T的最短路及最短距离。本文档共68页；当前第33页；编辑于星期三\12点10分V1V2V3V4V5V6V752276742136例求图中v1到v7的最短路。05277610本文档共68页；当前第34页；编辑于星期三\12点10分例求图中任意两点之间的最短距离。V1V2V3V4V6V752276742136本文档共68页；当前第35页；编辑于星期三\12点10分4、矩阵算法

求任意两点间最短距离的方法⑴构造任意两点间直接到达的最短距离矩阵记做D(0)=dij(0)其中dij(0)=dij注意：D(0)是一个对称矩阵，且对角线上的元素全是0.D（0）=v1v2v3v4v5v6v7V1052∞∞∞∞V250∞27∞∞V32∞07∞4∞V4∞27062∞V5∞7∞6013V6∞∞42106v7∞∞∞∞360本文档共68页；当前第36页；编辑于星期三\12点10分其中dij（1）=min{

dir（0）+drj（0）}

irjdir（0）drj（0）r⑵构造任意两点间直接到达、或者最多经过1个中间点到达的最短距离矩阵D（1）=dij（1）即dij(1)为D(0)中第i行和第j列对应元素之和的最小值D（1）=v1v2v3v4v5v6v7V10527126∞V250727410V327065410V47260328V512753013V66442104v7∞10108340本文档共68页；当前第37页；编辑于星期三\12点10分其中dij（2）=min{

dir（1）+drj（1）}irjdir（1）drj（1）r⑶构造任意两点间最多可经过3个中间点到达的最短距离矩阵D（2）=dij（2）即dij(2)为D(1)中第i行和第j行对应元素之和的最小值D（2）=v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340本文档共68页；当前第38页；编辑于星期三\12点10分其中dij（3）=min{

dir（2）+drj（2）

}irjdir（2）drj（2）r⑷构造任意两点间最多可经过7个中间点到达的最短距离矩阵D（3）=dij（3）即dij(3)为D(2)中第i行和第j行对应元素之和的最小值D（3）=v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340=D（2）故D(2)中的元素就是图中相应两点之间的最短距离。本文档共68页；当前第39页；编辑于星期三\12点10分说明：一般的对于D（k）=dij（k），其中dij（k）=min{dir（k-1）+drj（k-1）}，(k=0,1,2,3,…)最多可经过2k-1个中间点收敛条件：当D（k+1）=D（k）时，计算结束；设网络图有p个点，即最多有p-2个中间点，则2k-1-1<p-22k-1

k-1<log2(p-1)k∴k<log2(p-1)+1，即计算到k=lg(p-1)/lg2+1时，计算结束。本文档共68页；当前第40页；编辑于星期三\12点10分注意狄克斯屈拉算法矩阵算法优点既可以求两点之间的最短距离，又可以确定最短路求任意两点之间的最短距离缺点求某两点之间的最短距离不能确定相应两点之间的最短路本文档共68页；当前第41页；编辑于星期三\12点10分

例：下图中v1—v7表示7个村子，需要联合建立一所小学，已知各村小学生的人数分别为v1—30人，v2—40人，v3—25人，v4—20人，v5—50人，v6—60人，v7—60人。问：学校应建在哪一个村子，可使学生总行程最少？V1V2V3V4V6V752276742136V5本文档共68页；当前第42页；编辑于星期三\12点10分v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340解：用矩阵算法得到任意两个村子之间的最短距离如下：

先将每一行的元素乘以该村子的学生人数，得到小学建在相应村子时，该村学生上学时单程所走的路程。再将每一列的元素累加，得到小学建在相应村子时，七个村子的学生上学时单程所走的总路程。本文档共68页；当前第43页；编辑于星期三\12点10分小学建在下列村子时，七个村子的学生上学时单程所走的路程v1v2v3v4v5v6v701506021021018030020002808020016032050175015012510020014040120060401203502502501500501503602402401206002406004804803601802400总路程17001335143010708357701330故小学应该建在v6村。本文档共68页；当前第44页；编辑于星期三\12点10分v1Sv2v3v4T§6.4网络的最大流v1Sv2v3v4T本文档共68页；当前第45页；编辑于星期三\12点10分一、基本概念和基本结论2、图的分类（1）无向图（简称图）记做G=(V,E)，V、E分别为点集和边集。（2）有向图记做D=(V,A），V、A分别为点集和弧集。注意：以下讨论的是有向图。3、弧的容量（简称容量）：弧(vi,vj)上可通过负载的最大能力。用c(vi,vj)或cij表示。1、图中两点vi与vj之间的连线有两种情况（1）边（edge）:未规定方向的连线，记做vi,vj,其中vi,vj称为端点（2）弧（arc）:规定方向的连线，记做(vi,vj)，其中vi称为起点，vj称为终点本文档共68页；当前第46页；编辑于星期三\12点10分4、容量网络（简称网络）：每条弧都有容量的网络。8v1Sv2v3v4T799265105例如：5、容量网络中点的分类发点（源点）：用S表示，“只出不入”收点（汇点）：用T表示，“只入不出”中间点：“有入有出”注意：任意容量网络总可以转换为只有一个发点和一个收点的情况。本文档共68页；当前第47页；编辑于星期三\12点10分6、流（flow）：加在网络中弧(vi,vj)上的一组负载量，用f(vi,vj)或fij表示。8(8)v1sv2v3v4t7(5)9(4)9(9)2(0)6(1)5(5)10(8)5(4)其中cij(fij)该流为可行流本文档共68页；当前第48页；编辑于星期三\12点10分10、网络的最大流：即使V(f)达到最大的可行流。8、零流：加在每条弧上的流量全为0。易见：零流一定是可行流。每个容量网络都有可行流。9、总流量：从发点s到收点t的流量,记做V(f)7、可行流(记做f)：能够在网络中通过的流，必须满足以下两个条件： ①容量限制条件：对所有弧，0

fijcij②中间点平衡条件：对任何一个中间点，流入量=流出量

本文档共68页；当前第49页；编辑于星期三\12点10分12、割的容量：割集中各弧的容量之和。13、最小割：所有割集中容量之和最小的一个割集。11、割集（简称割）：一组弧的集合，割断这些弧能使从s到t的流中断。定理：网络的最大流量等于它的最小割集的容量。8(8)v1sv2v3v4t7(5)9(4)9(9)2(0)6(1)5(5)10(8)5(4)例如：割集={(v1,v3),(v2,v4)}割的容量=9+9=18本文档共68页；当前第50页；编辑于星期三\12点10分14、前向弧（或正向弧）：在从发点s到收点t的一条链中，指向为s到t的弧称为前向弧，记做μ+。16、增广链：对于从s到t的一条链，如果在前向弧上满足流量小于容量，即fij<cij（即前向弧不饱和），后向弧上满足流量大于0，即fij>0（即后向弧不为0），则称这样的链为增广链。15、后向弧（或逆向弧）：在从发点s到收点t的一条链中，指向为t到s的弧称为后向弧，记做μ-。st6(4)5(3)4(4)8(7)μ+μ+μ+μ-这是一条增广链定理：当网络中不存在增广链时，网络达到最大流状态。本文档共68页；当前第51页；编辑于星期三\12点10分二、网络最大流的求法

标号算法(Ford-Fulkerson标号算法)1、基本思想：寻找增广链；若无增广链，则已经得到最大流和最小割，结束；若有增广链，则改善流量分布，再重复寻找，直到不存在增广链为止。2、点v的标号v(x,ε(v))

其中x是使v得到标号的已标号点，

ε(v)是从x到v的流量的最大可调值。标号算法下规定:前向弧是已标号点指向未标号点的弧,后向弧是未标号点指向已标号点的弧.本文档共68页；当前第52页；编辑于星期三\12点10分3、步骤：①对发点s标号：s（0，+∞）

从已标号点i出发，看与其相邻的未标号点j之间的弧， 对前向弧μ+若满足fij<cij，则对点j标号（i,ε(j)），其中ε(j)=min{ε(i)，cij-fij}对后向弧μ-若满足fji＞0，则对点j标号（i,ε(j)），其中ε(j)=min{ε(i)，fji}（注：若有多个可标号点，可任选。）若出现其他情况，则点j不标号。前向弧不饱和，要标号后向弧不为0，要标号本文档共68页；当前第53页；编辑于星期三\12点10分③当t得到标号时，从t开始沿已标号点用反向追踪法得到增广链，利用ε(t)调整流量：对前向弧μ+，新流量fij=fij+ε(t)

对后向弧μ-，新流量fij=fij-ε(t)

其余弧上的流量不变。④去掉所有标号，重复①。

若标号中断，即t没有得到标号，则该流为所求的网络最大流（此时最小割集为已标号点与未标号点之间的前向弧），结束；否则重复②，继续标号，直到收点t得到标号，转③。本文档共68页；当前第54页；编辑于星期三\12点10分8(8)v1sv2v3v4t7(5)9(4)9(9)2(0)6(1)5(5)10(8)(0,+∞)(s,2)(v2,2)(v1,2)(v3,1)(v4,1)5(4)cijfij例求网络的最大流。最大可调量为17(6)5(3)9(5)6(0)10(9)本文档共68页；当前第55页；编辑于星期三\12点10分8(8)v1sv2v3v4t7(6)9(5)9(9)2(0)6(0)5(5)10(9)5(3)(0,+∞)(s,1)(v2,1)(v1,1)最大流V（f）=14最小割集：｛(v3,t),(v2,v4)｝割集容量之和=14标号中断！本文档共68页；当前第56页；编辑于星期三\12点10分例某河流中有4座岛屿B、C、D、E与河岸A、F之间有数座桥相连，问至少需要炸毁几座桥，才可以中断两岸的交通联系？ABCDEF本文档共68页；当前第57页；编辑于星期三\12点10分ABCFED222131111解：建立6阶容量网络，弧上的容量表示