《运筹学 --图与网络1(qh).ppt》由会员分享，可在线阅读，更多相关《运筹学 --图与网络1(qh).ppt（201页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第十章第十章图与网络分析图与网络分析引言引言图图论论是是专专门门研研究究图图的的理理论论的的一一门门数数学学分分支支，属属于于离离散散数数学学范范畴畴，与与运运筹筹学学有有交交叉叉，它它有有200多多年年历历史史，大大体体可可划划分分为为三三个个阶阶段段：第第一一阶阶段段是是从从十十八八世世纪纪中中叶叶到到十十九九世世纪纪中中叶叶，处处于于萌萌芽芽阶阶段段，多多数数问问题题为为游游戏戏而而产产生生，最最有有代代表表性性的的工工作作是是所所谓谓的的Euler七七桥桥问问题题(1736年年)，即即一一笔笔画画问题。问题。第第二二阶阶段段是是从从十十九九世世纪纪中中叶叶到到二二十十世世纪纪中中叶叶，
2、这这时时，图图论论问问题题大大量量出出现现，如如Hamilton问问题题，地地图图染染色色的的四四色色问问题题以以及及可可平平面面性性问问题题等等，这这时时，也也出出现现用用图图解解决决实实际际问问题题，如如Cayley把把树树应应用用于于化化学学领领域域，Kirchhoff用用树树去去研研究究电电网络等网络等.第第三三阶阶段段是是二二十十世世纪纪中中叶叶以以后后，由由生生产产管管理理、军军事事、交交通通、运运输输、计计算算机机网网络络等等方方面面提提出出实实际际问问题题，以以及及大大型型计计算算机机使使大大规规模模问问题题的的求求解解成成 为为 可可 能能，特特 别别 是是 以以 Ford和
3、和Fulkerson建建立立的的网网络络流流理理论论，与与线线性性规规划划、动动态态规规划划等等优优化化理理论论和和方方法法相相互互渗渗透透，促促进进了了图图论论对对实实际际问题的应用。问题的应用。例例10-1：哥尼斯堡七桥问题哥尼斯堡七桥问题哥哥尼尼斯斯堡堡（现现名名加加里里宁宁格格勒勒）是是欧欧洲洲一一个个城城市市，Pregei河河把把该该城城分分成成两两部部分分，河河中中有有两两个个小小岛岛，十十八八世世纪纪时时，河河两两边边及及小小岛岛之之间间共共有有七七座座桥桥，当当时时人人们们提提出出这这样样的的问问题题：有有没没有有办办法法从从某某处处（如如A）出出发发，经经过过各各桥桥一一次次
4、且且仅仅一一次次最最后后回回到到原原地呢？地呢？ABCD最最后后，数数学学家家Euler在在1736年年巧巧妙妙地地给给出出了了这这个个问问题题的的答答案案，并并因因此此奠奠定定了了图图论论的的基基础础，Euler把把A、B、C、D四四块块陆陆地地分分别别收收缩缩成成四四个个顶顶点点，把把桥桥表表示示成成连连接接对对应应顶顶点点之之间间的的边边，问问题题转转化化为为从从任任意意一一点点出出发发，能能不不能能经经过过各各边边一一次次且且仅仅一一次次，最最后后返返回回该该点点。这这就就是是著著名名的的Euler问题。问题。ACBD例例10-2：有有7个个人人围围桌桌而而坐坐，如如果果要要求求每每次
5、次相相邻邻的的人人都都与与以以前前完完全全不不同同，试试问问不不同同的的就就座座方方案案共共有有多少种？多少种？用用顶顶点点表表示示人人，用用边边表表示示两两者者相相邻邻，因因为为最最初初任任何何两两个个人人都都允允许许相相邻邻，所所以以任任何何两两点点都都可可以以有边相连。有边相连。1 12 23 37 76 64 45 5假定第一次就座方案是假定第一次就座方案是（1，2，3，4，5，6，7，1），那那么么第第二二次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻，只只能能从从图图中删去这些边。中删去这些边。1 12 23 37 76 64 45 51 12 23
6、37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 5假定第二次就座方案是假定第二次就座方案是（1，3，5，7，2，4，6，1），那那么么第第三三次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻，只只能能从图中删去这些边。从图中删去这些边。1 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 7
7、6 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 5假定第三次就座方案是假定第三次就座方案是（1，4，7，3，6，2，5，1），那那么么第第四四次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻，只只能能从从图图中中删删去去这这些些边边，只只留留下下7点点孤孤立立点点，所所以以该该问问题题只只有有三三个个就就座座方方案。案。1 12 23 37 76 64 45 51 12 23 37 76 6
8、4 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 5例例10-3：哈哈密密顿顿（Hamilton）回回路路是是十十九九世世纪纪英英国国数数学学家家哈哈密密顿顿提提出出，给给出出一一个个正正12面面体体图图形形，共共有有20个个顶顶点点表表示示20个个城城市市，要要求求从从某某个个城城市市出出发发沿沿着着棱棱线线寻寻找找一一条条经经过过每每个个城城市市一一次次而而且且仅仅一一次次，最最后
9、后回回到到原原处处的的周周游游世世界界线线路（并不要求经过每条边）。路（并不要求经过每条边）。一.有甲、乙、丙、丁、戊、己6名运动员报名参加A，B，C，D，E，F,6项比赛。下表给出6个运动员报名参加的比赛项目。问6个项目比赛顺序如何安排，做到每名运动员不连续参加两项比赛。甲乙丙丁戊己ABCDEF解解:比赛项目作为点比赛项目作为点,两个比赛项目由同一个人参加连一边两个比赛项目由同一个人参加连一边.如图如图:ABDFCE比赛顺序可安排A-C-B-F-E-D或A-F-B-C-D-E甲乙丙丁戊己ABCDEF10.1 10.1 图的基本概念图的基本概念图论是专门研究图的理图论是专门研究图的理论的一门数
10、学分支，主要研论的一门数学分支，主要研究点和线之间的究点和线之间的几何关系。几何关系。定义定义：（图）：（图）设设G=（V，E，）其中：其中：V=（v1，v2，.vm）是是m个顶点集合；个顶点集合；E=（e1，e2，.en）是是n条边集合。条边集合。是描述边与顶点之间关系的函数是描述边与顶点之间关系的函数称称称称G=G=（V V，E E，）为为为为 一个图，如果它满足：一个图，如果它满足：一个图，如果它满足：一个图，如果它满足：（1 1）V V非空；非空；非空；非空；（2 2）E E是一个不与是一个不与是一个不与是一个不与VV中顶点相交的边集合；中顶点相交的边集合；中顶点相交的边集合；中顶点相
11、交的边集合；（3 3）是关联函数。是关联函数。是关联函数。是关联函数。V V，E E，称为图的称为图的称为图的称为图的三要素三要素三要素三要素。说明：说明：说明：说明：（1 1）V V非空，即没有顶点的图不讨论；非空，即没有顶点的图不讨论；非空，即没有顶点的图不讨论；非空，即没有顶点的图不讨论；（2 2）E E无非空条件，即允许没有边；无非空条件，即允许没有边；无非空条件，即允许没有边；无非空条件，即允许没有边；（3 3）条件（）条件（）条件（）条件（2 2）是指点只在边的端点）是指点只在边的端点）是指点只在边的端点）是指点只在边的端点处相交；处相交；处相交；处相交；（4 4）任一条边必须与一
12、对顶点关联，）任一条边必须与一对顶点关联，）任一条边必须与一对顶点关联，）任一条边必须与一对顶点关联，反之不然。反之不然。反之不然。反之不然。v1v1v3v3v2v2v4v4v5v5v1v1v3v3v2v2v4v4v5v5有向图有向图v1v1v3v3v2v2v4v4v6v6v5v5e1e1e3e3e5e5e6e6e4e4e8e8e7e7e2e2例例10-5V=（v1，v2，.v6）E=（e1，e2，.e8）（e1）=（v1，v2）（e2）=（v1，v2）（e7）=（v3，v5）（e8）=（v4，v4）次（度）次（度）：与顶点关联的边数。：与顶点关联的边数。简单图简单图：没有环和重边的图。：没有
13、环和重边的图。悬挂点悬挂点：次为：次为1的点。的点。悬挂边悬挂边：次为：次为1的边。的边。孤立点孤立点：次为：次为0的点。的点。(e8)=(v4，v4),称为自回路称为自回路(环环)；v6是孤立点，是孤立点，v5为悬挂点，为悬挂点，e7为悬挂边，为悬挂边，顶点顶点v3的次为的次为4，顶点，顶点v2的次为的次为3。定理定理1：在一个图中，所有顶点次的和：在一个图中，所有顶点次的和等于边的两倍。等于边的两倍。定理定理8-1：在一个图中，所有顶点次：在一个图中，所有顶点次的和等于边的两倍。的和等于边的两倍。定理定理2：在任意一个图中，奇顶点的：在任意一个图中，奇顶点的个数必为偶数。个数必为偶数。证明
14、证明:设设V1和和V2分别为分别为G中奇点和偶点的集合中奇点和偶点的集合,定理定理8-1：在一个图中，所有：在一个图中，所有顶点次的和等于边的两倍。顶点次的和等于边的两倍。定理定理8-2：在任意一个图中，：在任意一个图中，奇顶点的个数必为偶数。奇顶点的个数必为偶数。注意：注意：一个图的形状并不唯一个图的形状并不唯一。但它的三要素是不能变一。但它的三要素是不能变的。的。注意：注意：注意：注意：一个图的形状并不唯一。但它的三要素是不能变的。一个图的形状并不唯一。但它的三要素是不能变的。一个图的形状并不唯一。但它的三要素是不能变的。一个图的形状并不唯一。但它的三要素是不能变的。例如：这两个图均为例如
15、：这两个图均为例如：这两个图均为例如：这两个图均为KK4 4v v1 1v v2 2v v3 3v v4 4v v1 1v v2 2v v3 3v v4 4定义定义：设设G=（V，E，）和和G1=（V1，E1，1）。）。如果如果V1 V，E1 E则称则称G1为为G的子图；的子图；如果如果G1=（V1，E1，1）是是G=（V，E，）子图，并且子图，并且V1=V，则称则称G1为为G的生成子图；的生成子图；如果如果V1 V，E1是是E中所有端点属中所有端点属于于V1的边组成的集合，的边组成的集合，则称则称G1是是G的关于的关于V1的导出子图；的导出子图；如果如果G1=（V1，E1，1）是是G=（V，
16、E，）子图，并且子图，并且V1=V，则称则称G1为为G的的生成（支撑）子图。生成（支撑）子图。v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2v1v1v5v5v4v4v2v2e1e1e5e5e3e3（a a）的子图的子图的子图的子图v1v1v5v5v4v4v2v2v3v3e8e8e6e6e5e5e2e2（a a）的生的生的生的生成子图成子图成子图成子图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2v1v1v5v5v4v4v2v2e1e1e8e8e7e7e6e6e5e5e4e4e3e
17、3（a a）的导的导的导的导出子图出子图出子图出子图定义（简单图）定义（简单图）如果图中任意如果图中任意两个顶点之间至多有一条边，两个顶点之间至多有一条边，则称为简单图，否则称为多重则称为简单图，否则称为多重图。即图。即:无环、无重边的图。无环、无重边的图。定义（简单图）定义（简单图）如果图中任意如果图中任意两个顶点之间至多有一条边，两个顶点之间至多有一条边，则称为简单图，否则称为多重则称为简单图，否则称为多重图。图。定义（有向图）定义（有向图）如果图中每一如果图中每一条边都规定了方向，则称为有条边都规定了方向，则称为有向图。向图。有向图去掉箭头得到的图称有向图去掉箭头得到的图称为基础图。为基
18、础图。定义（链）定义（链）如果图中的某些点、如果图中的某些点、边可以排列成点和边的交错序边可以排列成点和边的交错序列，则称此为一条链。列，则称此为一条链。定义（链）定义（链）如果图中的某些点、如果图中的某些点、边可以排列成点和边的交错序边可以排列成点和边的交错序列，则称此为一条链。列，则称此为一条链。定义（圈）定义（圈）如一条链中起点和如一条链中起点和终点重合，则称此为一条圈。终点重合，则称此为一条圈。v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e
19、6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图链（路）链（路）初等链（点
20、不同）初等链（点不同）简单链（边不同）简单链（边不同）v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3圈（回路）圈（回路）圈（回路）圈（回路）连通图：图中任何两个点之间必有一条链。连通图：图中任何两个点之间必有一条链。否则，称为不连通图。否则，称为不连通图。v1v1v5v5v4v4v2v2v3v3e1e1e7e7e6e6e5e5e4e4e3e3e2e2v6v6v7v7v8v8二、图的矩阵表
21、示二、图的矩阵表示一个图非常直观，但是不一个图非常直观，但是不容易计算，特别不容易在计算容易计算，特别不容易在计算机上进行计算，一个有效的解机上进行计算，一个有效的解决办法是将图表示成矩阵形式，决办法是将图表示成矩阵形式，通常采用的矩阵是邻接矩阵、通常采用的矩阵是邻接矩阵、边长邻接矩阵、弧长矩阵和关边长邻接矩阵、弧长矩阵和关联矩阵。联矩阵。1邻接矩阵邻接矩阵邻接矩阵邻接矩阵A表示图表示图G的顶点之的顶点之间的邻接关系，它是一个间的邻接关系，它是一个nn的矩的矩阵，如果两个顶点之间有边相联时，阵，如果两个顶点之间有边相联时，记为记为1，否则为，否则为0。v1v1v2v2v3v3v4v4v1v2v
22、3v4v10111v21110v31101v41010无向图的邻接矩阵是对称矩阵。无向图的邻接矩阵是对称矩阵。无向图的邻接矩阵是对称矩阵。无向图的邻接矩阵是对称矩阵。v1v1v2v2v3v3v4v4v1v1v5v5v4v4v3v3v2v2也可以也可以也可以也可以对有向对有向对有向对有向图图图图v1v2v3v4v5v100011v210010v301100v401101v510010二、边长邻接矩阵二、边长邻接矩阵在图的各边上一个数量指标，在图的各边上一个数量指标，具体表示这条边的权（距离，单价，具体表示这条边的权（距离，单价，通过能力等）通过能力等）赋权图或网络。赋权图或网络。无向网络；有向网
23、络；混合网络；无向网络；有向网络；混合网络；边权网络；点权网络；边权网络；点权网络；以边长代替邻接矩阵中的元素得到以边长代替邻接矩阵中的元素得到边长邻接矩阵。边长邻接矩阵。v1v1v2v2v3v3v4v42 25 56 64 43 34 4v1v2v3v4v10256v2243 v35304v46 40其中其中 表示两点之间不能连接表示两点之间不能连接。3弧长矩阵弧长矩阵对有向图的弧可以用弧长对有向图的弧可以用弧长矩阵来表示。其中矩阵来表示。其中 表示两点表示两点之间没有之间没有弧弧连接连接。v1v1v5v5v4v4v3v3v2v21 14 42 23 32 22 26 61 12 2v1v2
24、v3v4v5v101 2v2 02 4v3 201 v4 3206v5 04关联矩阵关联矩阵关联矩阵关联矩阵B揭示了图揭示了图G的顶点和的顶点和边之间的关联关系，它是一个边之间的关联关系，它是一个nxm矩阵。矩阵。1（vi，vk）=ejBij=-1（vk，vi）=ej0其他其他v1v1v2v2v4v4v3v3e1e1e2e2e4e4e3e3e7e7e5e5e6e6e1e2e3e4e5e6e7v11-110000v200-1-1-100v3010101-1v4-10001-11对无向图不存在对无向图不存在-1元素元素。10-2 10-2 最优树问题（或最小树）最优树问题（或最小树）树是一类极其简
25、单而很有用的图。树是一类极其简单而很有用的图。定义（链）定义（链）如果图中的某些点、边可如果图中的某些点、边可以排列成点和边的交错序列，则称此以排列成点和边的交错序列，则称此为一条链。为一条链。定义（链）定义（链）如果图中的某些点、边如果图中的某些点、边可以排列成点和边的交错序列，则可以排列成点和边的交错序列，则称此为一条链。称此为一条链。定义（圈）定义（圈）如一条链中起点和终点如一条链中起点和终点重合，则称此为一条圈。重合，则称此为一条圈。定义（连通图）定义（连通图）如果图中的任意如果图中的任意两点之间至少存在一条通路，则两点之间至少存在一条通路，则称图为连通图，否则为不连通图。称图为连通图
26、，否则为不连通图。定义（连通图）定义（连通图）如果图中的任意如果图中的任意两点之间至少存在一条通路，则两点之间至少存在一条通路，则称图为连通图，否则为不连通图。称图为连通图，否则为不连通图。定义（树）定义（树）一个无圈的连通图称一个无圈的连通图称为树。如果一个无圈的图中每一为树。如果一个无圈的图中每一个分支都是树，则称图为森林。个分支都是树，则称图为森林。定理定理定理定理3 3：设图设图设图设图G=(V,E)G=(V,E)是一个树，顶点个数是一个树，顶点个数是一个树，顶点个数是一个树，顶点个数,则则则则GG中至少有两个悬挂中至少有两个悬挂中至少有两个悬挂中至少有两个悬挂点。点。点。点。证明：设
27、证明：设证明：设证明：设是是是是GG中含边数最多的初等链。中含边数最多的初等链。中含边数最多的初等链。中含边数最多的初等链。往证往证往证往证是悬挂点。若是悬挂点。若是悬挂点。若是悬挂点。若，则存在边，则存在边，则存在边，则存在边因为因为因为因为GG为树，不含圈，故不在为树，不含圈，故不在为树，不含圈，故不在为树，不含圈，故不在P P上。上。上。上。是比是比是比是比P P更长的初等链。矛盾。更长的初等链。矛盾。更长的初等链。矛盾。更长的初等链。矛盾。定理定理定理定理4 4：设图设图设图设图G=(V,E)G=(V,E)是一个树的充分必要条件是是一个树的充分必要条件是是一个树的充分必要条件是是一个树
28、的充分必要条件是GG不含圈，且恰有不含圈，且恰有不含圈，且恰有不含圈，且恰有条边。条边。条边。条边。证明：证明：证明：证明：必要性：必要性：必要性：必要性：用数学归纳法：用数学归纳法：用数学归纳法：用数学归纳法：时，显然成立。设对时，显然成立。设对时，显然成立。设对时，显然成立。设对时也成时也成时也成时也成立。设图立。设图立。设图立。设图GG含含含含n+1n+1个点，由定理个点，由定理个点，由定理个点，由定理3 3，GG含悬挂点含悬挂点含悬挂点含悬挂点，考虑图，考虑图，考虑图，考虑图，有，有，有，有充分性：充分性：充分性：充分性：往证往证往证往证GG为连通图，若为连通图，若为连通图，若为连通图
29、，若GG不为连通图，则有不为连通图，则有不为连通图，则有不为连通图，则有s s（s2s2）个连通分图个连通分图个连通分图个连通分图。每一个都连通不含圈，即为树。每一个都连通不含圈，即为树。每一个都连通不含圈，即为树。每一个都连通不含圈，即为树。矛盾矛盾定理定理定理定理5 5：设图设图设图设图G=(V,E)G=(V,E)是一个树的充分必要条件是是一个树的充分必要条件是是一个树的充分必要条件是是一个树的充分必要条件是GG是连通图，且是连通图，且是连通图，且是连通图，且证明：证明：证明：证明：必要性：由定理必要性：由定理必要性：由定理必要性：由定理4 4即得。即得。即得。即得。充分性：充分性：充分性
30、：充分性：往证往证往证往证GG不含圈。对点用数学归纳法：不含圈。对点用数学归纳法：不含圈。对点用数学归纳法：不含圈。对点用数学归纳法：时，显然成立。设对时，显然成立。设对时，显然成立。设对时，显然成立。设对时也成立。设图时也成立。设图时也成立。设图时也成立。设图GG含含含含n+1n+1个点，个点，个点，个点，GG必含悬挂点。否则，必含悬挂点。否则，必含悬挂点。否则，必含悬挂点。否则，设设设设是是是是GG的悬挂点，考虑的悬挂点，考虑的悬挂点，考虑的悬挂点，考虑仍为连通图，仍为连通图，仍为连通图，仍为连通图，由归纳假设知由归纳假设知由归纳假设知由归纳假设知不含圈，则不含圈，则不含圈，则不含圈，则G
31、G必不含圈。必不含圈。必不含圈。必不含圈。定理定理定理定理6 6：设图设图设图设图G=(V,E)G=(V,E)是一个树的充分必要条件是是一个树的充分必要条件是是一个树的充分必要条件是是一个树的充分必要条件是GG的任意顶点之间恰有一条链。的任意顶点之间恰有一条链。的任意顶点之间恰有一条链。的任意顶点之间恰有一条链。矛盾矛盾（1）G不含圈不含圈（2）G是连通图是连通图（3）（4）图）图G=(V,E)是一个树是一个树上述条件有两个成立，就推出其余条件成立。上述条件有两个成立，就推出其余条件成立。树的性质：树的性质：1在图中任意两点之间必有一条而在图中任意两点之间必有一条而且只有一条通路。且只有一条通
32、路。树的性质：树的性质：1在图中任意两点之间必有一条而在图中任意两点之间必有一条而且只有一条通路。且只有一条通路。2在图中划去一条边，则图不连通。在图中划去一条边，则图不连通。树是边最少的连通图树是边最少的连通图树的性质：树的性质：1在图中任意两点之间必有一条而在图中任意两点之间必有一条而且只有一条通路。且只有一条通路。2在图中划去一条边，则图不连通。在图中划去一条边，则图不连通。3在图中不相邻的两个顶点之间加在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。一条边，可得一个且仅得一个圈。树的性质：树的性质：1在图中任意两点之间必有一条而在图中任意两点之间必有一条而且只有一条通路。且只
33、有一条通路。2在图中划去一条边，则图不连通。在图中划去一条边，则图不连通。3在图中不相邻的两个顶点之间加在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。一条边，可得一个且仅得一个圈。4图中边数有图中边数有n=p-1（p为顶点数）为顶点数）a ab bc cf fe ed dh hg g例例10-6b bf fe ed db bf fd dg gb bc ce ed da ab bc ch ha af fd dg g定义（生成树）定义（生成树）如果图如果图T是是G的一的一个生成子图，而且个生成子图，而且T又是一棵树，又是一棵树，则称图则称图T为一棵生成树。对于分为一棵生成树。对于分离（
34、不连通图）图，则称为生成离（不连通图）图，则称为生成森林。森林。一个子图与生成树的区别是：子一个子图与生成树的区别是：子图与原图相比少弧又少点，生成图与原图相比少弧又少点，生成树与原图相比少弧不少点。树与原图相比少弧不少点。定理定理图图G有生成树的充分必要条有生成树的充分必要条件为图是连通图。件为图是连通图。定义（最优树）定义（最优树）在赋权图在赋权图G中，一中，一棵生成树所有树枝上权的和，称为棵生成树所有树枝上权的和，称为生成树的权。具有最小权的生成树，生成树的权。具有最小权的生成树，称为最优树（或最小树）。称为最优树（或最小树）。求最小树的方法有求最小树的方法有破圈法破圈法和和避圈法避圈法
35、。v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636例例10-7破圈法破圈法破圈法破圈法：在给定连通图：在给定连通图：在给定连通图：在给定连通图GG中，任取一圈，去掉一条最大权边中，任取一圈，去掉一条最大权边中，任取一圈，去掉一条最大权边中，任取一圈，去掉一条最大权边（如果有两条或两条以上的边都是权最大的边，则任意去掉（如果有两条或两条以上的边都是权最大的边，则任意去掉（如果有两条或两条以上的边都是权最大的边，则任意去掉（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条边），在余图中（是图其
36、中一条边），在余图中（是图其中一条边），在余图中（是图其中一条边），在余图中（是图GG的支撑子图）任取一圈，的支撑子图）任取一圈，的支撑子图）任取一圈，的支撑子图）任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即可去掉一条最大权边，重复下去，直到余图中无圈为止，即可去掉一条最大权边，重复下去，直到余图中无圈为止，即可去掉一条最大权边，重复下去，直到余图中无圈为止，即可得到图得到图得到图得到图GG的最小树。的最小树。的最小树。的最小树。v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v
37、1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 32
38、82817174 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 328
39、2817174 41 123233636避圈法避圈法避圈法避圈法（kruskalkruskal算法）：在连通图算法）：在连通图算法）：在连通图算法）：在连通图GG中，任取权值最小的一条边中，任取权值最小的一条边中，任取权值最小的一条边中，任取权值最小的一条边（若有两条或两条以权数相同且最小，则任取一条），在未选边（若有两条或两条以权数相同且最小，则任取一条），在未选边（若有两条或两条以权数相同且最小，则任取一条），在未选边（若有两条或两条以权数相同且最小，则任取一条），在未选边中选一条权值权值最小的边，要求所选边与已选边不构成圈，重中选一条权值权值最小的边，要求所选边与已选边不构成圈，重中选一
40、条权值权值最小的边，要求所选边与已选边不构成圈，重中选一条权值权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止。已选边与顶点复下去，直到不存在与已选边不构成圈的边为止。已选边与顶点复下去，直到不存在与已选边不构成圈的边为止。已选边与顶点复下去，直到不存在与已选边不构成圈的边为止。已选边与顶点构成的图构成的图构成的图构成的图T T就是所求最小树。就是所求最小树。就是所求最小树。就是所求最小树。v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4
41、v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5
42、v6v6202015159 9161625253 3282817174 41 123233636总造价总造价=1+4+9+3+17+23=573最短路问题最短路问题(19591959年年年年DijkstraDijkstra给出最短路算法给出最短路算法给出最短路算法给出最短路算法)最短路问题是网络分析中的一个基本问题，它不仅可以直接应用最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局于于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局等，而且经常被作为一个基本工具，用于解决其它的优化问题等，而且经常被作为一个基本工具，用于解
43、决其它的优化问题.定义给定一个赋权有向图D=(V,A)，记D中每一条弧上的权为为。给定D中一个起点和终点，设P是D中从到的一条路.则定义路P的权是P中所有弧的权之和.记为，即又若P*是D图中到的一条路，且满足则称P*为从到的最短路。下面介绍在一个赋权有向图中寻求最短路的方法，这种方法实际上求出了从给定到任一个顶点的最短路.如下事实是经常要利用的，即如果P是D中从到的最短路，是P中的一点，那么从沿P到路也是从到的最短路.事实上，如果这个结论不成立，设Q是从到的最短路，令P是从沿Q到达，再从沿P到达的路，那么P的权就比P的权小，这与P是从到的最短路矛盾.PPQP例例1：求图：求图A到到B的最短路的
44、最短路ABCDEFG1353584612450BCDEFG135358461245013BCDEFG13535846124501364BCDEFG135358461245013645BCDEFG1353584612450136459最短路为最短路为ACGFBv7v6v4v3G7182433147202v1v2v5例例2：求图：求图到到的最短路的最短路v1v7v7v6v4v3G7182433147202v1v2v514v7v6v4v3G7182433147202v1v2v5514v7v6v4v3G7182433147202v1v2v55414v7v6v4v3G7182433147202v1v2v
45、557414v7v6v4v3G7182433147202v1v2v5574914v1到v7的最短路径是：v1v3v4v7，（5分）分）最短距离为最短距离为1+4+2=7。v7v6v4v3G7182433147202v1v2v5574914v1到v7的最短路径是：v1v3v4v7，（5分）分）最短距离为最短距离为1+4+2=7。例：例：某交通网络如下图，求某交通网络如下图，求v1 1到到v8 8的最的最短路线短路线解：解：v1v2v4v5v6v7v86312216104310446练习：求最短路练习：求最短路v1v2v4v5v6v7v86312216104310446v1V2(v(v3 3,5)
46、,5)V3(v(v1 1,3),3)V4(v(v1 1,1),1)V5(v(v2 2,6),6)V6(v(v5 5,10),10)6312216104 104364V2(v1,6）v7(v(v5 5,9),9)v8(v(v5 5,12),12)例设备更新问题设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要负购买费。试确定一个负购买费。试确定一个5年计划，使总支出最小。年计划，使总支出最小。若已知设备在各年
47、的购买费，及不同机器役龄时的残值与维修费若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表，如表1所示所示表表1项目第1年第2年第3年第4年第5年购买费1111121213机器役龄0-11-22-33-44-5维修费5681118残值43210解：解：把把这这个个问题问题化化为为最短路最短路问题问题。设设bi 表示设备在第表示设备在第i 年年初的购买费年年初的购买费,ci 表示设备使用表示设备使用i 年后的维修费年后的维修费,V=v1,v2,v6,点点vi表示第表示第i 年年初购进一台新设备年年初购进一台新设备,虚设一个点虚设一个点v6表示第表示第5 5年年底年年底.E=vivj|
48、1ij6.若每年购置一台新设备，则购置费为：若每年购置一台新设备，则购置费为：11+11+12+12+13=5911+11+12+12+13=59，每年的维修费为，每年的维修费为5 5元，元，共共59+5*5=84.59+5*5=84.若在若在1，2，3年购置一台新设备，则购置费为：年购置一台新设备，则购置费为：11+12+13=36，每年的维修费为（，每年的维修费为（5+6）+（5+6）+5=27，共，共36+27=63.设备使用一年后就更新则不划算。设备使用一年后就更新则不划算。由表由表1知，设备使用三年后应当更新。知，设备使用三年后应当更新。这样上述设备更新问题就变为：在有向赋权图这样上
49、述设备更新问题就变为：在有向赋权图G=(V,E,F)(图解如下图解如下)中求中求v1到到v6的最短路问题的最短路问题.由实际问题可知由实际问题可知,设备使用三年后应当更新设备使用三年后应当更新,因此删除该图中因此删除该图中v1到到v5,v1到到v6,v2到到v6的连线；又的连线；又设备使用一年后就更新则不划算设备使用一年后就更新则不划算,因此再删除该因此再删除该图中图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6（费用费用22+3122+31）和和v1v4v6 （费用费用22+31）
50、.而这两条路都是而这两条路都是v1到到v6的最短路的最短路.3网络最大流问题网络最大流问题 引例：如下输水网络，南水北调工程，从引例：如下输水网络，南水北调工程，从引例：如下输水网络，南水北调工程，从引例：如下输水网络，南水北调工程，从vsvs到到到到vtvt送水，送水，送水，送水，弧旁数字前者为管道容量，后者为现行流量，如何调弧旁数字前者为管道容量，后者为现行流量，如何调弧旁数字前者为管道容量，后者为现行流量，如何调弧旁数字前者为管道容量，后者为现行流量，如何调整使输水最多？整使输水最多？整使输水最多？整使输水最多？vsvtv2v1v4v3(3,3)(5,1)(1,1)(4,3)(1,1)(