运筹学基础及应用第五版-胡运权.ppt

第6章 图与网络分析Graph and Network Analysis 图是一种模型，如公路铁路交通图，图是一种模型，如公路铁路交通图，水或煤气管网图，通讯联络图等。水或煤气管网图，通讯联络图等。图是对现实的抽象，用点和线的图是对现实的抽象，用点和线的连接组合表示。连接组合表示。6.1 图的基本概念和模型 图不同于几何图形。图不同于几何图形。一、基本概念一、基本概念1、图、图(graph)：由：由V,EV,E构成的构成的有序二元组，用以表示对有序二元组，用以表示对某些现实对象及其联系的抽象，记作某些现实对象及其联系的抽象，记作 G=V,E。其中其中V称为点集，记做称为点集，记做V=v1,v2,vn E称为边集，记做称为边集，记做E=e1,e2,em点点(vertex)：表示所研究的对象，用：表示所研究的对象，用v v表示；表示；边边(edge)：表示对象之间的联系，用：表示对象之间的联系，用e e表示。表示。网络图网络图(赋权图赋权图)：点或边具有实际意义点或边具有实际意义(权数权数)的图，的图，记做记做N。零图：零图：边集为空集的图。边集为空集的图。v1v2v3v4v5e1e2e3e4e5e6e7e8特别的，若边特别的，若边e e的两个端点重合，则称的两个端点重合，则称e e为环。为环。若两个端点之间多于一条边，则称为多重边若两个端点之间多于一条边，则称为多重边。2、图的阶：即图中的点数。、图的阶：即图中的点数。例如例如 右图为一个五阶图右图为一个五阶图3、若图中边、若图中边e=vi,vj,则则vi,vj称称为为e的端点，的端点，e称为称为vi,vj的关联边。的关联边。若若vi与与vj是一条边的两个端是一条边的两个端点，则称点，则称vi与与vj相邻；相邻；若边若边ei与与ej有公共的端点，有公共的端点，则称则称ei与与ej相邻。相邻。简单图：无环、无多重边的图。简单图：无环、无多重边的图。例如：例如：e e6 6=v=v2 2,v,v3 3 4 4、点、点v v的次（或度，的次（或度，degreedegree）与点与点v v关联的边的条数，记为关联的边的条数，记为d dG G(v)(v)或或d(v)d(v)。v1v2v3v4e1e2e3e4e5e6e7v5 悬挂点悬挂点 次为次为1 1的点，如的点，如 v v5 5 悬挂边悬挂边 悬挂点的关联边，如悬挂点的关联边，如 e e8 8e8 孤立点孤立点 次为次为0 0的点的点 偶点偶点 次为偶数的点，如次为偶数的点，如 v v2 2 奇点奇点 次为奇数的点次为奇数的点,如如 v v5 55 5、链：图中保持关联关系的点和边的交替序列，其、链：图中保持关联关系的点和边的交替序列，其中点可重复，但边不能重复。中点可重复，但边不能重复。路：点不能重复的链。路：点不能重复的链。圈：起点和终点重合的链。圈：起点和终点重合的链。回路：起点和终点重合的路。回路：起点和终点重合的路。连通图：任意两点之间至少存在一条链的图。连通图：任意两点之间至少存在一条链的图。完全图：任意两点之间都有边相连的简单图。完全图：任意两点之间都有边相连的简单图。n阶完全图用阶完全图用Kn表示，边数表示，边数=注意：完全图是连通图，但连通图不一定是完全图。注意：完全图是连通图，但连通图不一定是完全图。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)是一个圈是一个圈本图是一个连通图。本图是一个连通图。7 7、已知图、已知图G G1 1=V V1 1,E,E1 1,G,G2 2=V V2 2,E,E2 2,若有若有V V1 1 V V2 2，E E1 1 E E2 2，则称，则称G G1 1是是G G2 2的一个子图；的一个子图；若若V V1 1=V=V2 2，E E1 1 E E2 2且且 E E1 1E E2 2，则称，则称G G1 1是是G G2 2的一个部分图。的一个部分图。6 6、偶图（二分图）：若图、偶图（二分图）：若图G G的点集的点集V V可以分为两个互不可以分为两个互不相交的非空子集相交的非空子集V V1 1和和V V2 2，而且在同一个子集中的点均，而且在同一个子集中的点均互不相邻，则图互不相邻，则图G G称为偶图。称为偶图。完全偶图：完全偶图：V V1 1中的每个点均和中的每个点均和V V2 2中的每个点相邻的偶中的每个点相邻的偶图。图。若完全偶图中若完全偶图中V V1 1有有m m个点，个点，V V2 2有有n n个点，则该图共有个点，则该图共有mn条边。条边。注意：部分图是子图，子图不一定是部分图。注意：部分图是子图，子图不一定是部分图。二、应用例例 有甲、乙、丙、丁、戊、己六名运动员报名有甲、乙、丙、丁、戊、己六名运动员报名参加参加A A、B B、C C、D D、E E、F F六个项目的比赛。如表中所六个项目的比赛。如表中所示，打示，打“”“”的项目是各运动员报名参加比赛的项的项目是各运动员报名参加比赛的项目。问：六个项目的比赛顺序应如何安排，才能做目。问：六个项目的比赛顺序应如何安排，才能做到使每名运动员不连续地参加两项比赛？到使每名运动员不连续地参加两项比赛？甲甲 乙乙 丙丙 丁丁 戊戊 己己项目项目人人ABCDEF解：构造一个六阶图如下：解：构造一个六阶图如下：点：表示运动项目。点：表示运动项目。边：若两个项目之间有同一名运动员报名参加，边：若两个项目之间有同一名运动员报名参加，则对应的两个点之间连一条边。则对应的两个点之间连一条边。ABCDEFACBFEDACBFED为满足题目要求，应为满足题目要求，应该选择不相邻的点来该选择不相邻的点来安排比赛的顺序：安排比赛的顺序：或或D DEFBCAEFBCA6.2 树图和图的最小部分树1 1、树（、树（treetree）：无圈的连通图称为树图，简称为）：无圈的连通图称为树图，简称为树树,用用T(V,E)T(V,E)或或T T表示。表示。一、树图的概念一、树图的概念2 2、树的性质、树的性质（1 1）树中必有悬挂点。）树中必有悬挂点。证明证明（反证法）：（反证法）：设树中任何点的次均不为设树中任何点的次均不为1.1.因为树无孤立点，所以树的点的次因为树无孤立点，所以树的点的次2.2.不妨设树有不妨设树有n n个点，记为个点，记为v v1 1,v,v2 2,v,vn n 因为因为d(vd(v1 1)2,)2,不妨设不妨设v v1 1与与v v2 2,v,v3 3相邻。相邻。又因为树没有圈，且又因为树没有圈，且d(vd(v2 2)2,)2,可设可设v v2 2与与v v4 4相邻，相邻，,依次下去，依次下去，v vn n必然与前面的某个点相邻，图中有圈，矛盾！必然与前面的某个点相邻，图中有圈，矛盾！注意：树去掉悬挂点和悬挂边后余下的子图还是树。注意：树去掉悬挂点和悬挂边后余下的子图还是树。（2 2）n n阶树必有阶树必有n-1n-1条边。条边。证明证明（归纳法）：（归纳法）：当当n=2n=2时，显然；时，显然；设设n=k-1n=k-1时结论成立。时结论成立。当当n=kn=k时，树至少有一个悬挂点。时，树至少有一个悬挂点。去掉该悬挂点和悬挂边，得到一个去掉该悬挂点和悬挂边，得到一个k-1k-1阶的树，它有阶的树，它有k-2k-2条边，则原条边，则原k k阶树有阶树有k-1k-1条边。条边。即即n=kn=k时结论也成立。时结论也成立。综上，综上，n n阶树有阶树有n-1n-1条边。条边。（3 3）任何有）任何有n n个点、个点、n-1n-1条边的连通图是树。条边的连通图是树。证明证明（反证法）：（反证法）：假设假设n n个点，个点，n-1n-1条边的连通图中有圈，则在该圈中去掉一条边的连通图中有圈，则在该圈中去掉一条边得到的子图仍连通，若子图仍有圈，则继续在相应圈中去条边得到的子图仍连通，若子图仍有圈，则继续在相应圈中去掉一条边，掉一条边，直到得到无圈的连通图，即为树。但是该树有，直到得到无圈的连通图，即为树。但是该树有n n个点，边数少于个点，边数少于n-1,n-1,矛盾！矛盾！注意：注意：树是边数最多的无圈图。树是边数最多的无圈图。树是边数最少的连通图。树是边数最少的连通图。在树中不相邻的两个点之间添上一条边，则恰得到一个圈。在树中不相邻的两个点之间添上一条边，则恰得到一个圈。从树中去掉一条边，则余下的图不连通。从树中去掉一条边，则余下的图不连通。3、图的最小部分树（1 1）部分树：若）部分树：若G G1 1是是G G2 2的一个部分图，且的一个部分图，且G1G1为树，为树，则称则称G G1 1是是G G2 2的一个部分树（或支撑树）。的一个部分树（或支撑树）。G2：ABCD547365576G1：ACBD注意：注意：图图G有部分树的必要条件是有部分树的必要条件是G是连通图。是连通图。部分树不是唯一的。部分树不是唯一的。（2 2）最小部分树（或最小支撑树）最小部分树（或最小支撑树）图图G G为网络图，若为网络图，若T T是部分树中权和最小者，则是部分树中权和最小者，则称称T T是是G G的最小部分树的最小部分树(或称最小支撑树或称最小支撑树).).二、最小部分树的求法二、最小部分树的求法1 1、原理、原理（1 1）图中与点）图中与点v v关联的最短边（即权最小的边）一关联的最短边（即权最小的边）一定包含在最小部分树中。定包含在最小部分树中。（2 2）将图中的点分成两个互不相交的非空子集，则）将图中的点分成两个互不相交的非空子集，则两个子集之间连线的最短边一定包含在最小部分树两个子集之间连线的最短边一定包含在最小部分树中。中。SABCDET252414317557即求图中的最小部分树即求图中的最小部分树例：要在下图所示的各个位置之间建立起通信网络，例：要在下图所示的各个位置之间建立起通信网络，试确定使总距离最小的方案。试确定使总距离最小的方案。2 2、求法、求法方法一：方法一：避圈法避圈法 将图中所有的点分将图中所有的点分V V为为V V两部分，两部分，VV最小部分树中的点的集合最小部分树中的点的集合 VV非最小部分树中的点的集合非最小部分树中的点的集合 任取一点任取一点vi，令，令viV，其他点在，其他点在V中中 在在V与与V相连的边中取一条最短的边相连的边中取一条最短的边(vi,vj)，加粗加粗(vi,vj)，令，令vjV，并在，并在V中去掉中去掉vj 重复重复，至所有的点均在，至所有的点均在V之内。之内。“取小边取小边”避圈法另一种做法避圈法另一种做法：1.1.在所有各边中找到边权最小的一条，将其作在所有各边中找到边权最小的一条，将其作为最小部分树中的第一边；在剩余的边中，仍然找为最小部分树中的第一边；在剩余的边中，仍然找到边权最小的作为最小部分树的第二条边；到边权最小的作为最小部分树的第二条边；2.2.在剩余的边中，找到边权最小的边，查看其在剩余的边中，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则在最小部分是否与前面的边形成圈，如果没有，则在最小部分树中添加该边，如果形成了圈，则不再考虑该边；树中添加该边，如果形成了圈，则不再考虑该边；3.3.重复进行第二步，直到找到第重复进行第二步，直到找到第 n-1 n-1 条边为条边为止。（因为有止。（因为有 n n 个顶点的树中一定有个顶点的树中一定有 n-1 n-1 条边）条边）例：分别用两种避圈法构造下图的最小部分树。例：分别用两种避圈法构造下图的最小部分树。第一种解法：第一种解法：1.1.在点集中任选一点，不妨取在点集中任选一点，不妨取 S S，令令 V=SV=S 2.2.找到和找到和 S S 相邻的边中，权值最小的相邻的边中，权值最小的 S,A S,A。3.3.V=S,AV=S,A 4.4.重复第重复第2 2，3 3步，找到下一个点。步，找到下一个点。第二种做法求解过程：第二种做法求解过程：方法二：破圈法求解步骤：方法二：破圈法求解步骤：1.1.从图从图 N N 中任取一回路，去掉这个回路中边权最大中任取一回路，去掉这个回路中边权最大的边，得到原图的一个子图的边，得到原图的一个子图 N1N1。2.2.从剩余的子图中任找一回路，同样去掉回路中边从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；权最大的一条边，得一新的子图；3.3.重复第重复第 2 2 步，直到图中不再含有回路为止。步，直到图中不再含有回路为止。用破圈法求解上例：用破圈法求解上例：1.1.任意找到一回路，不妨取任意找到一回路，不妨取 DETDDETD，去掉边权最大的去掉边权最大的边边 T,E;T,E;2.2.从剩余的子图中任找一回路，同样去掉回路中边从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；依次类推。权最大的一条边，得一新的子图；依次类推。破圈法的另一种解法：破圈法的另一种解法：1.1.从剩余图中找到边权最大的一条边，如果将其删从剩余图中找到边权最大的一条边，如果将其删除后图仍然是连通的，则删除此边，否则不再考虑此边；除后图仍然是连通的，则删除此边，否则不再考虑此边；2.2.重复上述步骤，直到剩余边数为重复上述步骤，直到剩余边数为 n-1 n-1 为止。为止。用此法求解上述问题：用此法求解上述问题：注意：注意：1.1.一个图的最小部分树不唯一，该题中用几种解法一个图的最小部分树不唯一，该题中用几种解法得到的结果都是相同的，是特殊情况；得到的结果都是相同的，是特殊情况；2.2.不同解法得到的最小部分树所包含的边虽然可能不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。是相同的，即都达到了最小。6.3 最短路问题1 1、最短路问题、最短路问题 从已知的网络图中找出两点之间距离最短（即权和从已知的网络图中找出两点之间距离最短（即权和最小）的路。最小）的路。2 2、相关记号、相关记号（1 1）dij表示图中两个相邻点表示图中两个相邻点i i和和j j之间的距离（即权）。之间的距离（即权）。易见易见 dii=0=0 约定：当约定：当i i和和j j不相邻时，不相邻时，dij=（2 2）Lij表示图中点表示图中点i i和和j j之间的最短距离（即最小权和）。之间的最短距离（即最小权和）。易见易见 Lii=0 =0 即在已知的网络图中，从给定点即在已知的网络图中，从给定点s s出发，要到达目出发，要到达目的地的地t t。问：选择怎样的行走路线，可使总行程最短？。问：选择怎样的行走路线，可使总行程最短？3 3、狄克斯屈拉（、狄克斯屈拉（Dijkstra）标号算法）标号算法（1 1）适用范围）适用范围 用于求某两个点之间的最短距离。用于求某两个点之间的最短距离。（2 2）原理）原理 最短路上任何片段是最短路。最短路上任何片段是最短路。v1 v2 v3 v4v5（3 3）思想）思想 按离出发点按离出发点s的距离由近至远逐步标出最短距离的距离由近至远逐步标出最短距离Lsi以及最佳行进路线。以及最佳行进路线。SABCDET252414317557例例 求图中求图中S到到T的最短路及最短距离。的最短路及最短距离。（4 4）步骤）步骤 在网络图中求在网络图中求s到到t的最短路。的最短路。第一步第一步 从从s出发，将出发，将Lss=0标记在标记在s旁边的方框内旁边的方框内（表示点（表示点s已标记）；已标记）；第二步第二步 找出与找出与s相邻且距离最小的点，设为相邻且距离最小的点，设为r，计算，计算Lsr=Lss+dsr，并将结果标记在，并将结果标记在r旁边的方框内旁边的方框内（表示点（表示点r r已标记），同时标记边已标记），同时标记边srsr；第三步第三步 从已标记的点出发，找出这些点的所有未从已标记的点出发，找出这些点的所有未标记邻点，分别计算已标记点的方框数与其邻点的距标记邻点，分别计算已标记点的方框数与其邻点的距离之和，利用离之和，利用“叠加最小叠加最小”的原则确定下一个被标记的原则确定下一个被标记点，设为点，设为p p，并将最小的和标记在，并将最小的和标记在p p旁边的方框内（表旁边的方框内（表示点示点p p已标记）已标记）,同时标记相应边；同时标记相应边；第四步第四步 重复第三步，直到重复第三步，直到t t得到标记为止。得到标记为止。SABCDET25241431755702447891413594最短路：最短路：S AB E D T最短距离：最短距离：LST=13例例 求图中求图中S到到T的最短路及最短距离。的最短路及最短距离。V1V2V3V4V5V6V752276742136例例 求图中求图中v v1 1到到v v7 7的最短路。的最短路。05277610例例 求图中任意两点之间的最短距离。求图中任意两点之间的最短距离。V1V2V3V4V6V7522767421364、矩阵算法 求任意两点间最短距离的方法 构造任意两点间直接到达的最短距离矩阵构造任意两点间直接到达的最短距离矩阵 记做记做D D(0)(0)=dij(0)其中其中dij(0)=dij注意：注意：D D(0)(0)是一个对称矩阵，且对角线上的元素全是是一个对称矩阵，且对角线上的元素全是0.0.D（0）=v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7V V1 10 05 52 2 V V2 25 50 02 27 7 V V3 32 2 0 07 7 4 4V V4 4 2 27 70 06 62 2V V5 5 7 76 60 01 13 3V V6 6 4 42 21 10 06 6v v7 7 3 36 60 0其中其中 d dijij（1 1）=min=min d dirir（0 0）+d+drjrj（0 0）irjdir（0）drj（0）r 构造任意两点间直接到达、或者最多经过构造任意两点间直接到达、或者最多经过1 1个中间点到达的最短距离矩阵个中间点到达的最短距离矩阵D（1）=dij（1）即dij(1)为D(0)中第i行和第j列对应元素之和的最小值D（1）=v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7V V1 10 05 52 27 71212 6 6V V2 25 50 07 72 27 74 41010V V3 32 27 70 06 65 54 41010V V4 47 72 26 60 03 32 28 8V V5 512127 75 53 30 01 13 3V V6 66 64 44 42 21 10 04 4v v7 7101010108 83 34 40 0其中其中 d dijij（2 2）=min=min d dirir（1 1）+d+drjrj（1 1）irjdir（1）drj（1）r 构造任意两点间最多可经过构造任意两点间最多可经过3 3个中间点到达个中间点到达的最短距离矩阵的最短距离矩阵 D D（2 2）=d dijij（2 2）即dij(2)为D(1)中第i行和第j行对应元素之和的最小值D（2）=v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7V V1 10 05 52 27 77 76 61010V V2 25 50 07 72 25 54 48 8V V3 32 27 70 06 65 54 48 8V V4 47 72 26 60 03 32 26 6V V5 57 75 55 53 30 01 13 3V V6 66 64 44 42 21 10 04 4v v7 710108 88 86 63 34 40 0其中其中 d dijij（3 3）=min=min d dirir（2 2）+d+drjrj（2 2）irjdir（2）drj（2）r 构造任意两点间最多可经过构造任意两点间最多可经过7 7个中间点到达的最短个中间点到达的最短距离矩阵距离矩阵 D D（3 3）=d dijij（3 3）即dij(3)为D(2)中第i行和第j行对应元素之和的最小值D（3）=v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7V V1 10 05 52 27 77 76 61010V V2 25 50 07 72 25 54 48 8V V3 32 27 70 06 65 54 48 8V V4 47 72 26 60 03 32 26 6V V5 57 75 55 53 30 01 13 3V V6 66 64 44 42 21 10 04 4v v7 710108 88 86 63 34 40 0=D（2）故故D D(2)(2)中的元素就是中的元素就是图中相应两点之间图中相应两点之间的最短距离。的最短距离。说明：说明：一般的对于一般的对于D D（k k）=d dijij（k k），其中其中 d dijij（k k）=min =min d dirir（k-1k-1）+d+drjrj（k-1k-1），(k=0,1,2,3,)(k=0,1,2,3,)最多可经过最多可经过2 2k k-1-1个中间点个中间点收敛条件：收敛条件：当当 D D（k+1k+1）=D=D（k k）时，计算结束；时，计算结束；设网络图有设网络图有p p个点，即最多有个点，即最多有p-2p-2个中间点，个中间点，则则 2 2k-1k-1-1 p-2-1 p-2 2 2k k-1 -1 k-1logk-1log2 2(p-1)(p-1)k k klog klog2 2(p-1)+1(p-1)+1，即计算到即计算到 k=k=lg(p-1)/lg2+1lg(p-1)/lg2+1 时，计算结束。时，计算结束。注意狄克斯屈拉算法矩阵算法优点既可以求两点之间的最短既可以求两点之间的最短距离，又可以确定最短路距离，又可以确定最短路求任意两点之间的求任意两点之间的最短距离最短距离缺点求某两点之间的最短距离求某两点之间的最短距离不能确定相应两点不能确定相应两点之间的最短路之间的最短路 例：下图中例：下图中v1v7表示表示7个村子，需要联合建立一所小个村子，需要联合建立一所小学，已知各村小学生的人数分别为学，已知各村小学生的人数分别为v130人，人，v240人，人，v325人，人，v420人，人，v550人，人，v660人，人，v760人。人。问：学校应建在哪一个村子，可使学生总行程最少？问：学校应建在哪一个村子，可使学生总行程最少？V1V2V3V4V6V752276742136V5v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7V V1 10 05 52 27 77 76 61010V V2 25 50 07 72 25 54 48 8V V3 32 27 70 06 65 54 48 8V V4 47 72 26 60 03 32 26 6V V5 57 75 55 53 30 01 13 3V V6 66 64 44 42 21 10 04 4v v7 710108 88 86 63 34 40 0解：用矩阵算法得到任意两个村子之间的最短距离如下：解：用矩阵算法得到任意两个村子之间的最短距离如下：先将每一行的元素乘以该村子的学生人数，得到小学先将每一行的元素乘以该村子的学生人数，得到小学建在相应村子时，该村学生上学时单程所走的路程。建在相应村子时，该村学生上学时单程所走的路程。再将每一列的元素累加，得到小学建在相应村子时，再将每一列的元素累加，得到小学建在相应村子时，七个村子的学生上学时单程所走的总路程。七个村子的学生上学时单程所走的总路程。小学建在下列村子时，七个村子的学生上学时单程所走的路程小学建在下列村子时，七个村子的学生上学时单程所走的路程v1v2v3v4v5v6v701506021021018030020002808020016032050175015012510020014040120060401203502502501500501503602402401206002406004804803601802400总路程总路程17001335143010708357701330故小学应该建在故小学应该建在v v6 6村。村。v1Sv2v3v4T6.4 网络的最大流v1Sv2v3v4T一、基本概念和基本结论一、基本概念和基本结论2 2、图的分类、图的分类（1 1）无向图（简称图）记做）无向图（简称图）记做G=(V,E)G=(V,E)，V V、E E分别为点集分别为点集和边集。和边集。（2 2）有向图）有向图 记做记做D=(V,AD=(V,A），），V V、A A分别为点集和弧集。分别为点集和弧集。注意：以下讨论的是有向图。注意：以下讨论的是有向图。3 3、弧的容量（简称容量）：弧、弧的容量（简称容量）：弧(vi,vj)上可通过负载的上可通过负载的最大能力。用最大能力。用c c(vi,vj)或或c cijij表示。表示。1 1、图中两点、图中两点v vi i与与v vj j之间的连线有两种情况之间的连线有两种情况（1 1）边（）边（edge）:未规定方向的连线，记做未规定方向的连线，记做 v vi i,v,vj j ,其其中中vi,vj称为端点称为端点（2 2）弧（）弧（arc）:规定方向的连线，记做规定方向的连线，记做(v(vi i,v,vj j)，其中，其中v vi i称为起点，称为起点，v vj j称为终点称为终点4 4、容量网络（简称网络）：每条弧都有容量的网络。、容量网络（简称网络）：每条弧都有容量的网络。8v1Sv2v3v4T799265105例如：例如：5 5、容量网络中点的分类、容量网络中点的分类发点（源点）：用发点（源点）：用S S表示，表示，“只出不入只出不入”收点（汇点）：用收点（汇点）：用T T表示，表示，“只入不出只入不出”中间点：中间点：“有入有出有入有出”注意：任意容量网络总可以转换为只有一个发点和一个收点注意：任意容量网络总可以转换为只有一个发点和一个收点的情况。的情况。6 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)该流为可行流该流为可行流1010、网络的最大流：即使、网络的最大流：即使V(V(f)达到最大的可行流。达到最大的可行流。8 8、零流：加在每条弧上的流量全为零流：加在每条弧上的流量全为0 0。易见：零流一定是可行流。易见：零流一定是可行流。每个容量网络都有可行流。每个容量网络都有可行流。9 9、总流量：从发点总流量：从发点s s到收点到收点t t的流量的流量,记做记做V(f)7 7、可行流、可行流(记做记做f)：能够在网络中通过的流，必须满：能够在网络中通过的流，必须满足以下两个条件：足以下两个条件：容量限制条件：对所有弧，容量限制条件：对所有弧，0 0 fijij cijij中间点平衡条件：中间点平衡条件：对任何一个中间点，流入量对任何一个中间点，流入量=流出量流出量1212、割的容量：割集中各弧的容量之和。、割的容量：割集中各弧的容量之和。13、最小割：所有割集中容量之和最小的一个割集。、最小割：所有割集中容量之和最小的一个割集。1111、割集（简称割）：一组弧的集合，割断这些、割集（简称割）：一组弧的集合，割断这些弧能使从弧能使从s s到到t t的流中断。的流中断。定理：网络的最大流量等于它的最小割集的容量。定理：网络的最大流量等于它的最小割集的容量。8(8)v1sv2v3v4t7(5)9(4)9(9)2(0)6(1)5(5)10(8)5(4)例如：割集例如：割集=(v=(v1 1,v,v3 3),(v),(v2 2,v,v4 4)割的容量割的容量=9+9=18=9+9=1814、前向弧（或正向弧）：在从发点、前向弧（或正向弧）：在从发点s到收点到收点t的一条的一条链中，指向为链中，指向为s到到t的弧称为前向弧，记做的弧称为前向弧，记做+。16、增广链：对于从、增广链：对于从s到到t的一条链，如果在前向弧上满的一条链，如果在前向弧上满足流量小于容量，即足流量小于容量，即fij0（即后向弧不为（即后向弧不为0），则称这），则称这样的链为增广链。样的链为增广链。15、后向弧（或逆向弧）：在从发点、后向弧（或逆向弧）：在从发点s到收点到收点t的一条的一条链中，指向为链中，指向为t到到s的弧称为后向弧，记做的弧称为后向弧，记做-。st6(4)5(3)4(4)8(7)+-这是一条增广链这是一条增广链定理：当网络中不存在增广链时，网络达到最大流状态。定理：当网络中不存在增广链时，网络达到最大流状态。二、网络最大流的求法 标号算法(Ford-Fulkerson标号算法)1、基本思想：、基本思想：寻找增广链；寻找增广链；若无增广链，则已经得到最大流和最小割，结束；若无增广链，则已经得到最大流和最小割，结束；若有增广链，则改善流量分布，再重复寻找，直到若有增广链，则改善流量分布，再重复寻找，直到不存在增广链为止。不存在增广链为止。2、点、点v的标号的标号 v(x,(v)其中其中x是使是使v得到标号的已标号点，得到标号的已标号点，(v)是从是从x到到v的流量的最大可调值。的流量的最大可调值。标号算法下规定标号算法下规定:前向弧是已标号点指向未标号点的弧前向弧是已标号点指向未标号点的弧,后向弧是未标号点指向已标号点的弧后向弧是未标号点指向已标号点的弧.3、步骤：、步骤：对发点对发点s标号：标号：s（0，+）从已标号点从已标号点i出发，看与其相邻的未标号点出发，看与其相邻的未标号点j之间的弧，之间的弧，对前向弧对前向弧+若满足若满足 fijcij，则对点，则对点j标号（标号（i,(j)），），其中其中 (j)=min(i)，cij-fij对后向弧对后向弧-若满足若满足fji0，则对点，则对点j标号（标号（i,(j)），），其中其中 (j)=min(i)，fji（注：若有多个可标号点，可任选。）（注：若有多个可标号点，可任选。）若出现其他情况，则点若出现其他情况，则点j不标号。不标号。前向弧不饱和，要标号前向弧不饱和，要标号后向弧不为后向弧不为0 0，要标号，要标号当当t得到标号时，从得到标号时，从t开始沿已标号点用反开始沿已标号点用反向追踪法得到增广链，利用向追踪法得到增广链，利用(t)调整流量：调整流量：对前向弧对前向弧+，新流量，新流量f ij=fij+(t)对后向弧对后向弧-，新流量，新流量f ij=fij -(t)其余弧上的流量不变。其余弧上的流量不变。去掉所有标号，重复去掉所有标号，重复。若标号中断，即若标号中断，即t没有得到标号，则该流为所求没有得到标号，则该流为所求的网络最大流（此时最小割集为已标号点与未标号的网络最大流（此时最小割集为已标号点与未标号点之间的前向弧），结束；否则重复点之间的前向弧），结束；否则重复，继续标号，继续标号，直到收点直到收点t得到标号，转得到标号，转。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例例 求网络的最大流。求网络的最大流。最大可调量为最大可调量为1 17(6)5(3)9(5)6(0)10(9)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标号中断！标号中断！例例 某河流中有某河流中有4 4座岛屿座岛屿B B、C C、D D、E E与河岸与河岸A A、F F之之间有数座桥相连，问至少需要炸毁几座桥，才可以间有数座桥相连，问至少需要炸毁几座桥，才可以中断两岸的交通联系？中断两岸的交通联系？ABCDEFABCFED222131111解：建立解：建立6 6阶容量网络，阶容量网络，弧上的容量表示相应位置的桥数：弧上的容量表示相应位置的桥数：ABCFED2(1)2(0)2(1)1(0)3(1)1(1)1(1)1(1)1(1)ABCFED2(1)2(1)2(1)1(1)3(2)1(1)1(0)1(1)1(1)任取一个可行流：任取一个可行流：用标号算法找到最大流：用标号算法找到最大流：最大流最大流V(f)=3，最小割最小割=（A,E），（），（D,E），（），（D,F）故至少要炸毁故至少要炸毁3座桥。座桥。(0,+)(A,1)(A,1)(B,1)ABCDEF此课件下载可自行编辑修改，此课件供参考！此课件下载可自行编辑修改，此课件供参考！部分内容来源于网络，如有侵权请与我联系删除！部分内容来源于网络，如有侵权请与我联系删除！