数学建模图论学习教案.pptx

《数学建模图论学习教案.pptx》由会员分享，可在线阅读，更多相关《数学建模图论学习教案.pptx（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、会计学1数学数学(shxu)建模图论建模图论第一页，共66页。前言前言(qin yn)n n图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。n n图与网络是运筹学（Operations Research）中的一个经典(jngdin)和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。n n传统的物理、化学、生命科学也都越来越广泛地使用了图论模型方法。第1页/共66页第二页，共66页。从七桥问题说起从七桥问题说起从七桥问题说起从七桥问题说起(shu q)(shu q)(shu q)(shu q)-

2、关于图模型关于图模型关于图模型关于图模型n n在哥尼斯堡有条普莱格尔河在哥尼斯堡有条普莱格尔河,它有两条支流在城市中它有两条支流在城市中心汇合后流入波罗的海。这条河将城市分割成四块心汇合后流入波罗的海。这条河将城市分割成四块:A:A、C C两个两个(li(li n n )小岛和小岛和B B、DD两块陆地（如图）。两块陆地（如图）。问题问题(wnt)的提出的提出哥尼斯堡七桥问题 七桥问题是发生在18世纪东普鲁土的哥尼斯堡的一个真实故事。ABCD第2页/共66页第三页，共66页。n n为通行方便，在四块陆地之间建了七座桥，每到节、假日或为通行方便，在四块陆地之间建了七座桥，每到节、假日或傍晚，都有

3、许多居民和大学生来此散步。久而久之傍晚，都有许多居民和大学生来此散步。久而久之,人们发人们发现并热衷于讨论这样现并热衷于讨论这样(zhyng)(zhyng)一个问题一个问题:能否从四块陆地之能否从四块陆地之一出发一出发,走遍每座桥一次且仅一次然后回到出发地走遍每座桥一次且仅一次然后回到出发地?n n自然有不少人作过实地尝试自然有不少人作过实地尝试,但一直未能实现。但一直未能实现。ABCD1735年,有大学生写信把问题告诉了欧拉,请他帮助解决(jiju)。欧拉从大家的失败中进行抽象的数学思考,从数学角度成功地解决(jiju)了问题。第3页/共66页第四页，共66页。问题分析与模型问题分析与模型(

4、mxng)(mxng)假设：假设：2.四块陆地可重复(chngf)经历,至于陆地的大小、形状、质地等也与问题的本质无关，因而可视四块陆地为四个点A、B、C、D。1.问题的本质是能否从一地无重复地一次走遍七桥,因而与所走过的桥的大小、形状、长短、曲直(qzh)等均无关，而只要桥存在，因此不妨将其视为一条弧线ABCDABDC第4页/共66页第五页，共66页。对对四个四个陆陆地地(ld)A(ld)A、B B、C C、D D，若其，若其间间有有桥桥，则则用一条弧用一条弧线连线连接起来，有两座接起来，有两座桥桥，则连则连两条不重合的弧两条不重合的弧线线，便得到一个，便得到一个图图，并称代表，并称代表陆陆

5、地地(ld)(ld)的四个点的四个点为顶为顶点点 ，代表，代表桥桥的弧的弧线为线为 边边 。这样一来，能否从一地出发(chf)走遍七座桥一次且仅一次再回到出发(chf)点就变成了：能否从这个图上任一顶点出发(chf)，经过每条边一次且仅一次而回到出发(chf)顶点。这就是众所周知的这个图能否“一笔画出”的问题。ABCDABDC第5页/共66页第六页，共66页。n n能否从能否从这这个个图图上任一上任一顶顶点点(dngdin)(dngdin)出出发发，经过经过每条每条边边一一次且次且仅仅一次而回到出一次而回到出发顶发顶点点(dngdin)(dngdin)。7“一笔画(bhu)出”能否从这个(zh

6、 ge)图上任一顶点出发，经过每个顶点一次且仅一次而回到出发顶点。旅行商问题旅行商问题能否从这个图选择尽量少的点，使得所有的其余点都和该点集有路径连接。覆盖问题覆盖问题-系统监控模型系统监控模型能否将图中点集分类，使得每一类点集都没有路径连接，最少需要分几类。支配集支配集-仓库分区仓库分区第6页/共66页第七页，共66页。n n将将该图该图中所有中所有顶顶点点(dngdin)(dngdin)用不同用不同颜颜色表示，最色表示，最少需要几种少需要几种颜颜色。色。8“点着(din zhe)色将该图中所有边用不同颜色表示，最少需要(xyo)几种颜色。边着色边着色关键路径关键路径最大流、最小流最大流、最

7、小流第7页/共66页第八页，共66页。问题问题2(2(哈密顿环球旅行问题哈密顿环球旅行问题):):十二面体的十二面体的2020个顶点代表世界个顶点代表世界(shji)(shji)上上2020个城市，能否从某个城市出发在十二面体上依次个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？经过每个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）第8页/共66页第九页，共66页。问题问题(wnt)3(wnt)3(四色问题四色问题(wnt):(wnt):对任何一张地图进行着色，两个共同边界的对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了国家染

8、不同的颜色，则只需要四种颜色就够了.第9页/共66页第十页，共66页。问题问题4(4(关键路径问题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中一座体育中心心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括许多都要包括许多工序工序.这些工序相互约束这些工序相互约束,只有在某些只有在某些(mu xi)(mu xi)工序工序完成之后完成之后,一个工序才能开始一个工序才能开始.即它们之间存在完即它们之间存在完成的先后次序关系成的先后次序关系,一般认为这些关系是预知的一般认为这些关系是预知的,而而且也能够预计完成每个工序所需要的时间且也能够

9、预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目时间才能够完成整个工程项目,影响工程进度的要影响工程进度的要害工序是哪几个？害工序是哪几个？第10页/共66页第十一页，共66页。一一图的基本概念图的基本概念二二二二三三三三最短路最短路(dunl)问题问题及其算法及其算法四四四四最小生成最小生成(shn chn)树问题树问题图的矩阵图的矩阵(j zhn)表示表示第11页/共66页第十二页，共66页。数学数学(shxu)建模建模-图论图论132023年年2月月7日日 一、图的基本概念一、图的基本概念第12页/共

10、66页第十三页，共66页。数学数学(shxu)建模建模-图论图论142023年年2月月7日日 一、图的基本概念一、图的基本概念图图1 1图图2 2第13页/共66页第十四页，共66页。数学数学(shxu)建模建模-图论图论152023年年2月月7日日 一、图的基本概念一、图的基本概念 一个图会有许多外形不同的图解,下面两个(lin)图表示同一个图G=(V,E)的图解.其中 V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4.第14页/共66页第十五页，共66页。数学数学(shxu)建模建模-图论图论162023年年2月月7日日 一、图的基本概念一、图的基

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

12、关联的边的数目称为出度，记作d+(v)d+(v)，与顶点与顶点v v入关联的边的数目称为入度，记作入关联的边的数目称为入度，记作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)建模建模-图论图论192023年年2月月7日日 一、图的基本概念一、图的基本概念几个基本几个基本

13、(jbn)定理：定理：第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 v1 vkv0 v1 vk是是G G的一条的一条(y tio)(y tio)通路通路.如果通路中没有如果通路中没有(mi yu)相同的

14、顶点相同的顶点,则称此通路为路则称此通路为路径径,简称路简称路.始点和终点相同的路称为始点和终点相同的路称为圈圈或或回路回路.一、图的基本概念一、图的基本概念数学建模数学建模数学建模数学建模-图论图论图论图论 数学建模数学建模数学建模数学建模-图论图论图论图论第19页/共66页第二十页，共66页。顶点顶点u u与与v v称为连通的，如果存在称为连通的，如果存在u u到到v v通路，任二顶点通路，任二顶点都连通的图称为连通图，否则都连通的图称为连通图，否则(fuz)(fuz)，称为非连通图。极，称为非连通图。极大连通子图称为连通分图。大连通子图称为连通分图。连通(lintng)而无圈的图称为树,

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

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

17、，羊，菜）的在西岸状态状态(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)建模建模-图论图论人在河西(hx)：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0

18、）（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）下过奇数盘棋的人数）下过奇数盘棋的人数(rn sh)是偶数个。是

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

20、示人，以边表示认识，得6个顶点个顶点的简单图的简单图G。问题：问题：3人互相认识即人互相认识即G包含包含K3为子图，为子图，3人互相不认识即人互相不认识即G包含（包含（3,0）图为子图。）图为子图。第25页/共66页第二十六页，共66页。一、图的基本概念一、图的基本概念(应用应用(yngyng)数学数学(shxu)建模建模-图论图论第26页/共66页第二十七页，共66页。282023年年2月月7日日一、图的基本概念一、图的基本概念(应用应用(yngyng)数学数学(shxu)建模建模-图论图论（设备更新问题）某企业每年年初（设备更新问题）某企业每年年初,都要作出决定都要作出决定,如果继续如果继

21、续(jx)(jx)使用旧设备使用旧设备,要付维修费；若购买一要付维修费；若购买一台新设备台新设备,要付购买费要付购买费.试制定一个试制定一个5 5年更新计划年更新计划,使使总支出最少总支出最少.已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11,11,11,12,12,13.12,12,13.使用不同时间设备所需的维修费分别为使用不同时间设备所需的维修费分别为5,6,8,11,18.5,6,8,11,18.第27页/共66页第二十八页，共66页。292023年年2月月7日日求求v1v1到到v6v6的最短路的最短路(dunl)(dunl)问题问题.一、图的基本概念一、图的

22、基本概念(应用应用(yngyng)(yngyng)数学数学(shxu)建模建模-图论图论第28页/共66页第二十九页，共66页。302023年年2月月7日日从上图中容易从上图中容易(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页。邻接矩阵（结点与结点的关系）

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

24、hxu)建模建模-图论图论第31页/共66页第三十二页，共66页。2 2 有向图的权矩阵有向图的权矩阵(j zhn)A=(aij)nn(j zhn)A=(aij)nn（n n为结点数）为结点数）例2：写出右图的权矩阵(j zhn)：解：二、图的矩阵二、图的矩阵(j zhn)表示表示 数学建模数学建模数学建模数学建模-图论图论图论图论第32页/共66页第三十三页，共66页。3 有向图的关联矩阵有向图的关联矩阵A=(aij)nm（n为结点为结点(ji din)数数m为边数）为边数）有向图：有向图：无向无向(w xin)图：图：二、图的矩阵二、图的矩阵(j zhn)表示表示 数学建模数学建模数学建模

25、数学建模-图论图论图论图论第33页/共66页第三十四页，共66页。例例3 3：分别：分别(fnbi)(fnbi)写出右边两图的关写出右边两图的关联矩阵联矩阵解：分别(fnbi)为：二、图的矩阵二、图的矩阵(j zhn)表示表示 数学建模数学建模数学建模数学建模-图论图论图论图论第34页/共66页第三十五页，共66页。二、图的矩阵二、图的矩阵(j zhn)(j zhn)表示表示4 4 应用应用(yngyng)(yngyng)实例实例 数学数学(shxu)建模建模-图论图论某航空公司在A,B,C,D四城市之间开辟了若干航线,如图所示表示了四城市间的航班图,如果从A到B有航班,则用带箭头的线连接A与

26、B.问题:如何直观给出各个城市之间的航班情况问题:如果没有直接航班到达,需要转机,有几种转机方案问题:如果城市不止4个,有n个城市,能否快速给出直接路径以及需要转机方案.问题:过年回家火车路线如何设置，北京公交地铁倒车如何如何设置百度地图第35页/共66页第三十六页，共66页。二、图的矩阵二、图的矩阵(j zhn)(j zhn)表示表示 数学数学(shxu)建模建模-图论图论数值表示(biosh)两地之间航线的数目，1表示(biosh)只有一条路径，2代表有两条路径第36页/共66页第三十七页，共66页。若将图若将图G G 的每一条边的每一条边e e都对应一个实数都对应一个实数(shsh)F(

27、e),(shsh)F(e),则称则称F(e)F(e)为该边的权为该边的权,并称图并称图G G为赋权图为赋权图,记为记为G=(V,E,G=(V,E,F).F).设设G=(V,E)G=(V,E)是一个是一个(y)(y)图图,v0,v1,v0,v1,vkV,vkV,且且“1ik,vi“1ik,vi1 viE,1 viE,则称则称v0 v1 vkv0 v1 vk是是G G的一条通路的一条通路.如果通路中没有相同的顶点如果通路中没有相同的顶点,则称此通路为则称此通路为路径路径,简称路简称路.对于赋权图，路的长度（即路的权）通常对于赋权图，路的长度（即路的权）通常(tngchng)指路指路上所有边上所有边

28、的权之和。的权之和。最短路问题最短路问题：求赋权图上指定点之间的权最小的路。：求赋权图上指定点之间的权最小的路。三、最短路问题及其算法三、最短路问题及其算法 数学建模数学建模数学建模数学建模-图论图论图论图论第37页/共66页第三十八页，共66页。重要重要(zhngyo)性质：性质：若若v0 v1 vm v0 v1 vm 是是G G 中从中从v0v0到到vmvm的最短路的最短路(dunl),(dunl),则则对对1km,v0v1 vk 1km,v0v1 vk 必为必为G G 中从中从v0v0到到vkvk的的最短路最短路(dunl).(dunl).即：最短路即：最短路(dunl)是一条路，且最短

29、路是一条路，且最短路(dunl)的任一段的任一段也是最短路也是最短路(dunl)。三、最短路问题及其算法三、最短路问题及其算法 数学建模数学建模数学建模数学建模-图论图论图论图论第38页/共66页第三十九页，共66页。设有给定连接若干城市设有给定连接若干城市(chngsh)(chngsh)的公路网，寻求从指定城的公路网，寻求从指定城市市(chngsh)(chngsh)到各城市到各城市(chngsh)(chngsh)的最短路线。的最短路线。2、应用、应用(yngyng)实例：最短路问题实例：最短路问题 问题(wnt)的数学模型:三、最短路问题及其算法三、最短路问题及其算法402023年年2月月7

30、日日 数学建模数学建模数学建模数学建模-图论图论图论图论第39页/共66页第四十页，共66页。412023年年2月月7日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论第40页/共66页第四十一页，共66页。422023年年2月月7日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论第41页/共66页第四十二页，共66页。432023年年2月月7日日 三、最短路问题三、最短路问题(wnt)及其算法及其算法 数学数学(shxu)建模建模-图论图论例例 求下图从顶点求下图从顶点(dngdin)u1

31、(dngdin)u1 到其他顶点到其他顶点(dngdin)(dngdin)的最短路的最短路邻接矩阵为邻接矩阵为第42页/共66页第四十三页，共66页。442023年年2月月7日日 三、最短路问题三、最短路问题(wnt)及其算法及其算法 数学数学(shxu)建模建模-图论图论第43页/共66页第四十四页，共66页。452023年年2月月7日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论例例 matlab matlab程序程序(chngx)road1.m(chngx)road1.m运行结果如下：运行结果如下：l=021736912z=11162

32、545第44页/共66页第四十五页，共66页。462023年年2月月7日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论u1u2u3u4u5u6u7u8第45页/共66页第四十六页，共66页。2023年年2月月7日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论作业作业(zuy)：对下面的有向图求顶点：对下面的有向图求顶点v0到其余顶点的最短到其余顶点的最短路。路。1445642537第46页/共66页第四十七页，共66页。2023年年2月月7日日 三、最短路三、最短路(dunl)问题及其算

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

34、2月月7日日 三、最短路三、最短路(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,则令则令dij=dik+dkj,rij=k,转向转向;终止判断

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

36、论图论329724例例 matlab matlab程序程序(chngx)road2.m floyd.m (chngx)road2.m floyd.m 第50页/共66页第五十一页，共66页。2023年年2月月7日日 三、最短路问题三、最短路问题(wnt)及其算法及其算法 数学数学(shxu)建模建模-图论图论作业作业(zuy)(zuy)求下列加权图中任意两点间的最短距离和求下列加权图中任意两点间的最短距离和路径路径68523374第51页/共66页第五十二页，共66页。532023年年2月月7日日 三、最短路三、最短路(dunl)问题及其算法问题及其算法 数学数学(shxu)建模建模-图论图论

37、选址问题选址问题:在在 n 个居民点个居民点v1,v2,vn中设置一银行中设置一银行.问设在问设在哪个点哪个点,可使最大服务可使最大服务(fw)距离最小距离最小?若设两个银行若设两个银行,问设问设在哪两个点在哪两个点?模型假设模型假设 设各个居民点都有条件设置银行设各个居民点都有条件设置银行,并有路相连并有路相连,且且路长已知路长已知.模型建立与求解模型建立与求解 用用Floyd算法求出任意两个居民点算法求出任意两个居民点vi,vj 之间的最短距离之间的最短距离,并用并用dij 表示表示.第52页/共66页第五十三页，共66页。542023年年2月月7日日 三、最短路三、最短路(dunl)问题

38、及其算法问题及其算法 数学数学(shxu)建模建模-图论图论求k,使 即若设置(shzh)一个银行,则银行设在 vk 点,可使最大服务距离最小.设置一个银行,银行设在vi 点的最大服务距离为第53页/共66页第五十四页，共66页。552023年年2月月7日日 三、最短路问题三、最短路问题(wnt)及其算法及其算法 数学数学(shxu)建模建模-图论图论 设置两个银行设置两个银行(ynhng),(ynhng),假设银行假设银行(ynhng)(ynhng)设设在在vs,vt vs,vt 点使最大服务点使最大服务 距离最小距离最小.记则s,t 满足：进一步进一步,若设置多个银行呢？若设置多个银行呢？

39、第54页/共66页第五十五页，共66页。562023年年2月月7日日 作业作业(zuy)：数学数学(shxu)建模建模-图论图论1 1、一只狼、一头山羊和一箩卷心菜在河的同侧。、一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要一个摆渡人要 将它们运过河去，但由于船小，他一次只将它们运过河去，但由于船小，他一次只能运三者之一过河。能运三者之一过河。显然，不管是狼和山羊，还是山羊和卷心显然，不管是狼和山羊，还是山羊和卷心菜，都不能在无人监菜，都不能在无人监 视的情况下留在一起。问摆渡人应怎样把视的情况下留在一起。问摆渡人应怎样把它们运过河去？它们运过河去？2 2、北京（、北京（PePe）、东京

40、）、东京(T)(T)、纽约、纽约(ni yu)(N)(ni yu)(N)、墨西哥城墨西哥城(M)(M)、伦敦、伦敦(L)(L)、巴黎巴黎(Pa)(Pa)各城市之间的航线距离如下各城市之间的航线距离如下表，请应用最短路方法，表，请应用最短路方法，给出北京到其他城市的最短路，并通过给出北京到其他城市的最短路，并通过图的形式标出。图的形式标出。第55页/共66页第五十六页，共66页。572023年年2月月7日日 数学数学(shxu)建模建模-图论图论例系统监控模型:居民区如图所示,ei为街道,vi为交叉路口,计划在交叉路口安置消防设施(shsh),只有与路口相邻的街道才能使用它们.为使街道必要时都有

41、消防设施(shsh)使用,在那些路口安置设施(shsh)最节约?覆盖集：KV(G),对任意eE，则e至少一顶属于K，则K为G一个 覆盖集；若K是G的覆盖集，对与任意vK,K-V不是(b shi)覆盖集。则K是 G的极小覆盖集。含顶最少覆盖集为最小覆盖集。最小覆盖集中所含顶数为图G的覆盖数。第56页/共66页第五十七页，共66页。582023年年2月月7日日 数学数学(shxu)建模建模-图论图论e1e4e3e2e5e6e7v1v2v3v4v5问题(wnt)归结为求最小覆盖(1)建立(jinl)关联矩阵e1e2e3e4e5e6e7v11001000v21100100v30110010v40011

42、001v50000111第57页/共66页第五十八页，共66页。592023年年2月月7日日 数学数学(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内一顶相邻

43、，则D为G的一个(y)支配集。若D是G的覆盖集，若D的任意子集不是支配集。则D是G的极小支配集。含顶最少的支配集为最小支配集。最小支配集中所含顶数为图G的支配数。例2:如图6个城镇v1v2v6建立通信系统,从中选几座城镇建中心台站,要求它们与各城镇相邻,为减少造价使中心台站数目最少.请提供建立方案.若在造价最低的条件下,建两套通信中心,以备出故障(gzhng)时启用另一套请提供建立方案.v6v2v1v3v4v5第59页/共66页第六十页，共66页。归为求最小支配(zhpi)(1)写出邻接矩阵A,将主对角线元素(yuns)全改为1.即A+E.v1v2v3v4v5v6v1111100v411111

44、1v2110100v3101100v5000111v6000111(3)划去A+E中v对应(duyng)的行及1所在列(2)寻含1最多的顶v归于D(例v4D)(4).在剩余矩阵内重复以上过程直至矩阵空若建两套通信中心,可在A+E划去v4对应的行,在剩余矩阵(A+E)2中重复以上过程v1v2v3v4v5v6v1111100v2110100v3101100 v5000111v6000111第60页/共66页第六十一页，共66页。v5v6v200v300v511v611D=v1v5独立(dl)集：IV(G),I中任意两顶不相邻，则I为G的一个独立(dl)集。若I是G的独立(dl)集，对与任意uV(G

45、),Iu不是独立(dl)集。则I是G的极大独立(dl)集。含顶最多的独立(dl)集为最大独立(dl)集。最大独立(dl)集中所含顶数为图G的独立(dl)数。定理(dngl)：K为极小覆盖VK为极大独立集。极大独立集必为极小支配集,反之(fnzh)不成立.第61页/共66页第六十二页，共66页。例3.公司生产a,b,c,d,e,f,g7种化学品,其中(a,b)(a,d)(b,c)(b,e)(b,g)(c,d)(c,e)(c,f)(d,e)(d,g)(e,f)(f,g)不能放在一起,公司必须把仓库分成若干个区,以便把不相容的制品分开(fnki),问至少分几个区,怎样存放才能保证安全.以顶vavbv

46、g表示7种化学(huxu)制品,在不相容制品间连边得图Gvfvavbvcvdvgve归为求最大独立(dl)集(也可用顶点着色)先求最小覆盖K1,则S1=V-K1为一个最大独立集.再求最小覆盖V-S1,最大独立集S2.再求最小覆盖V-S1-S2,最大独立集S3.第62页/共66页第六十三页，共66页。问题(wnt)归结为求最小覆盖(1)建立(jinl)关联矩阵(2)寻含1最多的顶v归于(guy)K(例vbK)vfvavbvcvdvgveeabeadebcecdebgebeeceeefefgedgecfva11000000000 vb10101100000 vc00110010001 vd01010000010 ve00000111000vf00000001101vg00001000110第63页/共66页第六十四页，共66页。寻含1最多的顶v归于(guy)K2(eabeadebcecdebgebeeceeefefgedgecfva11000000000 vb10101100000 vc00110010001 vd01010000010 ve00000111000vf00000001101 vg00001000110第64页/共66页第六十五页，共66页。vfvavbvcvdvgve第65页/共66页第六十六页，共66页。