运筹学基础及应用(第五版),(第六章图与网络分析).ppt

2020/6/11，1，运筹学，2020/6/11，2，1。图的基本概念和模型，2。树图和图的最小部分树，3。最短路径问题，4。网络的最大流量，5。最小成本流，第6章图形和网络分析，2020/6/11，3。当地居民热衷于这样一个问题：一个步行者怎么能走过这七座桥，而且每座桥只能走一次，最后回到原点。虽然有许多实验者，但没有一个成功。柯尼斯堡的七座桥问题，2020/6/11，4。为了找到答案，欧拉在1736年把陆地缩小到一个点，把桥当作连接点的边缘，把问题抽象成一个图形的笔画。也就是说，是否可以从某一点开始画一个图形而不重复一个笔画，最后回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图中的每一个顶点都与奇数条边相连，而且不可能用一个笔画出来。这是经典图论中的第一个著名问题。为了反映实际生产和生活中事物之间的关系，人们经常在纸上画各种点和线的示意图。例如，有六个队在踢足球。我们用v1v6点分别表示这六个队。它们之间的匹配也可以通过图表反映出来。众所周知，v1队打败了v2队，v2队打败了v3队，v3队打败了v5队，等等。这种胜利和失败的情况可以由下图所示的有向图反映出来。V3，V1，V2，V4，V6，V5，2020/6/11，6，6.1。图形的基本概念和模型。图由连接点的一些节点、顶点和边组成。记住G=V，E，其中V是顶点的集合，E是边的集合。为图形中的点和边指定特定的含义和权重。我们称这样的图为网络图(加权图)。首先，基本概念，2020/6/11，7。图中的点用V表示，边用E表示，每条边都可以用它所连接的点来表示。如图所示，有：e1=v1，v1，e2=v1，v2或e2=v2，v1，点与点之间的连线形成的图形反映了实际生产和生活中某些特定对象之间的特定关系。通常，研究对象由点表示，研究对象之间的具体关系由点与点之间的线表示。在正常情况下，点在图形中的相对位置以及点之间的线的优缺点对于反映研究对象之间的关系显然并不重要。因此，图论中的图本质上不同于几何图和工程图。如果边E可以表示为e=vi，vj，则所述vi和vj是边E的端点，同时所述边E是点vi和vj的关联边，如果点vi、vj与同一条边关联，则所述点vi和vj是相邻的；如果边ei和ej有一个公共端点，则边ei和ej被称为是相邻的；如果边E的两个端点是重的，则称该边为环，如果两点之间有一条以上的边，则称之为有多条边的图，没有环和多条边的图称为简单图。环，多条边，简单图，2020/6/11，9，度，奇点，偶点，孤立点，与某一点相关的边的数量，称为该点的度(或度，线性度)，被记录为d(v)。奇数阶的点称为奇点，偶数阶的点称为偶点，零阶的点称为孤立点。如图：奇点是v5，v3，偶点是v1，v2，v4，v6，孤立点是v6，2020/6/11，10，链，环，路径，环，连通图，交替序列=v0，E1，v1，E2，ek，vk中的一些点和边，如果每条边E1，E2，ek是不同的，并且任何vi，t-1，vit(2tk)是相邻的，被称为链。如果所有顶点v0，v1，链中的vk也是不同的，这样的链变成了一条路径，起点和终点重合的链叫做圆，起点和终点重合的路径叫做环。如果一个图中每对顶点之间至少有一条链，这样的图称为连通图，否则称为断开图。如果一个简单图中的任意两点都有连通的边，这样的图被称为一个有n个顶点的完全图，它的边数是有编号的。如果一个图的顶点可以分成两个不相交的非空集V1和V2，这样同一集中的任何两个顶点都不相邻，这样的图称为偶图(也称为二部图)。如果偶图的顶点集V1和V2之间的每对顶点都有一条连通边，这样的图称为完全偶图，完全偶图中的V1包含m个顶点，V2包含n个顶点，其边数为mn。2020/6/11，12，子图，部分图，图G1=V1，E1和G2=V2，E2，如果有和，G1是G2的子图；如果是这样，G1被认为是G2的一个局部图。注意：部分图也是子图，但是子图不一定是部分图。子图：部分图，2020/6/11，13，2。树形图和最小部分树、树形图(简称树，表示为T(V，E)是无圈连通图。(无圆，无多条边)，1。树木的自然，自然1。任何树上都必须有一个次1点。阶数为1的点称为悬挂点，与之相关的边称为悬挂边。财产2。有n个顶点的树正好有(n-1)条边。财产3。任何有n个点和(n-1)条边的连通图都是一棵树。只要在树上任意添加一条边，就会出现一个圆。树中任意两点之间只有一条路径。如果从树中删除任何边，它将不再连接。(树是最脆弱的连通图)，2020/6/11，14，2。图的最小部分树，如果G1是G2的部分图，也是树形图，那么G1就是G2的部分树(或支持树)；树形图的每条边都被称为一个分支(假设每条边都有一个权重)；具有最小总分支长度的部分树称为图的最小部分树(也称为最小支持树)。定理1。图中的任何点I，如果j是离I最近的点，那么边i，j必须包含在图的最小部分树中。推论。如果一个图的所有点都被分成V和两个集合，那么这两个集合之间的最短连接边必须包含在最小部分树中。2020/6/11，15，3。避圈法和破圈法。寻找最小偏树的方法主要有两种：避圈法和破圈法。避圈步骤：1。从图表中选择一个点vi，以便包含viV和图表中的其余点；2。从V和之间的连接线中找出最小的边。这条边必须包含在最小零件树中。你也可以将这条边设为vi，vj来加粗它，并将其标记为最小零件树中的边。设VvjV，-vj 3。重复步骤2和3，直到图中的所有点都包含在v，2020/6/11，16中，另一种避免圆的方法：1。在所有边中找到边权重最小的边，并将其作为最小零件树中的第一边；在剩余的边中，仍然找到边权最小的最小部分树的第二条边；2。在剩余的边中，找到边权重最小的边，并检查它是否与前一条边形成一个圆。如果没有，将边添加到树的最小部分。如果形成一个圆，则不考虑边缘。3.重复第二步，直到找到n-1边。(因为有n个顶点的树必须有n-1条边)，例如，2020/6/11，17:使用两种避免圆的方法来构造下图中最小的部分树。第一个解决方案：1。选择点集中的任何一点，你不妨取S，这样V=S，2。找到与S相邻的边，它有最小的权重S，A。2020/6/11，18，3.V=S，A，4。重复步骤2和3以找到下一点。2020/6/11，19，第二种方法求解过程：2020/6/11，20，破圈法求解步骤：1。从图N中选取任何一个环，去掉该环中边权最大的边，得到原图的子图N1。2.从任何剩余的子图中找到一个循环，并移除循环中边权重最大的边，以获得一个新的子图；3.重复步骤2，直到图中不再有循环。为了任意地找到主循环，我们不妨采用DETD并移除具有最大边缘权重的边缘T，E。2020/6/11，21，2。从剩余的子图中找出任何一个循环，并去掉循环中边权最大的边，得到一个新的子图；等等。2020/6/11，22，另一种解圆方法：1。从剩余的图中找出边权重最大的边，如果删除后图仍然连通，删除这条边，否则不再考虑这条边；2。重复上述步骤，直到剩余边数为n-1。本方法用于解决上述问题：2020/6/11，23，注：1。图的最小部分树不是唯一的，在这个问题中用几种方法得到的结果是相同的，这是一个特例；尽管由不同解获得的最小部分树中包含的边可能不同，但是每个最小部分树中所有边权重的总和必须相同，即它们都达到最小值。2020/6/11，24，3。最短线路问题，最短线路问题是从给定的网络图中找出任意两点之间的最短距离(重量和最小值)。一些整数规划和动态规划问题可以归结为寻找最短路径的问题。如选址、管道铺设、设备更新、投资等问题。寻找最短路径的方法：1。一个点与其他点之间最短距离的Dijksrta算法；2.求网络图中任意两点间最短距离的矩阵算法。2020/6/11，25，1。dijkstra算法，1。让Dij代表图中两个相邻点之间的距离，如果我和J不相邻，使Dij=，显然dii=0。Dijkstra算法假设：基本思想：如果v1v2v3v4是v1v4的最短路径，v1v2v3必须是v1v3的最短路径。V2v3v4必须是V2和v4之间的最短路径。让Lsi代表从S点到I点的最短距离。2020/6/11，26，Dijkstra算法步骤：1。对于起点S，因为Lss=0，所以在S旁边的小框中标记0，表示点S已被标记；2。从点S开始，在与点S相邻的点中找出距离最小的一个，将其设置为R，并在R旁边的小框中标记LSR=最小二乘距离的值，表示点R也已被标记；3。从标记点中，找到所有与这些点相邻的未标记点。如果最小有效位=最小值LSSD，最小有效位，标记点，并在点旁边的小方框中标记最小有效位值；重复步骤3，直到标记了T点。寻找从起点S到终点T的最短路径，例如，2020/6/11，27。在下图中找到从v1到v7的最短路径。(1)从点v1开始，在其旁边的小框中标记L11=0的点v1，以便v1V和其余点属于它；2020/6/11，28，L1r=min 0d12，0d13=min 5，2=2=L13，(2)v1附近的未标记点为v2，v3，2020/6/11，29，对于v3，在v3旁边的小框中标记L13的值；将(v1，v3)加粗，并使Vv3V，2020/6/11，30，l1p=min l11d12，l13d34，l13d36=min 05，27，24=5=L12，(3)与v1，v3相邻的未标记点是v2，v4，v6，2020/6/11，31，对于v2，在v2旁边的小框中标记L12；加厚(v1，v2)并使Vv2V，2020/6/11，32，l1p=min l12d25，l12d24，l13d34，l13d36=min 57，52，27，24=6=l16，(4)邻近V1、V2和V3的未标记点为v4、v5和v6、2020/6/11和33。对于v6标签，在v6旁边的小框中标记L16的值；Bold (v3，v6)并使Vv6V，2020/6/11，34，l1p=min l12d25，l12d24，l13d34，l16d64，l16d65，l16d67=min 57，52，27，62，61，66=7=l14=l15，(5)与v1，v2，v3相同，与v6相邻的未标记点为v4，v5，v7，2020/6对于v4、v5，值L14=L15标记在v4、v5旁边的小框中。(v2，v4)，(v6，v5)加厚，并且Vv4v5V，2020/6/11，36，L1P=min L15d57，L16D67=min 73，66=10=L17，(6)与v1，v2，v3，v4，v5，v6相邻的未标记点只有v7，2020/6/11，37。对于v7，在v7旁边的小框中标记L17的值；Bold (v5、v7)。图中粗线表示从点v1到网络中其他点的最短路径，每个点旁边的数字表示从点v1到每个点的最短距离。2020/6/11，38，2。矩阵算法寻找任意两点之间的最短距离，Dijkstra算法只能计算从一点到图中其他点的最短距离，如果要计算每个点之间的最短距离，就需要分别计算每个点，而矩阵算法可以同时寻找所有点之间的最短距离。用矩阵算法求上述网络图中各点之间的最短距离。让dij代表图中两个相邻点I和j之间的距离。如果I和j不相邻，则dij=，显然dii=0。建立距离矩阵：2020/6/11，39，2020/6/11，40。从上面的距离矩阵，我们可以看到从点I到点J的直接距离，但是从点I到点J的最短距离不一定是从点I到点J的直接距离与上述问题一样，从V1到V2的最短距离应为最小值D11D12，D12D22，D13D32，D14D42，D15D52，D16D62，D17D72，即最小值D1RD2。因此，可以构造一个新的矩阵D(1)，使得D(1)中的每个元素都是：dij(1)=mindir drj，那么矩阵D(1)给出了当直接到达和通过中间点时网络中任意两点之间的最短距离。2020/6/11，41，重构矩阵D(2)，dij(2)=mindir(1) drj(1)。等等来构造矩阵D(k)，dij(k)=mindir(k-1) drj(k-1)，并计算停止控制：p是图中的顶点数。2020/6/11，42，在这个例子中k=3，2020/6/11，43，上面D(2)中的元素给出了点之间的最短距离，但是它们没有给出获得最短距离所通过的特定中间点。如果你想知道中间点是什么，你需要在计算过程中记录它们。教材160页例5，2020/6/11，44，4。网络的最大流量，1。网络最大流量的概念。有向图和容量网络，具有指定方向的图的每条边称为有向图，有向图的边称为弧，表示为(vi，vj)，表示方向从点vi指向点vj，有向图是点和弧的集合，表示为D(V，A)。电弧的最大通过能力(vi，vj)称为电弧的能力，记录为c (vi，vj)，或简称为cij。定义弧容量的网络称为容量网络。2020/6/11，45，容量网络通常指定一个发送点(源点，表示为S)和一个接收点(汇点，表示为T)，网络中的其余点称为中间点。从发送点到接收点允许的最大流量称为最大流量。具有多个接收(发送)点的网络可以转换成只有一个接收(发送)点的网络。流