数学建模图论模型学习教案

1、会计学1数学建模图论数学建模图论(t ln)模型模型第一页，共75页。第1页/共74页第二页，共75页。 1. 几个(j )引例2. 基本概念 3. 最短路(dunl)问题及算法 4. 简单(jindn)应用 第2页/共74页第三页，共75页。ABCD哥尼斯堡七桥示意图问题1:七桥问题 能否从任一陆地出发通过(tnggu)每座桥恰好一次而回到出发点？1. 几个(j )引例第3页/共74页第四页，共75页。七桥问题(wnt)模拟图ABDC欧拉指出：如果(rgu)每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。第4页/共74页第五页，共75页。 莱昂哈德欧拉(L

2、eonhard Euler，) 瑞士的数学家和物理学家(w l xu ji)。他被称为历史上最伟大的两位数学家之一（另一位是卡尔弗里德里克高斯）。欧拉出生于瑞士，在那里受教育。他是一位数学神童。作为数学教授，他先后任教于圣彼得堡(1727-1741)和柏林，尔后再返圣彼得堡(1766)。 欧拉的一生很虔诚。然而，那个广泛流传的传说却不是真的。传说中说到，欧拉在叶卡捷琳娜二世的宫廷里，挑战德尼狄德罗：“先生，(a+b)n/n = x；所以上帝存在，这是回答！” 欧拉的离世也很特别：据说当时正是下午茶时间，正在逗孙儿玩的时候，被一块蛋糕卡在喉头窒息而死。 欧拉是第一个使用“函数”一词来描述包含各种

3、参数的表达式的人，例如：y = F(x) (函数的定义由莱布尼兹在1694年给出)。他是把微积分应用于物理学的先驱者之一。欧拉是有史以来最多产的数学家，他的全集共计75卷。欧拉实际上支配了18世纪的数学，对于当时新发明的微积分，他推导出了很多结果。在他生命的最后7年中，欧拉的双目完全失明，尽管如此，他还是以惊人的速度产出了生平一半的著作。 小行星欧拉2002是为了纪念欧拉而命名的。莱昂哈德欧拉 第5页/共74页第六页，共75页。问题2:哈密顿圈（环球旅行游戏）十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次(yc)经过每个城市恰好一次最后回到出发点？第6页/共74页

4、第七页，共75页。问题(wnt)3:四色问题(wnt) 对任何(rnh)一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了。德摩尔根致哈密顿的信（1852年10月23日） 我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有(jyu)公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。第7页/共74页第八页，共75页。问题4(关键路径问题) 一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, 都要包括许多工序.这些工序相互约束,只有在某些工序完

5、成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这些关系是预知(y zh)的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目, 影响工程进度的要害工序是哪几个？ 第8页/共74页第九页，共75页。1) 图的概念(ginin)2) 赋权图与子图3) 图的矩阵(j zhn)表示4) 图的顶点度5) 路和连通第9页/共74页第十页，共75页。 定义 一个(y )图G是指一个(y )二元组(V(G),E(G)，其中: 其中元素(yun s)称为图G的顶点.组成的集合，即称为边集,其中元素称为边.),(jivv 定义

6、 图G的阶是指图的顶点数|V(G)|, 用来表示；v图的边的数目|E(G)|用来表示. 也用来表示边jivv).,(jivv,)(21vvvGV是非空有限集，称为顶点集，1)2) E(G)是顶点集V(G)中的无序或有序的元素偶对).,(EVG )(),(GEGVG 表示图，简记 用第10页/共74页第十一页，共75页。 其为有限图. 只有一个顶点的图称为平凡(pngfn)图，其他的 所有(suyu)图都称为非平凡图.第11页/共74页第十二页，共75页。,称G为有向),(jivv边 为无向边，称e连接(linji) 和 ，顶点 和 称图. 称边为有向边或弧,称),(jivve 是从),(jiv

7、ve iv连接(linji)jv，称 为e的尾，称 为e的头. ivjv 若图G中的边均为无序偶对 ，称G为无向图.称jivv为e的端点. jivve ivjvivjv 既有无向边又有有向边的图称为混合图.第12页/共74页第十三页，共75页。1) 边和它的两端点称为互相(h xing)关联.2)与同一条边关联的两个(lin )端点称为相邻的顶点，与同一个顶点 点关联的两条边称为相邻的边. 3) 端点重合为一点的边称为环， 端点不相同的边称为连杆.4) 若一对顶点之间有两条以上的边联结，则这些边 称为重边5) 既没有环也没有重边的图，称为简单图 第13页/共74页第十四页，共75页。 常用(c

8、hn yn)术语6) 任意两顶点都相邻的简单(jindn)图,称为完全图. 记为Kv. 7) 若 ， ，且X 中任意(rny)两顶点不YXGV)(YX ， 相邻，Y 中任意两顶点不相邻，则称为二部图或 偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为完全二部图或完全偶图,记为 (m=|X|,n=|Y|)nmK,8) 图 叫做星.nK, 1:X1x2x3x:Y1y2y3y4y二部图6K:X1x2x3x:Y1y2y3y4y4 , 1K4 , 3K第14页/共74页第十五页，共75页。)(),(GEGVG 一个(y )实数w(e)，称w(e)为边e的权，G 连同边上的权称为(chn wi)赋权图.

9、定义 设 和 是两个图.),(EVG ),(EVG 1) 若 ,称 是 的一个子图,记 EEVV,GG.GG 2) 若 ， ，则称 是 的生成子图.VV EE GG 3) 若 ，且 ，以 为顶点集，以两端点 VV VV 均在 中的边的全体为边集的图 的子图，称 VG 为 的由 导出的子图，记为 .GVVG4) 若 ，且 ，以 为边集，以 的端点EE EEE 集为顶点集的图 的子图，称为 的由 导出的GGE 边导出的子图，记为 . EG第15页/共74页第十六页，共75页。,321vvvG,6543eeeeG 3) 若 ，且 ，以 为顶点集，以两端点 VV VV 均在 中的边的全体为边集的图 的

10、子图，称 VG4) 若 ，且 ，以 为边集，以 的端点EE EEE 集为顶点集的图 的子图，称为 的由 导出的GGE 边导出的子图，记为 . EGGVVG 为 的由 导出的子图，记为 .第16页/共74页第十七页，共75页。邻接矩阵:1) 对无向图 ，其邻接矩阵 ，其中： G)(ijaA., 0, 1不相邻与若相邻与若jijiijvvvva54321543210010000100110110010100110vvvvvAvvvvv(以下均假设(jish)图为简单图).第17页/共74页第十八页，共75页。2) 对有向图 ,其邻接矩阵 ,其中： )(ijaA),(EVG .),(, 0,),(,

11、 1EvvEvvajijiij若若432143210100001000001110uuuuAuuuu第18页/共74页第十九页，共75页。其中(qzhng)：3) 对有向赋权图 , 其邻接矩阵 ,)(ijaA),(EVG .),(,0,),(,EvvjiwEvvwajiijjiijij若，为其权，且若43214321040608730uuuuAuuuu对于(duy)无向赋权图的邻接矩阵可类似定义. 第19页/共74页第二十页，共75页。1) 对无向图 ，其关联矩阵 ,),(EVG )(ijmM其中(qzhng)：., 0, 1不关联与若相关联与若jijiijevevm5432154321100

12、0001000111100010100011vvvvvMeeeee第20页/共74页第二十一页，共75页。2) 对有向图 ，其关联矩阵 ,),(EVG )(ijmM., 0, 1, 1的头与尾不是若的头是若的尾是若jijijiijevevevm其中(qzhng)：43215432111000101100001101101uuuuMeeeee第21页/共74页第二十二页，共75页。 邻接矩阵 A = (aij )nn , EvvEvvajijiij, 0, 1例 写出右图的邻接矩阵0101100101001010A解：第22页/共74页第二十三页，共75页。 权矩阵(j zhn)A = (aij

13、 ) nn EvvjiEvvvvFajijijiij , , 0 ,例 写出右图的权矩阵(j zhn)：05420370860A解：图的矩阵(j zhn)表示第23页/共74页第二十四页，共75页。定义(dngy) 1) 在无向图G中，与顶点v关联的边的数目(环算两次),称为(chn wi)顶点v的度或次数，记为d(v)或 dG(v).称度为奇数的顶点为奇点，度为偶数的顶点为偶点.2) 在有向图中，从顶点v引出的边的数目称为顶点 v的出度，记为d+(v)，从顶点v引入的边的数目称为 v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的 度或次数定理.2)(Vvvd的个

14、数为偶数推论 任何图中奇点4)(1vd1)(3ud2)(3ud3)(3ud第24页/共74页第二十五页，共75页。 定义(dngy)1) 无向图G的一条途径（或通道或链）是指一个有限非空序列 ，它的项交替kkveevevW2110 地为顶点和边，使得对 ， 的端点是 和 ,ki 1ie1iviv称W是从 到 的一条途径，或一条 途径. 整0vkv),(0kvv数k称为W的长. 顶点 和 分别称为的起点和终点 ,0vkv而 称为W的内部顶点.121,kvvv 2) 若途径W的边互不相同但顶点(dngdin)可重复，则称W为迹或简单链. 3) 若途径W的顶点和边均互不相同，则称W为路或路径. 一条

15、起点为 ,终点为 的路称为 路0vkv),(0kvv记为).,(0kvvP第25页/共74页第二十六页，共75页。 定义(dngy) 1) 途径 中由相继项构成子序列kkvevevW.110 称为途径W的节.jjiiivevev.11 2) 起点与终点(zhngdin)重合的途径称为闭途径. 3) 起点与终点重合的的路称为(chn wi)圈(或回路)，长为k的圈称为k阶圈，记为Ck. 4) 若在图G中存在(u,v)路，则称顶点u和v在图G中连通. 5) 若在图G中顶点u和v是连通的，则顶点u和v之之间的距离d(u,v)是指图G中最短(u,v)路的长；若没没有路连接u和v，则定义为无穷大.第26

16、页/共74页第二十七页，共75页。 6) 图G中任意(rny)两点皆连通的图称为连通图 7) 对于有向图G，若 ，且 有kkveevevW2110ie 类似(li s)地，可定义有向迹，有向路和有向圈.头 和尾 ，则称W为有向途径.iv1iv 例 在右图中： 途径(tjng)或链： 迹或简单链： 路或路径： 圈或回路：wugyexeyfxcyvbwcxdvauguavdxcwuuavbwcxfyg第27页/共74页第二十八页，共75页。例 一摆渡人欲将一只狼，一头羊，一篮菜从河西(h x)渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。第28页/共74页

17、第二十九页，共75页。解：用四维0-1向量表示(biosh)（人，狼，羊，菜）的在西岸状态，（在西岸则分量取1，否则取0.）共24=16种状态(zhungti)，由题设，状态(zhungti)（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允许的，从而对应状态（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允许的，图论的基本概念第29页/共74页第三十页，共75页。人在河西(h x)：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,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）人

18、在河东(h dn)：以十个向量作为顶点，将可能(knng)互相转移的状态连线，则得10个顶点的偶图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。图论的基本概念第30页/共74页第三十一页，共75页。 最短路问题(wnt)是图论应用的基本问题(wnt)，很多实际问题，如线路(xinl)的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.最短路的定义最短路问题的两种方法：Dijkstra和Floyd算法 .1) 求赋权图中从给定点到其余顶点的最短路.2

19、) 求赋权图中任意两点间的最短路.第31页/共74页第三十二页，共75页。 2) 在赋权图G中，从顶点(dngdin)u到顶点(dngdin)v的具有最小权定义(dngy) 1) 若H是赋权图G的一个子图，则称H的各边的权和 为H的权. 类似地，若)()()(HEeewHw称为(chn wi)路P的权若P(u,v)是赋权图G中从u到v的路,称)()()(PEeewPw 的路P*(u,v)，称为u到v的最短路 3) 把赋权图G中一条路的权称为它的长，把(u,v)路的最小权称为u和v之间的距离，并记作 d(u,v). 第32页/共74页第三十三页，共75页。 假设(jish)G为赋权有向图或无向图

20、，G边上的权均非负若 ，则规定 )(),(GEvu.),(vuw最短路(dunl)是一条路，且最短路(dunl)的任一节也是最短路(dunl)求下面赋权图中顶点u0到其余顶点的最短路第33页/共74页第三十四页，共75页。Dijkstra算法(sun f): 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(minvuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i+1 代1i1i替i，

21、并转2). 7,.,2 , 1,)(,00juluSj01Su 10 ,min)(1ul第34页/共74页第三十五页，共75页。Dijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(minvuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i+1 代1i1i替i，并转2). 7,.,2 , 1,)(,00juluSj01Su 1)(1ul第35页/共74页第三十六页，共

22、75页。02Su Dijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(minvuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i+1 代1i1i替i，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul第36页/共74页第三十七页，共75页。03Su )(3ulDijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ，

23、 ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(minvuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i+1 代1i1i替i，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul第37页/共74页第三十八页，共75页。04Su )(3ulDijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(m

24、invuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i+1 代1i1i替i，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul第38页/共74页第三十九页，共75页。05Su )(3ulDijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(minvuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv

25、一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i+1 代1i1i替i，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul第39页/共74页第四十页，共75页。06Su )(3ulDijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(minvuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i

26、+1 代1i1i替i，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul4)(6ul第40页/共74页第四十一页，共75页。07Su Dijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(minvuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i+1 代1i1i替i，并转2). 7,.,2 , 1,)(,00juluS

27、j1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul第41页/共74页第四十二页，共75页。Dijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(minvuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i+1 代1i1i替i，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)

28、(6ul)()(min10ulvlSv8)(7ul第42页/共74页第四十三页，共75页。Dijkstra算法(sun f): 求G中从顶点u0到其余顶点的最短路. 1) 置 ，对 ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(minvuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i+1 代1i1i替i，并转2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2mi

29、n)(2ul2)(2ul第43页/共74页第四十四页，共75页。Dijkstra算法: 求G中从顶点u0到其余(qy)顶点的最短路. 1) 置 ，对 ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(minvuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i+1 代1i1i替i，并转2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ul第44页

30、/共74页第四十五页，共75页。Dijkstra算法: 求G中从顶点u0到其余(qy)顶点的最短路. 1) 置 ，对 ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 对每个 ，用iSv),()(),(minvuwulvlii代替 ，计算 ，并把达到这个最小值的)(vl)(minvliSv一个顶点记为 ，置1iu.11iiiuSS 3) 若 ，则停止；若 ，则用 i+1 代1i1i替i，并转2).第45页/共74页第四十六页，共75页。第46页/共74页第四十七页，共75页。定义 根据顶点v的标号l(v)的取值途径，使 到v0u的最短路中与v相邻的前一个顶点(dngdin)w，称

31、为v的先驱点，记为z(v), 即z(v)=w.先驱(xinq)点可用于追踪最短路径. 例5的标号过程也可按如下方式(fngsh)进行：首先写出左图带权邻接矩阵024782063446046340357630135102273201847210W因G是无向图，故W是对称阵第47页/共74页第四十八页，共75页。第48页/共74页第四十九页，共75页。1u0u6u7u2u4u3u5u第49页/共74页第五十页，共75页。Dijkstra算法：求G中从顶点u0到其余(qy)顶点的最短路设G为赋权有向图或无向图，G边上(bin shn)的权均均非负. 对每个顶点(dngdin)，定义两个标记（l(v)

32、，z(v)），其中: l(v) ：表从顶点u0到v的一条路的权 z(v) ：v的先驱点，用以确定最短路的路线.l(v)为从顶点u0到v的最短路的权算法的过程就是在每一步改进这两个标记，使最终S：具有永久标号的顶点集.输入: G的带权邻接矩阵 w(u,v)备用-将求最短路与最短路径结合起来:第50页/共74页第五十一页，共75页。算法(sun f)步骤：l(v)u0vl(u)uw(u,v)第51页/共74页第五十二页，共75页。首先(shuxin)写出带权邻接矩阵024782063446046340357630135102273201847210W例 求下图从顶点u0到其余(qy)顶点的最短路因

33、G是无向图，故W是对称(duchn)阵第52页/共74页第五十三页，共75页。第53页/共74页第五十四页，共75页。1u0u6u7u2u4u3u5u第54页/共74页第五十五页，共75页。 （I）求距离矩阵(j zhn)的方法.（II）求路径矩阵的方法.（III）查找最短路路径的方法. Floyd算法：求任意两顶点间的最短路. 举例说明第55页/共74页第五十六页，共75页。第56页/共74页第五十七页，共75页。第57页/共74页第五十八页，共75页。在建立(jinl)距离矩阵的同时可建立(jinl)路径矩阵R 第58页/共74页第五十九页，共75页。ivjv然后(rnhu)用同样的方法再

34、分头查找若：1av2av3avkav1bv2bvmbv第59页/共74页第六十页，共75页。第60页/共74页第六十一页，共75页。例 求下图中加权图的任意(rny)两点间的距离与路径. ,053142503330212044401210 )0(D,654321654321654321654321654321654321 )0(R第61页/共74页第六十二页，共75页。,053142503330212044401210 )0(D,min) 1() 1() 1()(kkjkikkijkijdddd插入(ch r)点 v1，得：,053132503330212043401210)1(D,65431

35、1654321654321654321154321654321 )1 (R矩阵中带“=”的项为经迭代比较以后(yhu)有变化的元素.第62页/共74页第六十三页，共75页。,min) 1() 1() 1()(kkjkikkijkijdddd插入(ch r)点 v2，得：,053132503330212043401210)1(D矩阵中带“=”的项为经迭代比较以后(yhu)有变化的元素.,05313250333021204534012510)2(D,654311654321654321654322154321654221 )2(R第63页/共74页第六十四页，共75页。,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D,654311654321654333654322153321653221 )3(R插入(ch r)点 v3，得：,05313250333021204534012510)2(D第64页/共74页第六十五页，共75页。,min) 1() 1() 1()(kkjkikkijkijdddd,053132