数学建模图论学习教案

1、会计学1数学数学(shxu)建模图论建模图论第一页，共66页。都越来越广泛地使用了图论模型方法。第1页/共66页第二页，共66页。问题问题(wnt)的提出的提出哥尼斯堡七桥问题 七桥问题是发生在18世纪东普鲁土的哥尼斯堡的一个真实故事。ABCD第2页/共66页第三页，共66页。ABCD1735年,有大学生写信把问题告诉了欧拉,请他帮助解决(jiju)。欧拉从大家的失败中进行抽象的数学思考,从数学角度成功地解决(jiju)了问题。 第3页/共66页第四页，共66页。2.四块陆地可重复(chngf)经历,至于陆地的大小、形状、质地等也与问题的本质无关，因而可视四块陆地为四个点A、B、C、D。1.问

2、题的本质是能否从一地无重复地一次走遍七桥,因而与所走过的桥的大小、形状、长短、曲直(qzh)等均无关，而只要桥存在，因此不妨将其视为一条弧线ABCDABDC第4页/共66页第五页，共66页。 这样一来，能否从一地出发(chf)走遍七座桥一次且仅一次再回到出发(chf)点就变成了：能否从这个图上任一顶点出发(chf)，经过每条边一次且仅一次而回到出发(chf)顶点。这就是众所周知的这个图能否“一笔画出”的问题。 ABCDABDC第5页/共66页第六页，共66页。7“一笔画(bhu)出”能否从这个(zh ge)图上任一顶点出发，经过每个顶点一次且仅一次而回到出发顶点。旅行商问题旅行商问题能否从这个

3、图选择尽量少的点，使得所有的其余点都和该点集有路径连接。覆盖问题覆盖问题-系统监控模型系统监控模型能否将图中点集分类，使得每一类点集都没有路径连接，最少需要分几类。支配集支配集-仓库分区仓库分区第6页/共66页第七页，共66页。8“点着(din zhe)色将该图中所有边用不同颜色表示，最少需要(xyo)几种颜色。边着色边着色关键路径关键路径最大流、最小流最大流、最小流第7页/共66页第八页，共66页。问题问题2(2(哈密顿环球旅行问题哈密顿环球旅行问题):): 十二面体的十二面体的2020个顶点代表世界个顶点代表世界(shji)(shji)上上2020个城市，能否从某个城市出发在十二面体上依个

4、城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？次经过每个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）第8页/共66页第九页，共66页。问题问题(wnt)3(wnt)3(四色问题四色问题(wnt):(wnt): 对任何一张地图进行着色，两个共同边界对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了的国家染不同的颜色，则只需要四种颜色就够了. .第9页/共66页第十页，共66页。问题问题4(4(关键路径问题关键路径问题):): 一项工程任务一项工程任务, ,大到建造一座大坝大到建造一座大坝, ,一座体育中一座体育中心心, ,小至组装

5、一台机床小至组装一台机床, ,一架电视机一架电视机, , 都要包括许多都要包括许多工序工序. .这些工序相互约束这些工序相互约束, ,只有在某些只有在某些(mu xi)(mu xi)工序工序完成之后完成之后, , 一个工序才能开始一个工序才能开始. . 即它们之间存在完即它们之间存在完成的先后次序关系成的先后次序关系, ,一般认为这些关系是预知的一般认为这些关系是预知的, , 而而且也能够预计完成每个工序所需要的时间且也能够预计完成每个工序所需要的时间. . 这时工程领导人员迫切希望了解最少需要多少这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目时间才能够完成整个工程项目,

6、, 影响工程进度的要影响工程进度的要害工序是哪几个？害工序是哪几个？ 第10页/共66页第十一页，共66页。图的基本概念图的基本概念最短路最短路(dunl)问题问题及其算法及其算法最小生成最小生成(shn chn)树问题树问题图的矩阵图的矩阵(j zhn)表示表示第11页/共66页第十二页，共66页。 数学数学(shxu)建模建模-图论图论132022年年4月月19日日 一、图的基本概念一、图的基本概念第12页/共66页第十三页，共66页。 数学数学(shxu)建模建模-图论图论142022年年4月月19日日 一、图的基本概念一、图的基本概念图图1 1图图2 2第13页/共66页第十四页，共6

7、6页。 数学数学(shxu)建模建模-图论图论152022年年4月月19日日 一、图的基本概念一、图的基本概念 一个图会有许多外形不同的图解, 下面两个(lin )图表示同一个图G = (V, E )的图解.其中 V = v1 , v2 , v3 , v4,E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4. 第14页/共66页第十五页，共66页。 数学数学(shxu)建模建模-图论图论162022年年4月月19日日 一、图的基本概念一、图的基本概念第15页/共66页第十六页，共66页。 数学数学(shxu)建模建模-图论图论172022年年4月月19日日

8、一、图的基本概念一、图的基本概念次数为奇数次数为奇数(j sh)顶点称为奇点，否则称为偶点。顶点称为奇点，否则称为偶点。第16页/共66页第十七页，共66页。 数学数学(shxu)建模建模-图论图论182022年年4月月19日日 一、图的基本概念一、图的基本概念常用常用(chn(chn yn yn)d(v)d(v)表示图表示图G G 中与顶点中与顶点v v关联的边的数目关联的边的数目, , d(v)d(v)称为顶点称为顶点v v的度数的度数. .与顶点与顶点v v出关联的边的数目称为出度，记作出关联的边的数目称为出度，记作d +(v)d +(v)，与顶点与顶点v v入关联的边的数目称为入度，记

9、作入关联的边的数目称为入度，记作d -(v)d -(v)。用用N(v)N(v)表示图表示图G G 中所有与顶点中所有与顶点(dngdin)v(dngdin)v相邻的顶点相邻的顶点(dngdin)(dngdin)的集合的集合. . 任意两顶点都相邻的简单图称为任意两顶点都相邻的简单图称为完全图完全图. .有有n n个顶点的完全图记为个顶点的完全图记为K Kn n 。第17页/共66页第十八页，共66页。 数学数学(shxu)建模建模-图论图论192022年年4月月19日日 一、图的基本概念一、图的基本概念几个基本几个基本(jbn)定理：定理： .21EvdEVGVv，有，、对图数个。、度为奇数的

10、顶点有偶2 . 3EvdvdEVGVvVv则是有向图，、设第18页/共66页第十九页，共66页。 若将图若将图G G的每一条边的每一条边e e都对应一个实数都对应一个实数(shsh)F(e), (shsh)F(e), 则称则称F(e)F(e)为该边的权为该边的权, , 并称图并称图G G为赋权图为赋权图, , 记为记为G = (V, E , F ). G = (V, E , F ). 设设G = (V, E )G = (V, E )是一个图是一个图, v0, v1, , vkV, , v0, v1, , vkV, 且且“1ik, vi“1ik, vi1 viE, 1 viE, 则称则称v0 v

11、1 vkv0 v1 vk是是G G的一条的一条(y tio)(y tio)通路通路. . 如果通路中没有如果通路中没有(mi yu)相同的顶点相同的顶点, 则称此通路为路则称此通路为路径径, 简称路简称路. 始点和终点相同的路称为始点和终点相同的路称为圈圈或或回路回路. . 一、图的基本概念一、图的基本概念 第19页/共66页第二十页，共66页。 顶点顶点u u与与v v称为连通的，如果存在称为连通的，如果存在u u到到v v通路，任二顶点通路，任二顶点都连通的图称为连通图，否则都连通的图称为连通图，否则(fuz)(fuz)，称为非连通图，称为非连通图。极大连通子图称为连通分图。极大连通子图称

12、为连通分图。 连通(lintng)而无圈的图称为树, 常用T 表示树. 树中最长路的边数称为树中最长路的边数称为(chn(chn wi) wi)树的高，度树的高，度数为数为1 1的顶点称为的顶点称为(chn(chn wi) wi)树叶。其余的顶点称树叶。其余的顶点称为为(chn(chn wi) wi)分枝点。树的边称为分枝点。树的边称为(chn(chn wi) wi)树枝。树枝。 设设G G是有向图，如果是有向图，如果G G的底图是树，则称的底图是树，则称G G是是有向树有向树，也简称，也简称树树。 一、图的基本概念一、图的基本概念 第20页/共66页第二十一页，共66页。 一、图的基本概念一

13、、图的基本概念(应用应用(yngyng) 数学数学(shxu)建模建模-图论图论用图论思想用图论思想(sxing)求解以下各题求解以下各题例例1、一摆渡人欲将一只狼，一头羊，一篮菜从、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。河方法。第21页/共66页第二十二页，共66页。 一、图的基本概念一、图的基本概念(应用应用(yngyng) 数学数学(shxu)建模建模-图论图论解：解：用四维用四维0-1向量表示（人，狼，羊，菜）的在

14、西岸向量表示（人，狼，羊，菜）的在西岸状态状态(zhungti)，（在西岸则分量取，（在西岸则分量取1，否则取，否则取0.）共共24=16种状态，种状态，由题设，状态（由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不是不允许的，允许的，从而对应状态（从而对应状态（1,0,0,1），），(1,1,0,0),(1,0,0,0)也是也是不允许的，不允许的，第22页/共66页第二十三页，共66页。 一、图的基本概念一、图的基本概念(应用应用(yngyng) 数学数学(shxu)建模建模-图论图论人在河西(h x)：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0

15、,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1） （0,0,0,0）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。第23页/共66页第二十四页，共66页。 一、图的基本概念一、图的基本概念(应用应用(yngyng) 数学数学(shxu)建模建模-图论图论例例2、考虑中国象棋的如下问题：、考虑中国象棋的如下问题：（1）下过奇数盘棋的人数）下过奇数盘棋

16、的人数(rn sh)是偶数个。是偶数个。（2）马有多少种跳法？）马有多少种跳法？（3）马跳出后又跳回起点，证明马跳了偶数步。）马跳出后又跳回起点，证明马跳了偶数步。（4）红方的马能不能在自己一方的棋盘上不重复）红方的马能不能在自己一方的棋盘上不重复的跳遍每一点，最后跳回起点？的跳遍每一点，最后跳回起点？第24页/共66页第二十五页，共66页。 一、图的基本概念一、图的基本概念(应用应用(yngyng) 数学数学(shxu)建模建模-图论图论例例3、证明：在任意、证明：在任意(rny)6人的集会上，总有人的集会上，总有3人互相认人互相认识，或总有识，或总有3人互相不认识。人互相不认识。解：以顶点

17、表示人，以边表示认识，得解：以顶点表示人，以边表示认识，得6个顶点个顶点的简单图的简单图G。问题：问题：3人互相认识即人互相认识即G包含包含K3为子图，为子图， 3人互相不认识即人互相不认识即G包含（包含（3,0）图为子图。）图为子图。第25页/共66页第二十六页，共66页。 一、图的基本概念一、图的基本概念(应用应用(yngyng) 数学数学(shxu)建模建模-图论图论 为子图。包含点不相邻，则点至少、这图为子图。包含点两两相邻，则、这。这又包含两种情况：点不相邻个顶即至少与另外个顶点相邻至多与另外）（为子图。包含点相邻，则点至少、这图为子图。包含点互不相邻，则、这两种情况：个顶点相邻，这

18、又包含至少与另外则有两种情况：任取0 , 3232 31 )3(22232 0 , 331 3 1 ,33GKGvKGGvGVv第26页/共66页第二十七页，共66页。282022年年4月月19日日一、图的基本概念一、图的基本概念(应用应用(yngyng) 数学数学(shxu)建模建模-图论图论（设备更新问题）某企业每年年初（设备更新问题）某企业每年年初, ,都要作出决定都要作出决定, ,如果继续如果继续(jx)(jx)使用旧设备使用旧设备, ,要付维修费；若购买要付维修费；若购买一台新设备一台新设备, ,要付购买费要付购买费. .试制定一个试制定一个5 5年更新计划年更新计划, ,使总支出最

19、少使总支出最少. . 已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11, 11,11, 12,12,13. 12,12,13. 使用不同时间设备所需的维修费分别为使用不同时间设备所需的维修费分别为5,6,8,11,18.5,6,8,11,18.第27页/共66页第二十八页，共66页。292022年年4月月19日日ijkkijicbvvF1)(求求v1v1到到v6v6的最短路的最短路(dunl)(dunl)问问题题. . 一、图的基本概念一、图的基本概念( (应用应用(yngyng)(yngyng)4 11411()11 568kkF vvbc 数学数学(shxu)建模

20、建模-图论图论第28页/共66页第二十九页，共66页。302022年年4月月19日日从上图中容易从上图中容易(rngy)(rngy)得到得到v1v1到到v6v6只有两条路：只有两条路：v v1 1v v3 3v v6 6和和v v1 1v v4 4v v6 6. . 而这两条路都是而这两条路都是v1v1到到v6v6的最短路的最短路(dunl).(dunl).一、图的基本概念一、图的基本概念(应用应用(yngyng) 第29页/共66页第三十页，共66页。邻接矩阵（结点与结点的关系）邻接矩阵（结点与结点的关系）关联矩阵（结点与边的关系）关联矩阵（结点与边的关系）路径矩阵（任意路径矩阵（任意(rn

21、y)(rny)两结点之间是否有路径）两结点之间是否有路径）可达性矩阵可达性矩阵直达矩阵直达矩阵 等等等等二、图的矩阵二、图的矩阵(j zhn)表示表示 数学数学(shxu)建模建模-图论图论第30页/共66页第三十一页，共66页。1 1 有向图的邻接矩阵有向图的邻接矩阵 A = (aij )n A = (aij )nn n （n n为结点为结点(ji din)(ji din)数）数）EvvEvvajijiij, 0, 1 例例1 1：写出右图的邻接矩阵：写出右图的邻接矩阵：0101100101001010A解：二、图的矩阵二、图的矩阵(j zhn)表示表示 数学数学(shxu)建模建模-图论图

22、论第31页/共66页第三十二页，共66页。2 2 有向图的权矩阵有向图的权矩阵(j zhn)A = (aij ) n(j zhn)A = (aij ) nn n （n n为结点数为结点数） EvvjiEvvvvFajijijiij , , 0 ,例2：写出右图的权矩阵(j zhn)：05420370860A解：二、图的矩阵二、图的矩阵(j zhn)表示表示 第32页/共66页第三十三页，共66页。3 有向图的关联矩阵有向图的关联矩阵A =(aij )nm （n为结点为结点(ji din)数数m为边数）为边数） 不关联与若的终点是若的始点是若iiiiiiijeveveva, 0, 1, 1有向图

23、：有向图： 无向无向(w xin)图：图：不关联与若关联与若jijiijvvvva, 0 , 1 二、图的矩阵二、图的矩阵(j zhn)表示表示 第33页/共66页第三十四页，共66页。例例3 3：分别：分别(fnbi)(fnbi)写出右边两图的写出右边两图的关联矩阵关联矩阵解：分别(fnbi)为：1101100011011000000111011001A 二、图的矩阵二、图的矩阵(j zhn)表示表示eabcd1e2e3e4e5e0001101001111000011010000A 第34页/共66页第三十五页，共66页。4 4 应用应用(yngyng)(yngyng)实例实例 数学数学(s

24、hxu)建模建模-图论图论某航空公司在A,B,C,D四城市之间开辟了若干航线,如图所示表示了四城市间的航班图,如果从A到B有航班,则用带箭头的线连接A与B.问题:如何直观给出各个城市之间的航班情况问题:如果没有直接航班到达,需要转机,有几种转机方案问题:如果城市不止4个,有n个城市,能否快速给出直接路径以及需要转机方案.问题:过年回家火车路线如何设置，北京公交地铁倒车如何如何设置百度地图第35页/共66页第三十六页，共66页。 数学数学(shxu)建模建模-图论图论00101001010101100010100101010110MM0010100101010110MABCD.20111 111

25、02101010数值表示(biosh)两地之间航线的数目，1表示(biosh)只有一条路径，2代表有两条路径第36页/共66页第三十七页，共66页。 若将图若将图G G 的每一条边的每一条边e e都对应一个实数都对应一个实数(shsh)F(e), (shsh)F(e), 则称则称F(e)F(e)为该边的权为该边的权, , 并称图并称图G G为赋权图为赋权图, , 记为记为G = (V, E , F ). G = (V, E , F ). 设设G = (V, E )G = (V, E )是一个是一个(y (y )图图, v0, v1, , , v0, v1, , vkV, vkV, 且且“1ik

26、, vi“1ik, vi1 viE, 1 viE, 则称则称v0 v1 vkv0 v1 vk是是G G的一条通路的一条通路. .如果通路中没有相同的顶点如果通路中没有相同的顶点, , 则称此通则称此通路为路径路为路径, ,简称路简称路. .对于赋权图，路的长度（即路的权）通常对于赋权图，路的长度（即路的权）通常(tngchng)指路指路上所有边上所有边的权之和。的权之和。最短路问题最短路问题：求赋权图上指定点之间的权最小的路。：求赋权图上指定点之间的权最小的路。 三、最短路问题及其算法三、最短路问题及其算法 第37页/共66页第三十八页，共66页。重要重要(zhngyo)性质：性质：若若v0

27、v1 vm v0 v1 vm 是是G G 中从中从v0v0到到vmvm的最短路的最短路(dunl), (dunl), 则则对对1km, v0v1 vk 1km, v0v1 vk 必为必为G G 中从中从v0v0到到vkvk的的最短路最短路(dunl). (dunl). 即：最短路即：最短路(dunl)是一条路，且最短路是一条路，且最短路(dunl)的任一段的任一段也是最短路也是最短路(dunl)。 三、最短路问题及其算法三、最短路问题及其算法 第38页/共66页第三十九页，共66页。 设有给定连接若干城市设有给定连接若干城市(chngsh)(chngsh)的公路网，寻求从指定的公路网，寻求从指

28、定城市城市(chngsh)(chngsh)到各城市到各城市(chngsh)(chngsh)的最短路线。的最短路线。 2、应用、应用(yngyng)实例：最短路问题实例：最短路问题 问题(wnt)的数学模型: 三、最短路问题及其算法三、最短路问题及其算法402022年年4月月19日日 第39页/共66页第四十页，共66页。412022年年4月月19日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论第40页/共66页第四十一页，共66页。422022年年4月月19日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)

29、建模建模-图论图论第41页/共66页第四十二页，共66页。432022年年4月月19日日 三、最短路问题三、最短路问题(wnt)及其算法及其算法 数学数学(shxu)建模建模-图论图论例例 求下图从顶点求下图从顶点(dngdin) u1 (dngdin) u1 到其他顶点到其他顶点(dngdin)(dngdin)的最短路的最短路03064093021509701608120W邻接矩阵为邻接矩阵为第42页/共66页第四十三页，共66页。442022年年4月月19日日 三、最短路问题三、最短路问题(wnt)及其算法及其算法 数学数学(shxu)建模建模-图论图论)(iul迭代次数1u2u3u 4u

30、5u6u 7u 8u2345678 0 2 8 10 8 3 10 8 6 10 12 7 1012 9 12 12最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5u第43页/共66页第四十四页，共66页。452022年年4月月19日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论例例 matlab matlab程序程序(chngx) road1.m(chngx) road1.m运行结果如下：运行结果如下：l=021736912z=11162545第44页/共66页第四十五页，共66页

31、。462022年年4月月19日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论u1u2u3u4u5u6u7u8第45页/共66页第四十六页，共66页。2022年年4月月19日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论作业作业(zuy)：对下面的有向图求顶点：对下面的有向图求顶点v0到其余顶点的最短到其余顶点的最短路。路。0v2v1v3v4v5v1445642537第46页/共66页第四十七页，共66页。2022年年4月月19日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法

32、 数学数学(shxu)建模建模-图论图论 求非负赋权图求非负赋权图G中某一点到其它各点最短路，一般中某一点到其它各点最短路，一般用用Dijkstra标号算法；标号算法； Dijkstra标号算法只适用标号算法只适用(shyng)于全部权为非负情况。于全部权为非负情况。 求非负赋权图上任意两点间的最短路，一般用求非负赋权图上任意两点间的最短路，一般用Floyd算法算法. Floyd算法可以适用于有负权的情况，还能判断是算法可以适用于有负权的情况，还能判断是否有负回路。否有负回路。 这两种算法均适用于有向赋权图这两种算法均适用于有向赋权图.第47页/共66页第四十八页，共66页。2022年年4月月

33、19日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论Floyd算法：求任意算法：求任意(rny)两顶点的最短路两顶点的最短路 设设A = (aij )nn为赋权图为赋权图G = (V, E, F)的权矩阵的权矩阵, dij表示表示从从vi到到vj点的距离点的距离, rij表示从表示从vi到到vj点的最短路中一个点的点的最短路中一个点的编号编号. 赋初值赋初值. 对所有对所有i, j, dij = aij, rij = j. k = 1. 转向转向. 更新更新dij , rij . 对所有对所有i, j, 若若dik + dk jdij ,

34、则令则令dij = dik + dkj , rij = k, 转向转向; 终止判断终止判断. 若若k = n终止终止; 否则令否则令k = k + 1, 转向转向. 最短路线可由最短路线可由rij得到得到. 第48页/共66页第四十九页，共66页。2022年年4月月19日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论32v1v3v4v5v29724例例 求如下求如下(rxi)(rxi)加权图的任一两点间的最短距离加权图的任一两点间的最短距离和路径和路径road2.m floyd.m road2.m floyd.m 第49页/共66页第五十页

35、，共66页。2022年年4月月19日日 三、最短路问题三、最短路问题(wnt)及其算法及其算法 数学数学(shxu)建模建模-图论图论 5333334331543243332344441,0646960243420256420793570RD32v1v3v4v5v297245v1v3v4v例例 matlab matlab程序程序(chngx) road2.m floyd.m (chngx) road2.m floyd.m 第50页/共66页第五十一页，共66页。2022年年4月月19日日 三、最短路问题三、最短路问题(wnt)及其算法及其算法 数学数学(shxu)建模建模-图论图论作业作业(z

36、uy) (zuy) 求下列加权图中任意两点间的最短距离求下列加权图中任意两点间的最短距离和路径和路径1v3v2v4v5v68523374第51页/共66页第五十二页，共66页。532022年年4月月19日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论选址问题选址问题:在在 n 个居民点个居民点v1, v2, , vn中设置一银行中设置一银行.问设在问设在哪个点哪个点,可使最大服务可使最大服务(fw)距离最小距离最小? 若设两个银行若设两个银行,问设问设在哪两个点在哪两个点? 模型假设模型假设 设各个居民点都有条件设置银行设各个居民点都有条件

37、设置银行,并有路相连并有路相连,且且路长已知路长已知. 模型建立与求解模型建立与求解 用用Floyd算法求出任意两个居民点算法求出任意两个居民点vi , vj 之间的最短距离之间的最短距离,并用并用dij 表示表示.第52页/共66页第五十三页，共66页。542022年年4月月19日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论求k,使.min1inikdd 即若设置(shzh)一个银行,则银行设在 vk 点,可使最大服务距离最小. 设置一个银行,银行设在vi 点的最大服务距离为.,.,2 , 1,max1niddijnji第53页/共66

38、页第五十四页，共66页。552022年年4月月19日日 三、最短路问题三、最短路问题(wnt)及其算法及其算法 数学数学(shxu)建模建模-图论图论 设置两个银行设置两个银行(ynhng),(ynhng),假设银行假设银行(ynhng)(ynhng)设设在在vs , vt vs , vt 点使最大服务点使最大服务 距离最小距离最小. .记.,minmax),(1jkiknkddjid则s,t 满足：).,(min),(1jidtsdnji进一步进一步, ,若设置多个银行呢？若设置多个银行呢？第54页/共66页第五十五页，共66页。562022年年4月月19日日 作业作业(zuy)： 数学数学

39、(shxu)建模建模-图论图论1 1、一只狼、一头山羊和一箩卷心菜在河的同侧、一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要。一个摆渡人要 将它们运过河去，但由于船小，他一次将它们运过河去，但由于船小，他一次只能运三者之一过河。只能运三者之一过河。 显然，不管是狼和山羊，还是山羊和卷心显然，不管是狼和山羊，还是山羊和卷心菜，都不能在无人监菜，都不能在无人监 视的情况下留在一起。问摆渡人应怎样把视的情况下留在一起。问摆渡人应怎样把它们运过河去？它们运过河去？2 2、北京（、北京（PePe）、东京）、东京(T)(T)、纽约、纽约(ni yu)(N)(ni yu)(N)、墨西哥城墨西哥城(M)

40、(M)、伦敦、伦敦(L)(L)、 巴黎巴黎(Pa)(Pa)各城市之间的航线距离如下各城市之间的航线距离如下表，请应用最短路方法，表，请应用最短路方法， 给出北京到其他城市的最短路，并通过给出北京到其他城市的最短路，并通过图的形式标出。图的形式标出。第55页/共66页第五十六页，共66页。572022年年4月月19日日 数学数学(shxu)建模建模-图论图论例系统监控模型:居民区如图所示,ei为街道,vi为交叉路口,计划在交叉路口安置消防设施(shsh),只有与路口相邻的街道才能使用它们.为使街道必要时都有消防设施(shsh)使用,在那些路口安置设施(shsh)最节约?覆盖集：KV(G),对任意

41、eE，则e至少一顶属于K， 则K为G一个 覆盖集； 若K是G的覆盖集，对与任意vK, K-V不是(b shi)覆盖集。则K是 G的极小覆盖集。含顶最少覆盖集为最小覆盖集。 最小覆盖集中所含顶数为图G的覆盖数。第56页/共66页第五十七页，共66页。582022年年4月月19日日 数学数学(shxu)建模建模-图论图论e1e4e3e2e5e6e7v1v2v3v4v5问题(wnt)归结为求最小覆盖(1)建立(jinl)关联矩阵e1e2e3e4e5e6e7v11001000v21100100v30110010v40011001v50000111第57页/共66页第五十八页，共66页。592022年年

42、4月月19日日 数学数学(shxu)建模建模-图论图论e1e2e3e4e5e6e7v11001000v21100100v30110010v40011001v50000111e1e4e5e7v11100v21010 v40101v50011(3)划去v对应(duyng)的行及1所在列e4e7v110v411v501(2)寻含1最多的顶v归于(guy)K(例v3K)(4).在剩余矩阵内重复以上过程直至矩阵空K=v2v3v4第58页/共66页第五十九页，共66页。支配集：DV(G),若图G中任意顶vD，则v必与D内一顶相邻，则D为G的一个(y)支配集。若D是G的覆盖集，若D的任意子集不是支配集。则D是G的极小支配集。含顶最少的支配集为最小支配集。最小支配集中所含顶数为图G的支配数。例2:如图6个城镇v1v2v6建立通信系统,从中选几座城镇建中心台站,要求它们与各城镇相邻,为减少造价使中心台站数目最少.请提供建立方案.若在造价最低的条件下,建两套通