图论方法.ppt

引言 图论(Graph Theory)是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉，它有200多年历史，大体可划分为三个阶段：第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题围游戏而产生，最有代表性的工作是所谓的Euler七桥问题，即一笔画问题。第二阶段是从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如Hamilton问题，地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如Cayley把树应用于化学领域，Kirchhoff用树去研究电网络等.第三阶段是二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。BACDl哥尼斯堡七桥问题哥尼斯堡七桥问题(Knigsberg Bridge Problem)lLeonhard Euler(1707-1783)在在1736年发表第一篇图论方面年发表第一篇图论方面的论文，奠基了图论中的一些基本定理的论文，奠基了图论中的一些基本定理.l很多问题都可以用点和线来表示，一般点表示实体，线表示很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联实体间的关联例例6.16.1：哥尼斯堡七桥问题：哥尼斯堡七桥问题1 1 图与网络的基本概念图与网络的基本概念l一般研究无向图l树图：倒置的树，根(root)在上，树叶(leaf)在下l多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图 2 最小支撑树最小支撑树(生成树生成树)一一 树的定义及其性质树的定义及其性质l无圈连通图称为树无圈连通图称为树(treetree)，记为记为T T 树的性质：树的性质：l任何树必存在次数为任何树必存在次数为 1 1 的点的点l具有具有 n n 个节点的树个节点的树 T T 的边恰好为的边恰好为 n n 1 1 条，反之，任何有条，反之，任何有n n 个节点，个节点，n n 1 1 条边的连通图必是一棵树条边的连通图必是一棵树图的生成树图的生成树:若图若图G G的一个支撑图的一个支撑图T T是一棵树是一棵树,则称则称T T是是G G的一棵的一棵生成树生成树(spanning treespanning tree).).在赋权图在赋权图G G中，一棵生成树所有边上权的和，称为生成树的权。中，一棵生成树所有边上权的和，称为生成树的权。具有最小权的生成树，称为具有最小权的生成树，称为最小树最小树（或最优树）（或最优树）,求最小树有求最小树有破圈破圈法法和和避圈法避圈法.定理 图 G有生成树的充分必要条件为图是连通图。定义（最优树）在赋权图G中，一棵生成树所有树柱上权的和，称为生成树的权。具有最小权的生成树，称为最优树（或最小树）。求最小树的方法有破圈法和避圈法。3 最小枝杈树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636例例10-7破圈法破圈法v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323总造价总造价=1+4+9+3+17+23=57v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636避圈法避圈法v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636总造价总造价=1+4+9+3+17+23=574：最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型，如设备更新、管道的铺设、线路的安排、厂区的布局等。最短路问题的一般提法是：设 为连通图，图中各边 有权 (表示 ，之间没有边）,为图中任意两点，求一条道路 ，使它是从 到 的所有路中总权最小的路。即：最小。最短路算法中1959年由 （狄克斯特洛）提出的算法被公认为是目前最好的方法，我们称之为 算法。下面通过例子来说明此法的基本思想。条件：所有的权数 思路：逐步探寻。下求 到 的最短路：1）从 出发，向 走。首先，从 到 的距离为0，给 标号（0）。画第一个弧。（表明已 标号，或已走出 ）从 出发，只有两条路可走 ，其距离为2）可能最短路为 给 划成粗线。划第二个弧。给 标号（4）。表明走出 后走向 的最短路目前看是 ，最优距离是4。现已考察完毕第二个圈内的路，或者说，已完成 的标号。3）接着往下考察，有三条路可走：可选择的最短路为 给 划成粗线。划第3个弧。给 标号（6）。4）接着往下考察，有四条路可走：可选择的最短路为 给 划成粗线。划第4个弧。给 标号（8）。5）接着往下考察，有四条路可走：可选择的最短路为 给 划成粗线。划第5个弧。给 标号（9）。6）接着往下考察，有四条路可走：可选择的最短路为 给 划成粗线。划第6个弧。给 标号（13）。7）接着往下考察，有四条路可走：可选择的最短路为 同时给 划成粗线。分别给 标号（14）。最后，从 逆寻粗线到 ，得最短路：长度为15。例例例例5-3 5-3 用狄克斯拉算法用狄克斯拉算法用狄克斯拉算法用狄克斯拉算法求解图求解图求解图求解图5-15-1所示最短路问题。所示最短路问题。所示最短路问题。所示最短路问题。4v1v2v3v4v6v5v722561413412图图5-1 例例5-3网络图网络图解：先将图解：先将图解：先将图解：先将图5-15-1的网络用矩阵形式表示出来的网络用矩阵形式表示出来的网络用矩阵形式表示出来的网络用矩阵形式表示出来:步骤步骤 考察点考察点 T标号点集标号点集 标标 号（号（表表P标号）标号）1v1v2，v7v1 v2 v3 v4 v5 v6 v7 0 -0+20+5 2 5 -23456v2v3v4v5v6v3，v7v4，v7v5，v6，v7v5，v72+22+42+6 4 6 8 -4+14+3 5 8 7 -5+45+1 5+4 8 6 96+2 8 8v78+18反向追踪，得到最优路线：反向追踪，得到最优路线：v1 v2 v3 v4 v6 v7v5讨讨论论：若若先先把把v7的的标标号号改改为为永永久久性性标标号号，该怎麽继续作下去？该怎麽继续作下去？56v6v7v5，v7v5v1 v2 v3 v4 v5 v6 v7 6+2 8 8 8+18 8 6 9反向追踪，得到相同的最优路线。反向追踪，得到相同的最优路线。反向追踪，得到相同的最优路线。反向追踪，得到相同的最优路线。在在在在得得得得到到到到从从从从起起起起点点点点到到到到终终终终点点点点的的的的最最最最短短短短路路路路长长长长的的的的同同同同时时时时，还还还还能得到什麽附加信息能得到什麽附加信息能得到什麽附加信息能得到什麽附加信息？（5）D氏标号法（氏标号法（Dijkstra）的特点的特点（获得的附加信息）：（获得的附加信息）：能能得得到到从从 （起起点点）到到各各点点的的最最短短路线和最短路长。路线和最短路长。第二讲：最短路问题的两个应用最短路问题在图论应用中处于很重要的地位，下面举两个实 际应用的例子。例 设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使 用，购买新的？如果继续使用旧的，要负维修费；若要购买 一套新的，要负购买费。试确定一个5年计划，使总支出最小若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表所示.项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210表8-2解：把这个问题化为最短路问题。用点 表示第i年初购进一台新设备，虚设一个点 ，表示第5年底。边 表示第i年购进的设备一直使用到第j年初（即第j-1年底）。边 上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买费、维修的全部费用（可由表8-2计算得到）。这样设备更新问题就变为：求从 到 的最短路问题.给 划成彩线。给 划成彩线。给 划成彩线。给 划成彩线。给 划成彩线。计算结果：最短路最短路路长为49。即：在第一年、第三年初各购买一台新设备为最优决策。这时5年的总费用为49。例13(选址问题)已知某地区的交通网络如图所示，其中点代表居民小区，边代表公路，为小区间公路距离，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？解 求中心的问题。解决方法：先求出 到其它各点的最短路长如再求即为所求。比如求 给 划成彩线。给 划成彩线。给 标号20。给 划成彩线。给 标号30。分别给 划成彩线。分别给 标号33。给 划成彩线。给 标号63。其它计算结果见下表：小区号0 30 50 63 93 45 609330 0 20 33 63 15 306350 20 0 20 50 25 405063 33 20 0 30 18 336393 63 50 30 0 48 639345 15 25 18 48 0 154860 30 40 33 63 15 063表 8.1由于 最小，所以医院应建在 ，此时离医院最远的小区 距离为48。一 概念l网路流一般在有向图上讨论,弧的方向为流的方向l定义网路上支路的容量为其最大通过能力，记为 rij，支路上的实际流量记为 xij,网络流为所有通过弧的流量的集合.l图中规定一个发点s，一个收点tl节点没有容量限制，流在节点不会存储4 4 最大流问题最大流问题可行流可行流满足以下条件的流称为可行流：满足以下条件的流称为可行流：1 1、每一个节点流量平衡、每一个节点流量平衡(流进流进=流出流出)2 2、00 x xijij u uijij(容量限制容量限制)总流量最大的可行流为总流量最大的可行流为最大流最大流链的前向弧链的前向弧,后向弧后向弧l是网络是网络G G中一条从始点中一条从始点VsVs到终点到终点VtVt的链的链,在链中与链的方在链中与链的方向一致的弧称为链的向一致的弧称为链的前向弧前向弧,在链中与链的方向相反的弧称在链中与链的方向相反的弧称为链的为链的前向弧前向弧.前向弧集合与后向弧集合为：前向弧集合与后向弧集合为：=(=(v v1 1,v v2 2),(),(v v3 3,v v6 6),),(v v4 4,v v7 7)=(=(v v3 3,v v2 2),(),(v v4 4,v v6 6)21xij=5rij=521xij=3rij=5饱和饱和弧弧弧弧、不饱和、不饱和弧弧弧弧、流量的间隙、流量的间隙（1，2）是饱和的）是饱和的2 2、如果、如果x xijij u uijij，边从边从i i到到j j的方向是不饱和的；的方向是不饱和的；（1，2）是不饱和的）是不饱和的间隙为间隙为 12=r12-x12=5-3=21 1、如果、如果x xijij=u uijij，边从边从i i到到j j的方向是饱和的；的方向是饱和的；截集与截集容量截集与截集容量定义：把网络的点集分割为两个非空集合S和S,且S包含 Vs 点，另一个包含 Vt 点,则把始点在S中,终点在S中的弧的集合称为分离Vs和Vt的一个截集.l截量是指截集中所有弧的容量之和 福特福特-富克森定理：富克森定理：网路的最大流等于最小截集容量网路的最大流等于最小截集容量st5342(4,0)(3,0)(2,0)(1,0)(1,0)(5,0)(3,0)(2,0)(5,0)增广链增广链(augmenting path)三三 确定网络最大流的标号法确定网络最大流的标号法l从任一个初始可行流出发，如从任一个初始可行流出发，如 0 流流l基本算法：找一条从基本算法：找一条从 s 到到 t 点的点的增广链增广链(augmenting path)l若在当前可行流下找不到增广链，则已得到最大流若在当前可行流下找不到增广链，则已得到最大流l增广链中与增广链中与 s 到到 t 方向一致的弧称为方向一致的弧称为前向弧前向弧，反之，反之后向弧后向弧 增广过程：前向弧增广过程：前向弧 f ij=fij+q q,后向弧后向弧 f ij=fij q q 增广后仍是可行流增广后仍是可行流 给出一个初始的可行流xij=02354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0找到所有的不饱和边，以及各边可以调整流量的方向2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0找到一条从1到7的不饱和链链的间隙为：=min8,3,1,8=1调整链的流量：xij=xij+2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0=3=1=8=8x=0调整流量，f=1。继续求出网络的不饱和边2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1x=1x=1x=1求出一条从1到7的不饱和链2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1x=1x=1x=1=1=6=9=7=min 7,1,6,9=1,调整流量 xij=xij+1,f=f+1=2调整流量，继续求出网络的不饱和边2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0求出一条从1到7的不饱和链2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0=5=8=7=min 7,5,8=5,调整流量 xij=xij+5,f=f+5=2+5=7调整流量，继续求出网络的不饱和边2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=6x=02354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=6x=0求出一条从1到7的不饱和链=min 6,7,4,3=3,调整流量 xij=xij+3,f=f+3=7+3=10=4=4=3=6调整流量，继续求出网络的不饱和边2354671f=10f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=0 x=0 x=9x=1x=1x=6x=0求出一条从1到7的不饱和链2354671f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=0 x=0 x=9x=1x=1x=6x=0f=10=1=3=7=3=min 3,1,3,7=1,调整流量 xij=xij+1,f=f+1=10+1=11调整流量，继续求出网络的不饱和边2354671f=11f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0已找不到一条从1到7的不饱和链，从1开始可以到达的节点为1，2，3已求得最大流2354671f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0f=11最大流f=11，最小割集为（2,5）（3,4）（3,5）u25+u34+u35=6+4+1=1144最大流问题最大流问题l最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。一、最大流的数学模型一、最大流的数学模型 例例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（的变化，它的各段管道（vi,vj）的流量的流量cij（容量）也是不一样的。容量）也是不一样的。cij的的单位为万加仑单位为万加仑/小时。如果使用这个网络系统从采地小时。如果使用这个网络系统从采地 v1向销地向销地 v7运送石运送石油，问每小时能运送多少加仑石油？油，问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图图11-2644最大流问题最大流问题 我们可以为此例题建立线性规划数学模型：我们可以为此例题建立线性规划数学模型：设弧设弧(vi,vj)上流量为上流量为fij，网络上的总的流量为，网络上的总的流量为F，则有：，则有：55最小费用最大流问题最小费用最大流问题l 最小费用最大流问题：给了一个带收发点的网络，对每一条弧最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi,vj），），除了给出容量除了给出容量cij外，还给出了这条弧的单位流量的费用外，还给出了这条弧的单位流量的费用bij，要，要求一个最大流求一个最大流F，并使得总运送费用最小。并使得总运送费用最小。一、最小费用最大流的数学模型一、最小费用最大流的数学模型 例例7 由于输油管道的长短不一，所以在例由于输油管道的长短不一，所以在例6中每段管道（中每段管道（vi,vj）除）除了有不同的流量限制了有不同的流量限制cij外外，还有不同的单位流量的费用，还有不同的单位流量的费用bij，cij的的单位为万单位为万加仑加仑/小时，小时，bij的的单位为百元单位为百元/万加仑。如图。从采地万加仑。如图。从采地 v1向销地向销地 v7运送石运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。量和最小费用。(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)55最小费用最大流问题最小费用最大流问题 这个最小费用最大流问题也是一个线性规划的问题。这个最小费用最大流问题也是一个线性规划的问题。解：我们用线性规划来求解此题，可以分两步走。解：我们用线性规划来求解此题，可以分两步走。第一步，先求出此网络图中的最大流量第一步，先求出此网络图中的最大流量F，这已在例，这已在例6中建中建立了线性规划的模型，通过管理运筹学软件已经获得结果。立了线性规划的模型，通过管理运筹学软件已经获得结果。第二步，在最大流量第二步，在最大流量F的所有解中，找出一个最小费用的的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：解，我们来建立第二步中的线性规划模型如下：仍然设弧（仍然设弧（vi,vj）上的流量为）上的流量为fij，这时已知网络中最大流，这时已知网络中最大流量为量为F，只要在例，只要在例6的约束条件上，再加上总流量必须等于的约束条件上，再加上总流量必须等于F的的约束条件：约束条件：f12=f14=F,即得此线性规划的约束条件，此线性规划即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用的目标函数显然是求其流量的最小费用 。由此得到线性规划模型如下：由此得到线性规划模型如下：55最小费用最大流问题最小费用最大流问题 55最小费用最大流问题最小费用最大流问题 用运筹学软件，可求得如下结果：用运筹学软件，可求得如下结果：f f1212=4,f=4,f1414=6,=6,f f2525=3,f=3,f2323=1,f=1,f4343=3,F=3,F5757=5,f=5,f3636=2,f=2,f4646=1,f=1,f4747=2,f=2,f6767=3,f=3,f3535=2=2。其最。其最优值优值(最小费用最小费用)=145)=145。对照前面例。对照前面例6 6的结果，可对最小费用最的结果，可对最小费用最大流的概念有一个深刻的理解。大流的概念有一个深刻的理解。如果我们把例如果我们把例7 7的问题改为：每小时运送的问题改为：每小时运送6 6万加仑的石油从万加仑的石油从采地采地v v1 1到销地到销地v v7 7最小费用是多少？应怎样运送？这就变成了一最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧在给定了收点和发点并对每条弧(v vi i,v,vj j)赋权以容量赋权以容量c cijij及单位及单位费用费用b bijij的网络中，求一个给定值的网络中，求一个给定值f f的流量的最小费用，这个给的流量的最小费用，这个给定值定值f f的流量应小于等于最大流量的流量应小于等于最大流量F F，否则无解。求最小费用流，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量条件中的发点流量F F改为改为f f即可。在例即可。在例6 6中只要把中只要把f f1212+f+f1414=F=F改为改为f f1212+f+f1414=f=6=f=6得到了最小费用流的线性规划的模型了。得到了最小费用流的线性规划的模型了。