数学建模之图论模型讲解ppt课件.ppt

《数学建模之图论模型讲解ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模之图论模型讲解ppt课件.ppt（135页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论模型图论模型数学系数学系 孙艳蕊孙艳蕊主要内容主要内容 图模型图模型 最短路问题最短路问题 最小生成树问题最小生成树问题 旅行售货员问题旅行售货员问题 最大流问题最大流问题 图论的基本概念图论的基本概念 匹配问题匹配问题一、图模型 例例1. 哥尼斯堡七桥问题哥尼斯堡七桥问题(18世纪，世纪，1736年年) (1) 问题问题 能否从一块陆地出发能否从一块陆地出发,走遍每座桥一次且仅一次然走遍每座桥一次且仅一次然后回到出发地后回到出发地? ABCD普瑞格尔河普瑞格尔河 (2)问题分析与模型假设问题分析与模型假设 问题的本质是能否从一地无重复地一次走问题的本质是能否从一地无重复地一次走遍七桥遍七

2、桥, , 与所走过的桥的大小、形状、长短、与所走过的桥的大小、形状、长短、曲直等均无关，因此不妨将其视为一条弧线；曲直等均无关，因此不妨将其视为一条弧线； 四块陆地可重复经历四块陆地可重复经历,至于陆地的大小、形至于陆地的大小、形状、质地等也与问题的无关，因而可视四块陆状、质地等也与问题的无关，因而可视四块陆地为四个点地为四个点 A、B、C、D。 对四个陆地对四个陆地 A、B、C、D，若其间有桥，则，若其间有桥，则用一条弧线连接起来，有两座桥，则连两条不重用一条弧线连接起来，有两座桥，则连两条不重合的弧线，便得到一个图，并称代表陆地的四个合的弧线，便得到一个图，并称代表陆地的四个点为点为顶点顶

3、点 ，代表桥的弧线为，代表桥的弧线为 边边 。A B C D 问题变成了：问题变成了：能否从这个图上任一顶点出发，能否从这个图上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。经过每条边一次且仅一次而回到出发顶点。-Euler-回路回路(圈圈)问题。问题。ABCD 例例2 药品存储问题药品存储问题 有有8种化学药品种化学药品A、B、C、D、P、R、S和和T要放要放进贮藏室保管进贮藏室保管,出于安全原因出于安全原因,下列各组药品不能下列各组药品不能贮在同一室内贮在同一室内:AR，AC，AT，RP，PS，ST，TB，BD，DC，RS，RB，PD，SC，SD，试为这，试为这8种药品设种药品设计一

4、个使用房间数最少的贮藏方案计一个使用房间数最少的贮藏方案。AR，AC，AT，RP，PS，ST，TB，BD，DC，RS，RB，PD，SC，SD.ARDSBTCP至少需用至少需用3个房间：个房间：A,S,B/D,T,R/C,P每种药品作为一个顶每种药品作为一个顶点，不能放在一起的点，不能放在一起的连边。相邻顶点用不连边。相邻顶点用不同颜色着色。同颜色着色。这一问题就是图论中的顶点着色问题。这一问题就是图论中的顶点着色问题。例例3 最短路问题（最短路问题（SPPshortest path problem） 一名司机奉命在最短的时间内将一车货物从甲一名司机奉命在最短的时间内将一车货物从甲地运往乙地。从

5、甲地到乙地的公路网纵横交错，有地运往乙地。从甲地到乙地的公路网纵横交错，有多种行车路线，这名司机应选择哪条线路呢？假设多种行车路线，这名司机应选择哪条线路呢？假设车的运行速度是恒定的。车的运行速度是恒定的。 这一问题相当于找到一条从甲地到乙地的最短路。这一问题相当于找到一条从甲地到乙地的最短路。6v6v5v1v3v236511333v4甲地甲地乙地乙地 例例4 中国邮递员问题（中国邮递员问题（chinese postman problem） 一名邮递员负责投递某个街区的邮件。如何一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出为他（她）设计一条最短的投递路线（从

6、邮局出发，经过投递区内每条街道至少一次，最后返回发，经过投递区内每条街道至少一次，最后返回邮局）？邮局）？ 这一问题是我国管梅谷教授这一问题是我国管梅谷教授1960年首先提出年首先提出的，所以国际上称之为的，所以国际上称之为中国邮递员问题中国邮递员问题。 若将投递区的街道用边表示，街道的长度为边若将投递区的街道用边表示，街道的长度为边的权，邮局街道交叉口用点表示，则一个投递区构的权，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图中国邮递员问题转化为：成一个赋权连通无向图中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的在一个非负加权连通图中，寻求一个权最小的Euler回

7、路回路. 例例5 旅行商问题（旅行商问题（TSPtraveling salesman problem） 一名推销员准备前往若干城一名推销员准备前往若干城镇镇推销产品。如何推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城经过每个城镇镇恰好一次，最后返回驻地）？恰好一次，最后返回驻地）？ 这一问题的研究历史十分悠久，通常称之为旅这一问题的研究历史十分悠久，通常称之为旅行商问题。行商问题。 若用顶点表示城镇，边表示连接两城镇的路，若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是边上的权表示距离（或时间

8、、或费用），于是旅旅行商问题行商问题就成为在加权图中寻找一条经过每个顶就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题点至少一次的最短闭通路问题-Hamilton圈问题。圈问题。例例6 人员分派问题人员分派问题 某公司准备分派某公司准备分派n个工人个工人X1,X2,Xn做做n件工件工作作Y1,Y2,Yn，已知这些工人中每个人都能胜任，已知这些工人中每个人都能胜任一件或几件工作。试问能否把所有的工人都分派一件或几件工作。试问能否把所有的工人都分派做一件他所胜任的工作？做一件他所胜任的工作？ 构造一个具有二分类构造一个具有二分类(X,Y)的偶图的偶图G， 这里这里 X=x1,x2,xn

9、，Y=y1,y2,yn ，且，且xi与与yj相连当相连当且仅当工人且仅当工人Xi胜任工作胜任工作Yj.于是问题转化为于是问题转化为G是否是否存在完美匹配存在完美匹配的问题。的问题。y1x1y2x2x5y5x3x4y4y3例例7 最小费用最大流最小费用最大流 一批货物要从工厂运至车站，可以有多条线一批货物要从工厂运至车站，可以有多条线路进行选择，在不同的线路上每吨货物的运费不路进行选择，在不同的线路上每吨货物的运费不同，且每条线路的运输能力有限。怎样运输才能同，且每条线路的运输能力有限。怎样运输才能使费用最少使费用最少? 用结点用结点s代表工厂，代表工厂，t代表车站，线路为边，线代表车站，线路为

10、边，线路的交点为网络的结点，每条边都有两个权：容路的交点为网络的结点，每条边都有两个权：容量量c和单位费用和单位费用a，于是构成网络流图，于是构成网络流图N，问题变，问题变成求成求N的最小费用流。的最小费用流。过河问题：过河问题：摆渡人摆渡人Ferryman,狼狼wolf,羊羊sheep,卷卷心菜心菜cabbage过河问题过河问题 . 如何摆渡使得它们不能互如何摆渡使得它们不能互相伤害相伤害.考试安排问题：考试安排问题：学校期末考试安排学校期末考试安排n门课的考门课的考试时间时，不能把同一位学生选修的两门课安排在试时间时，不能把同一位学生选修的两门课安排在同一时间考试，问学校考试最少要进行多长

11、时间？同一时间考试，问学校考试最少要进行多长时间？信道分配问题信道分配问题：发射台所用频率从小到大编号：发射台所用频率从小到大编号为为1,2, 称为信道。用同一信道的两个台站相距得称为信道。用同一信道的两个台站相距得少于一个常数少于一个常数d，问各台至少需同时使用几个不同，问各台至少需同时使用几个不同的信道？的信道？指派问题（指派问题（assignment problem） 一家公司经理准备安排名员工去完成项任务，每一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配成同一

12、项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？工作方案可以使总回报最大？二、二、 图论的基本概念（略）图论的基本概念（略） 1. 图的概念图的概念V(G)中的中的元素称为图元素称为图G的的顶点顶点；E(G)是是V(G)中的中的无序无序中的元素称为中的元素称为边边.),(jivv|V(G)|：图的顶点数；图的顶点数； |E(G)|：图的边的数。图的边的数。表示边表示边jivv).,(jivv,)(21nvvvGV是非空有限集，称为是非空有限集，称为顶顶点集点集，或有序的元素对或有序的元素对).,(EVG )(),(GEGVG 表示图，表示图，简记简记 用用组成的集合，称为组成的

13、集合，称为边集边集, E(G)一个一个图图G 是指一个二元组是指一个二元组 (V(G), E(G)， 其中其中平凡图：平凡图：只有一个顶点的图。只有一个顶点的图。图：无向图，有向图和混合图。图：无向图，有向图和混合图。A B C De1e5e7e6e3e4e2V=A,B,C,D，E=e1,e2,e3,e4,e5,e6,e7 v3 v2v1 v0e1e2e3e4e5e6V=v1,v2,v3,v4，E=e1,e2,e3,e4,e5,e6无向图无向图有向图有向图孤立结点孤立结点:不与任何边关联的顶点不与任何边关联的顶点.零图零图:仅由一些孤立结点构成的图仅由一些孤立结点构成的图. 常用术语1) 边和

14、它的两端点称为互相边和它的两端点称为互相关联关联.2)与同一条边关联的两个端点称与同一条边关联的两个端点称为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点 点关联的两条边称为点关联的两条边称为相邻相邻的边的边. 3) 端点重合的边称为端点重合的边称为环环， 端点不相同的边称为端点不相同的边称为连杆连杆.4) 若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边 称为称为重边重边5) 既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 c a b d 常用术语6) 任意两顶点都相邻的简单图任意两顶点都相邻的简单图,称为完全图称为完全图. 记为

15、记为Kn. ， K5 K3 YXGV)(YX ， 则称则称为为二部图或偶图；二部图或偶图；若若X中每一顶点皆与中每一顶点皆与Y 中一切顶点相邻中一切顶点相邻,称为称为完全二部图完全二部图或或完全偶图完全偶图，记为记为 (m=|X|,n=|Y|)nmK,1x2x3x1y2y3y4y1x2x3x1y2y3y4y7) 若若且两个点集且两个点集X与与Y的内部的内部 任意两顶点不相邻，任意两顶点不相邻，4 , 3K2赋权图与子图赋权图与子图 定义 若图若图 的每一条边的每一条边e 都赋以都赋以)(),(GEGVG 一个实数一个实数w(e)，称，称w(e)为边为边e的的权权，G 连同边上的权连同边上的权称

16、为称为赋权图赋权图. 定义定义 设设 和和 是两个图是两个图.),(EVG ),(EVG 1) 若若 ,称称 是是 的一个的一个子图子图 EEVV,GG 2) 若若 ， ，则称，则称 是是 的的生成子图生成子图.VV EE GG 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 VV VV 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 VG 为为 的的由由 导出的子图导出的子图，记为，记为 .GVVG4) 若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点EE EEE 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由

17、 导出的导出的GGE 边导出的子图边导出的子图，记为，记为 . EG,321vvvG,6543eeeeG 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 VV VV 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 VG4) 若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点EE EEE 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的GGE 边导出的子图边导出的子图，记为，记为 . EGGVVG 为为 的的由由 导出的子图导出的子图，记为，记为 .3 图的矩阵表示图的矩阵表示 (1) 邻接矩阵邻接矩阵:

18、1) 对无向图对无向图 ，其邻接矩阵，其邻接矩阵 ，其中：，其中： G()ijn nAa., 0, 1不相邻与若相邻与若jijiijvvvva1234512345 0110010100110110010000100vvvvvvvAvvv(以下均假设图为简单图以下均假设图为简单图)2) 对有向图对有向图 ,其邻接矩阵其邻接矩阵 ,其中：其中： ()ijn nAa),(EVG .),(, 0,),(, 1EvvEvvajijiij若若0 1 000 0 100 0 001 1 10 43214321uuuuAuuuu(2)关联矩阵 1) 对无向图对无向图 ，其关联矩阵，其关联矩阵 ,),(EVG

19、mnijmM)(其中：其中：., 0, 1不关联与若相关联与若jijiijevevm 1 00000 10001 11100 01010 0 0 1 1 5432154321vvvvvMeeeee2) 对有向图对有向图 ，其关联矩阵，其关联矩阵 ,),(EVG mnijmM)(., 0, 1, 1的头与尾不是若的头是若的尾是若jijijiijevevevm其中：其中：11000101100001101101 432154321uuuuMeeeee4. 顶点的度顶点的度 定义定义 在无向图在无向图G中，与顶点中，与顶点v关联的边的数目关联的边的数目(环环算两次算两次),称为顶点称为顶点v的的度度

20、，记为，记为d(v). 在有向图中，从顶点在有向图中，从顶点v引出的边的数目称为顶点引出的边的数目称为顶点 v的的出度出度，记为，记为d+(v)，从顶点，从顶点v引入的边的数目称为引入的边的数目称为 v的的入度入度，记为，记为d -(v). 称称d(v)= d+(v)+d -(v)为顶点为顶点v的的 度度定理定理.2)(Vvvd推论推论 任何图中奇点的个数为偶数任何图中奇点的个数为偶数5. 路和连通路和连通 定义定义 无向图无向图G的一条的一条途径途径（或（或通道通道或或链链）是指）是指一个有限非空序列一个有限非空序列 ，它的项交替，它的项交替kkveevevW2110 地为顶点和边，使得对地

21、为顶点和边，使得对 ， 的端点是的端点是 和和 ,ki 1ie1iviv称称W是从是从 到到 的一条的一条途径途径，或一条，或一条 途径途径. 整整0vkv),(0kvv数数k称为称为W的的长长. 顶点顶点 和和 分别称为的分别称为的起点起点和和终点终点 ,0vkv而而 称为称为W的的内部顶点内部顶点.121,kvvv 若途径若途径W的边互不相同但顶点可重复，则称的边互不相同但顶点可重复，则称W为为迹迹或或简单链简单链. 若途径若途径W的顶点和边均互不相同，则称的顶点和边均互不相同，则称W为为路路或或路径路径. 一条起点为一条起点为 ,终点为终点为 的路称为的路称为 路路0vkv),(0kvv

22、记为记为).,(0kvvP起点与终点重合的途径称为起点与终点重合的途径称为闭途径闭途径.起点与终点重合的的路称为起点与终点重合的的路称为圈圈(或或回路回路)，长，长为为k的圈称为的圈称为k阶圈阶圈，记为，记为Ck.若在图若在图G中存在中存在(u,v)路，则称顶点路，则称顶点u和和v在图在图G中中连通连通.图图G中任意两点皆连通的图称为中任意两点皆连通的图称为连通图连通图 例例 在右图中：在右图中： 途径或链：途径或链： 迹或简单链：迹或简单链： 路或路径：路或路径： 圈或回路：圈或回路：wugyexeyfxcyvbwcxdvauguavdxcwuuavbwcxfyg三、最短路问题及算法三、最短

23、路问题及算法 最短路问题是图论应用的基本问题，很多实际最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费问题，如线路的布设、运输安排、运输网络最小费用流等问题用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解.最短路问题的两种方法：最短路问题的两种方法：Dijkstra和和Floyd算法算法 .1) 求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路. .2) 求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路.在赋权图在赋权图G中，从顶点中，从顶点u到顶点到顶点v的具有最小权的路的具有最小权的路称为路称为

24、路 P(u,v)的的权权若若P(u,v)是赋权图是赋权图G中从中从u到到v的路的路,称称)()()(PEeewPwP*(u,v)，称为，称为u到到v的的最短路最短路把赋权图中一条路的权称为它的把赋权图中一条路的权称为它的长长，把，把(u,v)路的路的最小权称为最小权称为u和和v之间的之间的距离距离，并记作，并记作 d(u,v). 在赋权图中找出指定两点之间的最短路的问题称之在赋权图中找出指定两点之间的最短路的问题称之为为最短路问题。最短路问题。赋权图中求给定点到各顶点的最短路的算法赋权图中求给定点到各顶点的最短路的算法(Dijkstra算法，算法，1959年年）令图令图G=, 集合集合Si V

25、 ,Si =V-Si , 令令|V|=n Si=u|从从u0到到u的最短路已求出的最短路已求出 Si =u |从从u0到到u 的最短路未求出的最短路未求出基本思想基本思想: 若使若使 (u0,u1,u2,un-1,un)最短最短, 就要使就要使(u0,u1,u2,un-1)最短最短, 即保证从即保证从u0到以后各点的到以后各点的路都是最短的路都是最短的.Dijkstra算法算法:(求从求从u0到各点到各点u的最短路长的最短路长)第一步第一步. 置初值置初值: d(u0,u0)=0 d(u0,v)= (其中其中v u0) i=0 S0=u0 S0 =V-S0 , 第二步第二步.若若 i=n-1

26、则停则停. 否则转第三步否则转第三步第三步第三步. 对每个对每个u Si 计算计算 d(u0,u )=mind(u0,u ), d(u0,ui)+c(ui,u ) ui Siu Si 计算计算 mind(u0,u )并用并用ui+1记下达到该最小值的那个结点记下达到该最小值的那个结点u ,置置Si+1 =Siui+1, i=i+1 Si =V-Si , 转第二步转第二步.例例.求右图中从求右图中从v1到到v6的最的最短路。短路。d(u0,v2)=3, 路路u0v2d(u0,v4)=4, 路路u0v2v4d(u0,v5)=5, 路路u0v2v4v5d(u0,v3)=7, 路路 u0v2v4 v3

27、d(u0,v6)=10, 路路u0v2v4v3v66v6v5v1v3v236511333v4实例实例1 一个多阶段存储问题一个多阶段存储问题 某商场欲编制某商品未来某商场欲编制某商品未来n个月的进货计划。假设个月的进货计划。假设每月月初进货，当月不需附加存储费，若一个月每月月初进货，当月不需附加存储费，若一个月后销售则需加存储费。设每月需求量、进货单价后销售则需加存储费。设每月需求量、进货单价和存储单价如下表：和存储单价如下表：月月1 2 n需求量需求量 b1 b2 bn单价单价c1 c2 cn存储月份存储月份 12 23 n-1n存储单价存储单价 d1 d2 dn-1确定一个进货与存储的合理

28、水平使总费用最少。确定一个进货与存储的合理水平使总费用最少。 分析分析 ： 第第k月的需要量可在第月的需要量可在第1月，第月，第2月，月，第第k月的任何一个月进货，分别计算费用如下：月的任何一个月进货，分别计算费用如下： 第第1月进货总费用：月进货总费用：a1=bk(c1+d1+ +dk-1) 第第2月进货总费用：月进货总费用：a2=bk(c2+d2+ +dk-1) 第第k月进货总费用：月进货总费用：ak=bkdk 比较比较a1,a2, ,ak的大小即可确定哪一个月进货总费的大小即可确定哪一个月进货总费用更省。用更省。在确定借贷与存储的合理水平时，仅考虑一个单在确定借贷与存储的合理水平时，仅考

29、虑一个单位货物，而不考虑进货量。位货物，而不考虑进货量。模拟图模拟图：以顶点：以顶点vi表示第表示第i月，月，i=1,2,n,连结点连结点vi,vi+1,得得边边vivi+1，给边，给边vivi+1赋权赋权di，i=1,2, ，n-1；附加顶点；附加顶点v0，连结顶点连结顶点v0,vi，得边，得边 v0vi, 给边给边 v0vi 赋权赋权 ci，i=1,2, ,n，得到得到n+1个顶点的赋权有向图，如下：个顶点的赋权有向图，如下：v0v3v2cnv1vn-1vnc1dn-1d2d1c2c3cn-1问题：问题：将边的权理解为距离，费用最小就是求距离最将边的权理解为距离，费用最小就是求距离最短。因

30、此只要求出短。因此只要求出顶点顶点v0到其余各点的最短路，到其余各点的最短路，即可即可确定每个月的需要量该由哪个月进货最好，从而制定确定每个月的需要量该由哪个月进货最好，从而制定出总费用最少的出总费用最少的n个月的进货与存储计划。个月的进货与存储计划。设备更新问题：企业使用一台设备，每年年初，企业领导设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的就要确定是购置新的，还是继续使用旧的.若购置新设备，若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的就要支付一定的购置费用；若继续使用，则需支付一定的维修费用维修费用.现要制定一个五年之内的设备更

31、新计划，使得五现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少年内总的支付费用最少.该种设备在每年年初的价格该种设备在每年年初的价格(万元万元)为：为： 使用不同时间设备所需维修费使用不同时间设备所需维修费(万元万元)为：为：第一年第一年第二年第二年第三年第三年第四年第四年第五年第五年1111121213使用年限使用年限0-11-22-33-44-5维修费维修费5681118实例实例2 多阶段决策问题多阶段决策问题构造加权有向图构造加权有向图G (V,E)bX1bX2)1(2rXbX3bX5bX4)1(5rX)1(4rX)1(3rX)2(3rX)2(4rX)3(4rX)2(5rX

32、)3(5rX)4(5rX)1(6rX)2(6rX)3(6rX)4(6rX)5(6rX弧弧(Xi,Xj)的权的权W (Xi,Xj)代表第代表第i年初到第年初到第i+1年年初之间的费用初之间的费用.512),()1(43rbXXW四、最小生成树及算法四、最小生成树及算法1v 连通且不含圈的无向图称为连通且不含圈的无向图称为树树常用常用T表示表示. 树中的边称为树中的边称为树枝树枝. 树中度为树中度为1的顶点称为的顶点称为树叶树叶.2v3v4v5v1. 树的定义树的定义2. 树的等价定义树的等价定义1)1)G是树（是树（ G无圈且连通）；无圈且连通）；2) G无圈，且有无圈，且有n-1条边；条边；3

33、) G连通，且有连通，且有n-1条边；条边；4) G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈; 5) G连通，且删去一条边就不连通了（即连通，且删去一条边就不连通了（即G为为最最最小连通图最小连通图）；）；6) G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.设设G是具有是具有n个顶点的图，则下述命题等价个顶点的图，则下述命题等价3. 生成树生成树定义定义 若若T是包含图是包含图G的全部顶点的子图的全部顶点的子图,它又是树它又是树,则称则称T是是G的的生成树生成树. 图图G中不在生成树的边叫做中不在生成树的边叫做弦弦.图图G=(V,E)有生成树的充要条件

34、是图有生成树的充要条件是图G是连通的是连通的.找生成树的方法找生成树的方法：避圈法和破圈法：避圈法和破圈法. 4. 4. 赋权图的最小生成树赋权图的最小生成树 一棵生成树中的所有边的权之和称为该一棵生成树中的所有边的权之和称为该生成树生成树的权的权. 具有最小权的生成树具有最小权的生成树,称为称为最小生成树最小生成树. 最小生成树很有实际应用价值最小生成树很有实际应用价值. 例如例如 顶点是城市顶点是城市,边的权表示两个城市间的距离边的权表示两个城市间的距离从一个城市出发走遍各个城市从一个城市出发走遍各个城市,如何选择最优的旅如何选择最优的旅行路线行路线. 城市间的通信网络问题城市间的通信网络

35、问题,如何布线如何布线,使得总的线路使得总的线路长度最短长度最短. 求最小生成树一般有两种方法：求最小生成树一般有两种方法： Kruskal算法（算法（或或避圈法避圈法）和）和破圈法破圈法. A. Kruskal算法（或避圈法）算法（或避圈法）步骤如下：步骤如下： (1) 选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；(2) 若已选定边若已选定边 ，则从，则从ieee,.,21,.,21ieeeE中选取中选取 ，使得，使得:1iei) 为无圈图，为无圈图，,.,121ieeeG ii) 是满足是满足i)的尽可能小的权，的尽可能小的权，)(1iew (3) 当第当第(2)步不能继续执

36、行时，则停止步不能继续执行时，则停止.B. 破圈法破圈法算法算法2 步骤如下：步骤如下： (1) 从图从图G中任选一棵树中任选一棵树T1.(2) 加上一条弦加上一条弦e1，T1+e1中中生成一个圈生成一个圈. 去掉此圈中最大权边，得到新树去掉此圈中最大权边，得到新树T2,以以T2代代T1,重复重复(2)再检查剩余的弦，直到全部弦再检查剩余的弦，直到全部弦检查完毕为止检查完毕为止.例例 n个城市个城市,各城市之间的距离如下表各城市之间的距离如下表(距离为距离为，表示两个城市之间没有直接到达的线路，表示两个城市之间没有直接到达的线路)。从一个城市出发走遍各个城市从一个城市出发走遍各个城市,如何选择

37、最优的如何选择最优的旅行路线旅行路线.07428702312015231036530437465062404812740城市作为顶点，两个城市之间有直达的线路，则连边，城市作为顶点，两个城市之间有直达的线路，则连边，且给边赋权距离，得一个赋权图。且给边赋权距离，得一个赋权图。v1 v5 v4v2 v3v8 v6v7 1212433v1 v5 v4v2 v3v8 v6v712213772486653443 问题就是求一棵最问题就是求一棵最小生成树。小生成树。五、五、 旅行售货员问题旅行售货员问题 一个旅行售货员想去访问若干城镇，然后回一个旅行售货员想去访问若干城镇，然后回到出发地到出发地.给定各

38、城镇之间的距离后，应怎样计划给定各城镇之间的距离后，应怎样计划旅行路线，使他能对每个城镇恰好经过一次而总旅行路线，使他能对每个城镇恰好经过一次而总距离最小？距离最小？ 它可归结为这样的它可归结为这样的图论问题：图论问题：在一个赋权完在一个赋权完全图中全图中,找出一个找出一个最小权的最小权的H圈圈. 但这个问题是但这个问题是NP-hard问题，即不存在多项式问题，即不存在多项式时间算法时间算法.也就是说也就是说,对于大型网络对于大型网络(赋权图赋权图),目前还目前还没有一个求解旅行售货员问题的有效算法，因此没有一个求解旅行售货员问题的有效算法，因此只能找一种求出相当好（不一定最优）的解只能找一种

39、求出相当好（不一定最优）的解. 定义定义设设G=(V,E)是连通无向图，包含图是连通无向图，包含图G的每个的每个顶点的路顶点的路称为称为G的的哈密尔顿哈密尔顿路路(Hamilton路或路或H路路). 包含图包含图G的每个顶点的圈，称为的每个顶点的圈，称为G的的哈密尔顿圈哈密尔顿圈(或或Hamilton圈或圈或H圈圈). 含含Hamilton圈的图称圈的图称为哈密尔顿图。为哈密尔顿图。9898年全国大学生数学建模竞赛年全国大学生数学建模竞赛B B题题 今年今年(1998年年)夏天某县遭受水灾夏天某县遭受水灾. 为考察灾情、为考察灾情、组织自救，县领导决定，带领有关部门负责人到组织自救，县领导决定

40、，带领有关部门负责人到全县各乡（镇）、村巡视全县各乡（镇）、村巡视. 巡视路线指从县政府巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线府所在地的路线.“最佳灾最佳灾情巡视路线情巡视路线” 1）若分三组（路）巡视，试设计总路程最）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线短且各组尽可能均衡的巡视路线. 2）假定巡视人员在各乡（镇）停留时间）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间小时，在各村停留时间t=1小时，汽车行驶速度小时，汽车行驶速度V=35公里公里/小时小时. 要在要在24小时内完

41、成巡视，至少应分小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线几组；给出这种分组下最佳的巡视路线.一个可行的方法一个可行的方法 : 先求一个先求一个H圈圈,再适当修改再适当修改,得到具有较小权的另一得到具有较小权的另一H圈圈.定义 若对于某一对若对于某一对i和和j，有，有)()()()(1111jjiijijivvwvvwvvwvvw则圈则圈Cij将是圈将是圈C的一个的一个改进改进. 在进行一系列改进之后在进行一系列改进之后, 最后得一个圈最后得一个圈,不能再不能再用此方法改进了，这个最后的圈可能不是最优的用此方法改进了，这个最后的圈可能不是最优的,但是它是比较好的，为了得到更高的

42、精度，这个但是它是比较好的，为了得到更高的精度，这个过程可以重复几次，每次以不同的圈开始过程可以重复几次，每次以不同的圈开始. 这种方这种方法叫做法叫做二边逐次修正法二边逐次修正法.例例 对下图的对下图的K6, ,用二边逐次修正法求较优用二边逐次修正法求较优H圈圈. .较优较优H圈圈:其权为其权为W(C3)=19213265413vvvvvvvC 六、网络与网络流六、网络与网络流 1. 网络流的基本概念网络流的基本概念 先来看一个实例。先来看一个实例。 现在现在想将一些物资从想将一些物资从S运抵运抵T，必须经过一些，必须经过一些中转站。连接中转站的是公路，每条公路都有最中转站。连接中转站的是公

43、路，每条公路都有最大运载量。大运载量。 每条弧代表一条公路，弧上的数表示该公路的每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从最大运载量。最多能将多少货物从S运抵运抵T？ 定义定义6.1 若有向图满足下列条件：若有向图满足下列条件： (1) 有且仅有一个入度为零的顶点有且仅有一个入度为零的顶点s，称为，称为源点源点； (2) 有且仅有一个出度为零的顶点有且仅有一个出度为零的顶点t，称为，称为汇点汇点; (3) 每一条弧每一条弧(vi, vj)都有一个非负数都有一个非负数cij ，称为该，称为该边的容量。如果边的容量。如果vi,vj之间没有边，之间没有边，cij =0。

44、则称该有向图为则称该有向图为网络网络，记为，记为N = (V, E, C). 图图6.1所给出的一个赋权有向图所给出的一个赋权有向图N就是一个网络，就是一个网络，指定指定v1是源点，是源点，v4为汇点，弧旁的数字为为汇点，弧旁的数字为cij。图图6.1图图6.2网络流：是定义在弧集合网络流：是定义在弧集合E上一个函数上一个函数f=f(vi,vj)，并称并称f(vi,vj)为弧为弧(vi,vj)上的流量上的流量(简记为简记为fij)。如图。如图6.2所所示的网络示的网络N，弧上两个数，第一个数表示容量，弧上两个数，第一个数表示容量cij，第二个数表示流量第二个数表示流量 fij。 2.可行流与最

45、大流可行流与最大流 (1) 定义定义 在实际问题中，对于流有两个显然的要求：一是在实际问题中，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力每个弧上的流量不能超过该弧的最大通过能力(即弧即弧的容量的容量)；二是中间点的流量为；二是中间点的流量为0，源点的净流出，源点的净流出量量和汇点的净流入量必相等。因此有定义如下。和汇点的净流入量必相等。因此有定义如下。 定义定义6.2 网络网络N = (V, E, C)中如果每条边都给定一中如果每条边都给定一个非负实数个非负实数fij满足下列条件满足下列条件 (1)容量约束容量约束：0fijcij，(vi,vj)E， (2)守恒条件守

46、恒条件 对于中间点：流入量对于中间点：流入量=流出量，即流出量，即sjjtjjffw 对于源点与汇对于源点与汇 点：点：源点的净流出量源点的净流出量=汇点的净汇点的净流入量，即流入量，即, ,ijjijjffis t那么这一那么这一组组fij称为网络称为网络N上的上的可行流可行流，w称为称为流量流量. 网络网络N中流值最大的流中流值最大的流f*称为称为N的的最大流最大流.(2) 可增广可增广(流流)路径路径 可增广路径可增广路径，是指这条路径上的流可以修改，通，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。过修改，使得整个网络的流值增大。定义定义6.3 设设f是一个是一个可行流

47、可行流，P是从源点是从源点s到汇点到汇点t的的一条路，若一条路，若P满足下列条件：满足下列条件： (1)在在P上的所有前向弧上的所有前向弧(vivj)都是非饱和弧，即都是非饱和弧，即0fijcij； (2)在在P上的所有后向弧上的所有后向弧(vivj)都是非零弧，即都是非零弧，即0fijcij。则称。则称P为为(关于可行流关于可行流f的的)一条一条可增广路可增广路径。径。(3) 割及其容量割及其容量定义定义6.4 如果如果S是是V的一个子集，的一个子集，SVS,sS tS ，则称边集，则称边集 为网络为网络N的一个的一个割。显然，若把某一割的弧从网络中去掉，则割。显然，若把某一割的弧从网络中去

48、掉，则从从s到到t就不存在路。所以直观上讲，割是从就不存在路。所以直观上讲，割是从s到到t的必经之道。的必经之道。( ,)S S定义定义5 给一割给一割( ,)c S S，把其中所有弧的容量，把其中所有弧的容量之和称为这个之和称为这个割的容量割的容量，记为，记为( ,)S S，即，即( ,)( )e Ec S Sc e 网络网络N中容量最小的割中容量最小的割*(,)SS称为称为N的的最小割最小割。 不难证明，任何一个可行流的流量不难证明，任何一个可行流的流量w都不会超过都不会超过任一割的容量，即任一割的容量，即( ,)wc S S 例如，图例如，图6.2中，若中，若32 ,( ,)( ,),(

49、 ,)SsS Ss vs v( ,)437.c S S 定理定理1 网络的网络的最大流量不超过最小的割的容量最大流量不超过最小的割的容量，即，即maxmin ( ,)wc S S 证明证明 设设f是给定网络的任意可行流，由可行流的性质是给定网络的任意可行流，由可行流的性质sjjfw ()0. , ,ijjijffis t jV ,(). ijjii S j Vffw 任给一个割任给一个割( ,)S S,()(). ijjiijjii S j Si S j Sffffw即即,()0, ijjii S j Sff 所以所以,(). ijjii S j Sffw 因因由于由于0, ijijijjii

50、jfcfff所以所以,() ( ,) ijjiijiji S j Si S j Si S j Swfffcc S S由于可行流和割的任意性，定理成立。由于可行流和割的任意性，定理成立。 如果网络的可行流不是最大流，就一定存在从如果网络的可行流不是最大流，就一定存在从s到到t的的可增流路径可增流路径。 令令s,v1,v2,vk,t是一条是一条s到到t的路径的路径Pst，其中每条，其中每条边的方向都是边的方向都是vj到到vj+1,称为称为向前边向前边。如果这条路径。如果这条路径上每条边上每条边eij都有都有fijcij，那么令，那么令min()ijstijijePcf 令令Pst每条边的流都增加每