第七章 图与网络模型.ppt

《第七章 图与网络模型.ppt》由会员分享，可在线阅读，更多相关《第七章 图与网络模型.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE第七章第七章 图与网络模型图与网络模型1 1 图与网络的基本概念图与网络的基本概念2 2 最小生成树问题最小生成树问题3 3 最短路问题最短路问题4 最大流问题 1武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE1 图与网络的基本概念 图论中图是由点和边构成，可以反映一些对象之间图论中图是由点和边构成，可以反映一些对象之间的关系。的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，例如：在一个人群中，对相互认识这个关系我们可以用图来表示，下图就是一个表示这种关系的图。下图就是一个表示这种关系的

2、图。(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e52武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE1 图与网络的基本概念 当然图论不仅仅是要描述对象之间关系，还要当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图来表示，可见图人的相互认

3、识关系我们也可以用图来表示，可见图论中的图与几何图、工程图是不一样的。论中的图与几何图、工程图是不一样的。(v1)赵赵(v2)钱钱孙孙(v3)李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e53武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE1 图与网络的基本概念 一、一、图的三要素图的三要素 顶点无序的图为无向图。顶点无序的图为无向图。顶点有序的图为有向图。顶点有序的图为有向图。二、二、链链 一个由点和边的交替序列。一个由点和边的交替序列。三、三、回路回路(圈圈)若若链链的第一个点和最后一个点相同，则该路为回路的第一个点和最后一个点相同，则该路为回路(圈

4、圈)。4武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE1 图与网络的基本概念四、四、连通图连通图 对无向图对无向图G，若任何两个不同的点之间，至少存在一条链，则，若任何两个不同的点之间，至少存在一条链，则G为连通图。为连通图。五、五、子图及生成子图子图及生成子图1 1子图子图 设无向图设无向图G=G=（V V、E E），若），若2 2生成子图生成子图5武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE1 图与网络的基本概念六、六、赋权图赋权图对一个无向图对一个无向图G G的每一条边的每一条边(V Vi i,V,Vj j)，相应地有一个数，相应地有一个数C

5、 Cijij，则，则称图称图G G为赋权图，为赋权图，C Cijij称为边称为边(V Vi i,V,Vj j)上的权。上的权。七、七、网络网络在赋权的有向图在赋权的有向图D D中指定一点，称为发点，指定另一点称为收中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把点，其它点称为中间点，并把D D中的每一条弧的赋权数称为弧中的每一条弧的赋权数称为弧的容量，的容量，D D就称为网络。就称为网络。6武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE2 最小生成树问题一、树的概念树的概念树树树树 一个无圈的连通图称为树。一个无圈的连通图称为树。一个无圈的连通图称为树。一

6、个无圈的连通图称为树。树的性质：树的性质：树的性质：树的性质：1 1 1 1 在图中任意两点之间必有一条而且只有一条通路。在图中任意两点之间必有一条而且只有一条通路。在图中任意两点之间必有一条而且只有一条通路。在图中任意两点之间必有一条而且只有一条通路。2 2 2 2 在图中划去一条边，则图不连通。在图中划去一条边，则图不连通。在图中划去一条边，则图不连通。在图中划去一条边，则图不连通。3 3 3 3 在图中不相邻的两个顶点之间加一条边，可得一个在图中不相邻的两个顶点之间加一条边，可得一个在图中不相邻的两个顶点之间加一条边，可得一个在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。且仅

7、得一个圈。且仅得一个圈。且仅得一个圈。4 4 4 4 图中边数有图中边数有图中边数有图中边数有NeNeNeNe=V-1=V-1=V-1=V-1（V V V V为顶点数）。为顶点数）。为顶点数）。为顶点数）。生成树：生成树：若若T T是无向图是无向图G G的生成子图，且的生成子图，且T T又是树，称又是树，称T T为为G G的生成树。的生成树。7武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE2 2 最小生成树问题最小生成树问题最小生成树问题最小生成树问题 就是指在一个赋权的连通的就是指在一个赋权的连通的无向图无向图G G中找出一个生成树，并使得这个生成中找出一个生成树，并使

8、得这个生成树的所有边的权数之和为最小。树的所有边的权数之和为最小。8武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE2 2 最小生成树问题最小生成树问题二、求解最小生成树的破圈算法算法步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第2步。9武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE2 2 最小生成树问题最小生成树问题 例、某大学准备对其所属的例、某大学准备对其所属的7 7个学

9、院办公室计算机联网，个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中这个网络的可能联通的途径如下图，图中v v1 1,v,v7 7 表示表示7 7个学个学院办公室，请设计一个网络能联通院办公室，请设计一个网络能联通7 7个学院办公室，并使总的线个学院办公室，并使总的线路长度为最短路长度为最短(单位单位:百米百米)。v1331728541034v7v6v5v4v2v3 解：此问题实际上是求图的最小生成树，也即按照图的解：此问题实际上是求图的最小生成树，也即按照图的(f)(f)设计，可设计，可使此网络的总的线路长度为最短，为使此网络的总的线路长度为最短，为1919百米。百米。“管理运筹

10、学软件管理运筹学软件”有专门的子程序可以解决最小生成树问题。有专门的子程序可以解决最小生成树问题。10武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE2 2 最小生成树问题最小生成树问题 例 用破圈算法求图（a）中的一个最小生成树v1331728541034v7v6v5v4v2v13317285434v7v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)11武汉科技学院经济管理学院武汉科技学院经

11、济管理学院SHUFESHUFE作业作业:求下列各图的最小树求下列各图的最小树V9V1V2V3V6V5V8V7V4675834423916547V1V2V3V4V6V7V8V5451684634749512武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE3 最短路问题最短路问题最短路问题：对一个赋权的有向图D(或无向图)中指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧(或边)的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧(或边)的权数的总和被称为从Vs到Vt的最短距离。13武汉科技学院经济管理学院武汉科技学院经济管理学院SHU

12、FESHUFE3 最短路问题例1 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。V1（甲地）甲地）151762444 31065v2V7（乙地）乙地）v3v4v5v614武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE3 最短路问题15武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE3 最短路问题2 2算法算法从起点标号，标号有两个内容（从起点标号，标号有两个内容（a aj j,b,bj j），），a aj j表示从起表示从起点到该点的最小距离，点到该点的最小

13、距离，b bj j表示此最小距离链的紧前一个表示此最小距离链的紧前一个顶点的足标。起点的标号为（顶点的足标。起点的标号为（0 0、0 0）。）。从已标号的顶点出发，找出与这些已标号的顶点紧邻从已标号的顶点出发，找出与这些已标号的顶点紧邻的所有顶点的距离，并选最小值进行标号。直到所有顶的所有顶点的距离，并选最小值进行标号。直到所有顶点都标号完为止。点都标号完为止。16武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE3 最短路问题例例2.求求V至各点的最短路至各点的最短路VV2VVVVV106203015829583217武汉科技学院经济管理学院武汉科技学院经济管理学院SHUF

14、ESHUFE3 最短路问题例例3上例中上例中,求求V3至各点的最短路至各点的最短路例例4.求求V至各点的最短路至各点的最短路6VV2VVVVV10203015829583218武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE3 最短路问题例例5：V2 55V1V319武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE3 最短路问题二、逐次逼近法（适用某些二、逐次逼近法（适用某些C Cijij00）。）。解决指定点到任意点的最短路或两指定点间最短路。解决指定点到任意点的最短路或两指定点间最短路。算法：算法：1 1先赋予起点标号（先赋予起点标号（0 0、0 0

15、）及与起点邻近点的标号（）及与起点邻近点的标号（C Cijij、1 1），其它标号为（），其它标号为（，1 1）2 2检查各顶点标号是否得到最小值，否则，逐个调整。检查各顶点标号是否得到最小值，否则，逐个调整。20武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE 例例6.求求 V至各点的最短路至各点的最短路3 最短路问题V1V2V4V6V3V53-434-2-25221武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE3 最短路问题例例7.7.求求 V V至各点的最短路至各点的最短路V1V2V4V6V3V53-434-6-25222武汉科技学院经济管理学院

16、武汉科技学院经济管理学院SHUFESHUFE3 最短路问题 循环，路长单调下降而趋向循环，路长单调下降而趋向-，无结果。回路上的权值之和为正数无结果。回路上的权值之和为正数或零，可求得结果。或零，可求得结果。回路上的权值之和为负数时，此法回路上的权值之和为负数时，此法失效。失效。23武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFEV7V130302520V215V61518V43 最短路问题例例8 8 已知某地区的交通网络如下图所示已知某地区的交通网络如下图所示,其中点代表居其中点代表居民小区民小区,边表示公路边表示公路,问区中心医院应建在哪个小区问区中心医院应建在哪个小区

17、,可使可使离医院最远的小区居民就诊时所走的路程最近。离医院最远的小区居民就诊时所走的路程最近。V5v55v1v3v2v4Vv7602030203025181515V56020V324武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE3 最短路问题小区小区号号V1V2V3V4V5V6V7D(VI)V1030506393456093V2300203363153063V3502002050254050V4633320030183363V5936350300486393V6451525184801548V760304033631506325武汉科技学院经济管理学院武汉科技学院经济管理

18、学院SHUFESHUFE4 最大流问题最大流问题在交通运输、物资供应中，经常会遇到人流、车流、信在交通运输、物资供应中，经常会遇到人流、车流、信息流、物流、现金流。称息流、物流、现金流。称“网络流理论网络流理论”。二十世纪中二十世纪中二十世纪中二十世纪中叶以后，叶以后，叶以后，叶以后，FordFordFordFord和和和和FulkersonFulkersonFulkersonFulkerson建立了网络流理论。建立了网络流理论。建立了网络流理论。建立了网络流理论。最大流问题：给一个带收发点的网络，其每条弧的赋权最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的

19、前提下，求出从称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。发点到收点的最大流量。一、最大流的数学模型一、最大流的数学模型 26武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE4 最大流问题最大流问题例1 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？63522241263v1v2v7v4v3v6v527武

20、汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE4 最大流问题最大流问题我们可以为此例题建立线性规划数学模型：我们可以为此例题建立线性规划数学模型：设弧设弧(vi,vj)上流量为上流量为fij，网络上的总的流量为，网络上的总的流量为F，则有：，则有：28武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE4 最大流问题最大流问题 在这个线性规划模型中，其约束条件中的前在这个线性规划模型中，其约束条件中的前6 6个方程个方程表示了网络中的流量必须满足守恒条件，发点的流出量表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点

21、，它必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧示对每一条弧(v vi i,v,vj j)的流量的流量f fijij要满足流量的可行条件，要满足流量的可行条件，应小于等于弧应小于等于弧(v vi i,v,vj j)的容量的容量c cijij，并大于等于零，即，并大于等于零，即0 0f fijij c cijij。我们把满足守恒条件及流量可行条件的一组。我们把满足守恒条件及流量可行条件的一组网络流网络流 f fijij 称之为可行流，（即线性规划的可行解），称之为可行流，（即线性规划的

22、可行解），可行流中一组流量最大（也即发出点总流出量最大）的可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。称之为最大流（即线性规划的最优解）。29武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE4 最大流问题最大流问题 FordFordFulkersonFulkerson算法算法 二、概念及原理二、概念及原理1 1可行流可行流:满足约束条件式满足约束条件式ofofijijccijij的的f fijij称为一组可称为一组可行流。行流。可行流总是存在的，如取所有可行流总是存在的，如取所有f fijij=0=030武汉科技学院经济管理学院武汉科

23、技学院经济管理学院SHUFESHUFE4 最大流问题最大流问题2 2增值链增值链：设设f fijij是一组可行流，如果存在一条从是一组可行流，如果存在一条从V V1 1到到V Vn n的初等链，在这条链上所有的前向弧的初等链，在这条链上所有的前向弧f fijij 00，则称这条链是一条关于可行流，则称这条链是一条关于可行流f fijij的可扩充链。的可扩充链。在所有前向弧上计算在所有前向弧上计算在所有后向弧上计算在所有后向弧上计算调整量调整量31武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE4 最大流问题最大流问题新的可行流新的可行流 在在V V1 1VVn n间增加了一

24、个流量，直至找不到可扩充链间增加了一个流量，直至找不到可扩充链为止，就得到了最大流。为止，就得到了最大流。3 3原理原理:在发点和起点之间是否存在增值链。在发点和起点之间是否存在增值链。32武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE4 最大流问题最大流问题二、计算（标号法）二、计算（标号法）1 1给出第给出第1 1个可行流个可行流 令令2 2寻找增值链，若无，则取得最大流。否则，确定调整量，寻找增值链，若无，则取得最大流。否则，确定调整量，将将 调整为一个更大的可行流调整为一个更大的可行流 ，直到得到最大流，直到得到最大流为止为止 。例例2 2求下图的最大流求下图的最

25、大流1246532315284433武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE例例3.3.求下图的最大流求下图的最大流2576433255434321524 最大流问题最大流问题34武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE4 最大流问题最大流问题三、最小割最大流三、最小割最大流最小截集（最小截集（V V1 1、V V2 2）,V,V1 1为标号点集合，为标号点集合，V V2 2为未标号点集合。为未标号点集合。最小割容量，只计算各正向容量之和，这最小割容量，只计算各正向容量之和，这里是薄弱环节。里是薄弱环节。35武汉科技学院经济管理学院武汉科技学院经济管理学院SHUFESHUFE 作业：求下图的最大流作业：求下图的最大流 257643417841033342536