运筹学基础及应用第五版-PPT.pptx

运筹学基础及应用第五版 图就是一种模型图就是一种模型,如公路铁路交通图如公路铁路交通图,水或煤气管网图水或煤气管网图,通讯联络图等。通讯联络图等。图就是对现实得抽象图就是对现实得抽象,用点与线得用点与线得连接组合表示。连接组合表示。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表示。表示。一、树图得概念一、树图得概念12大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流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,32,3步步,找到下一个点。找到下一个点。第二种做法求解过程第二种做法求解过程:方法二方法二:破圈法求解步骤破圈法求解步骤:1 1、从图从图 N N 中任取一回路中任取一回路,去掉这个回路中边权最大去掉这个回路中边权最大得边得边,得到原图得一个子图得到原图得一个子图 N1N1。2 2、从剩余得子图中任找一回路从剩余得子图中任找一回路,同样去掉回路中边同样去掉回路中边权最大得一条边权最大得一条边,得一新得子图得一新得子图;3 3、重复第重复第 2 2 步步,直到图中不再含有回路为止。直到图中不再含有回路为止。用破圈法求解上例用破圈法求解上例:1 1、任意找到一回路任意找到一回路,不妨取不妨取 DETD,DETD,去掉边权最大得去掉边权最大得边边 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