数学建模5图论-课件

数学建模

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

---关于图模型在哥尼斯堡有条普莱格尔河,它有两条支流在城市中心汇合后流入波罗的海。这条河将城市分割成四块:A、C两个小岛和B、D两块陆地（如图）。问题的提出哥尼斯堡七桥问题七桥问题是发生在18世纪东普鲁土的哥尼斯堡的一个真实故事。ABCD3为通行方便，在四块陆地之间建了七座桥，每到节、假日或傍晚，都有许多居民和大学生来此散步。久而久之,人们发现并热衷于讨论这样一个问题:能否从四块陆地之一出发,走遍每座桥一次且仅一次然后回到出发地?自然有不少人作过实地尝试,但一直未能实现。ABCD1735年,有大学生写信把问题告诉了欧拉,请他帮助解决。欧拉从大家的失败中进行抽象的数学思考,从数学角度成功地解决了问题。4

问题分析与模型假设：

2.四块陆地可重复经历,至于陆地的大小、形状、质地等也与问题的本质无关，因而可视四块陆地为四个点A、B、C、D。

1.问题的本质是能否从一地无重复地一次走遍七桥,因而与所走过的桥的大小、形状、长短、曲直等均无关，而只要桥存在，因此不妨将其视为一条弧线ABCDABDC5

对四个陆地A、B、C、D，若其间有桥，则用一条弧线连接起来，有两座桥，则连两条不重合的弧线，便得到一个图，并称代表陆地的四个点为顶点，代表桥的弧线为边。

这样一来，能否从一地出发走遍七座桥一次且仅一次再回到出发点就变成了：能否从这个图上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。这就是众所周知的这个图能否“一笔画出”的问题。ABCDABDC6能否从这个图上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。7“一笔画出”能否从这个图上任一顶点出发，经过每个顶点一次且仅一次而回到出发顶点。旅行商问题能否从这个图选择尽量少的点，使得所有的其余点都和该点集有路径连接。覆盖问题-系统监控模型能否将图中点集分类，使得每一类点集都没有路径连接，最少需要分几类。支配集--仓库分区将该图中所有顶点用不同颜色表示，最少需要几种颜色。8“点着色将该图中所有边用不同颜色表示，最少需要几种颜色。边着色关键路径最大流、最小流问题2(哈密顿环球旅行问题):

十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）9问题3(四色问题):

对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.10问题4(关键路径问题):

一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.

这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？11一图的基本概念二三最短路问题及其算法四最小生成树问题图的矩阵表示12

数学建模-图论132023年7月26日

一、图的基本概念13

数学建模-图论142023年7月26日

一、图的基本概念图1图214

数学建模-图论152023年7月26日

一、图的基本概念

一个图会有许多外形不同的图解,下面两个图表示同一个图G=(V,E)的图解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.

15

数学建模-图论162023年7月26日

一、图的基本概念16

数学建模-图论172023年7月26日

一、图的基本概念次数为奇数顶点称为奇点，否则称为偶点。17

数学建模-图论182023年7月26日

一、图的基本概念常用d(v)表示图G中与顶点v关联的边的数目,

d(v)称为顶点v的度数.与顶点v出关联的边的数目称为出度，记作d

+(v)，与顶点v入关联的边的数目称为入度，记作d

-(v)。用N(v)表示图G中所有与顶点v相邻的顶点的集合.任意两顶点都相邻的简单图称为完全图.有n个顶点的完全图记为Kn。18

数学建模-图论192023年7月26日

一、图的基本概念几个基本定理：19若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图,记为G=(V,E,F

).

设G=(V,E)是一个图,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,则称v0v1…

vk是G的一条通路.

如果通路中没有相同的顶点,则称此通路为路径,简称路.始点和终点相同的路称为圈或回路.

一、图的基本概念数学建模-图论

数学建模-图论20顶点u与v称为连通的，如果存在u到v通路，任二顶点都连通的图称为连通图，否则，称为非连通图。极大连通子图称为连通分图。

连通而无圈的图称为树,常用T表示树.树中最长路的边数称为树的高，度数为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。设G是有向图，如果G的底图是树，则称G是有向树，也简称树。

一、图的基本概念

数学建模-图论21

一、图的基本概念(应用)

数学建模-图论用图论思想求解以下各题例1、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。22

一、图的基本概念(应用)

数学建模-图论解：用四维0-1向量表示（人，狼，羊，菜）的在西岸状态，（在西岸则分量取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)也是不允许的，23

一、图的基本概念(应用)

数学建模-图论人在河西：（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）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。24

一、图的基本概念(应用)

数学建模-图论例2、考虑中国象棋的如下问题：（1）下过奇数盘棋的人数是偶数个。（2）马有多少种跳法？（3）马跳出后又跳回起点，证明马跳了偶数步。（4）红方的马能不能在自己一方的棋盘上不重复的跳遍每一点，最后跳回起点？25

一、图的基本概念(应用)

数学建模-图论例3、证明：在任意6人的集会上，总有3人互相认识，或总有3人互相不认识。解：以顶点表示人，以边表示认识，得6个顶点的简单图G。问题：3人互相认识即G包含K3为子图，3人互相不认识即G包含（3,0）图为子图。26

一、图的基本概念(应用)

数学建模-图论27282023年7月26日一、图的基本概念(应用)

数学建模-图论（设备更新问题）某企业每年年初,都要作出决定,如果继续使用旧设备,要付维修费；若购买一台新设备,要付购买费.试制定一个5年更新计划,使总支出最少.

已知设备在每年年初的购买费分别为11,11,12,12,13.使用不同时间设备所需的维修费分别为5,6,8,11,18.28292023年7月26日求v1到v6的最短路问题.

一、图的基本概念(应用)

数学建模-图论29302023年7月26日从上图中容易得到v1到v6只有两条路：v1v3v6和v1v4v6.

而这两条路都是v1到v6的最短路.一、图的基本概念(应用)

数学建模-图论30邻接矩阵（结点与结点的关系）关联矩阵（结点与边的关系）路径矩阵（任意两结点之间是否有路径）可达性矩阵直达矩阵等等……二、图的矩阵表示

数学建模-图论311有向图的邻接矩阵

A=(aij)n×n

（n为结点数）

例1：写出右图的邻接矩阵：解：二、图的矩阵表示

数学建模-图论322有向图的权矩阵A=(aij)n×n

（n为结点数）

例2：写出右图的权矩阵：解：二、图的矩阵表示

数学建模-图论333有向图的关联矩阵A=(aij)n×m

（n为结点数m为边数）

有向图：无向图：

二、图的矩阵表示

数学建模-图论34例3：分别写出右边两图的关联矩阵解：分别为：

二、图的矩阵表示

数学建模-图论35

二、图的矩阵表示4应用实例

数学建模-图论

某航空公司在A,B,C,D四城市之间开辟了若干航线,如图所示表示了四城市间的航班图,如果从A到B有航班,则用带箭头的线连接A与B.问题:如何直观给出各个城市之间的航班情况问题:如果没有直接航班到达,需要转机,有几种转机方案问题:如果城市不止4个,有n个城市,能否快速给出直接路径以及需要转机方案.问题:过年回家火车路线如何设置，北京公交地铁倒车如何如何设置

百度地图36

二、图的矩阵表示

数学建模-图论数值表示两地之间航线的数目，1表示只有一条路径，2代表有两条路径37若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图,记为G=(V,E,F

).

设G=(V,E)是一个图,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,则称v0v1…

vk是G的一条通路.如果通路中没有相同的顶点,则称此通路为路径,简称路.对于赋权图，路的长度（即路的权）通常指路上所有边的权之和。最短路问题：求赋权图上指定点之间的权最小的路。

三、最短路问题及其算法

数学建模-图论38重要性质：若v0v1…

vm是G中从v0到vm的最短路,则对1≤k≤m,v0v1…

vk必为G中从v0到vk的最短路.即：最短路是一条路，且最短路的任一段也是最短路。

三、最短路问题及其算法

数学建模-图论39

设有给定连接若干城市的公路网，寻求从指定城市到各城市的最短路线。

2、应用实例：最短路问题

问题的数学模型:

三、最短路问题及其算法402023年7月26日

数学建模-图论40412023年7月26日

三、最短路问题及其算法

数学建模-图论41422023年7月26日

三、最短路问题及其算法

数学建模-图论42432023年7月26日

三、最短路问题及其算法

数学建模-图论例

求下图从顶点u1到其他顶点的最短路邻接矩阵为43442023年7月26日

三、最短路问题及其算法

数学建模-图论44452023年7月26日

三、最短路问题及其算法

数学建模-图论例

matlab程序road1.m运行结果如下：l=021736912z=1116254545462023年7月26日

三、最短路问题及其算法

数学建模-图论u1u2u3u4u5u6u7u8462023年7月26日

三、最短路问题及其算法

数学建模-图论作业：对下面的有向图求顶点v0到其余顶点的最短路。1445642537472023年7月26日

三、最短路问题及其算法

数学建模-图论求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；

Dijkstra标号算法只适用于全部权为非负情况。求非负赋权图上任意两点间的最短路，一般用Floyd算法.Floyd算法可以适用于有负权的情况，还能判断是否有负回路。这两种算法均适用于有向赋权图.482023年7月26日

三、最短路问题及其算法

数学建模-图论Floyd算法：求任意两顶点的最短路设A=(aij)n×n为赋权图G=(V,E,F)的权矩阵,dij表示从vi到vj点的距离,rij表示从vi到vj点的最短路中一个点的编号.

①赋初值.对所有i,j,dij=aij,rij=j.k=1.转向②.

②更新dij,rij.对所有i,j,若dik+dkj＜dij,则令dij=dik+dkj,rij=k,转向③;

③终止判断.若k=n终止;否则令k=k+1,转向②.

最短路线可由rij得到.492023年7月26日

三、最短路问题及其算法

数学建模-图论329724例

求如下加权图的任一两点间的最短距离和路径road2.mfloyd.m502023年7月26日

三、最短路问题及其算法

数学建模-图论329724例

matlab程序road2.mfloyd.m512023年7月26日

三、最短路问题及其算法

数学建模-图论作业求下列加权图中任意两点间的最短距离和路径68－523－37452532023年7月26日

三、最短路问题及其算法

数学建模-图论选址问题:在n个居民点v1,v2,…,vn中设置一银行.问设在哪个点,可使最大服务距离最小?若设两个银行,问设在哪两个点?

模型假设设各个居民点都有条件设置银行,并有路相连,且路长已知.

模型建立与求解用Floyd算法求出任意两个居民点vi,vj之间的最短距离,并用dij表示.53542023年7月26日

三、最短路问题及其算法

数学建模-图论求k,使

即若设置一个银行,则银行设在

vk点,可使最大服务距离最小.⑴设置一个银行,银行设在vi点的最大服务距离为54552023年7月26日

三、最短路问题及其算法

数学建模-图论⑵设置两个银行,假设银行设在vs,vt点使最大服务

距离最小.记则s,t满足：进一步,若设置多个银行呢？55562023年7月26日作业：

数学建模-图论1、一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要

将它们运过河去，但由于船小，他一次只能运三者之一过河。

显然，不管是狼和山羊，还是山羊和卷心菜，都不能在无人监

视的情况下留在一起。问摆渡人应怎样把它们运过河去？2、北京（Pe）、东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、

巴黎(Pa)各城市之间的航线距离如下表，请应用最短路方法，

给出北京到其他城市的最短路，并通过图的形式标出。56572023年7月26日

数学建模-图论

例系统监控模型:居民区如图所示,ei为街道,vi为交叉路口,计划在交叉路口安置消防设施,只有与路口相邻的街道才能使用它们.为使街道必要时都有消防设施使用,在那些路口安置设施最节约?覆盖集：KV(G),对任意eE，则e至少一顶属于K，则K为G一个

覆盖集；

若K是G的覆盖集，对与任意vK,K-{V}不是覆盖集。则K是G的极小覆盖集。含顶最少覆盖集为最小覆盖集。

最小覆盖集中所含顶数为图G的覆盖数。57582023年7月26日

数学建模-图论e1e4e3e2e5e6e7v1v2v3v4v5问题归结为求最小覆盖(1)建立关联矩阵e1e2e3e4e5e6e7v11001000v21100100v30110010v40011001v5000011158592023年7月26日

数学建模-图论e1e2e3e4e5e6e7v11001000v21100100v30110010v40011001v50000111e1e4

e5e7v11100v21010v40101v50011(3)划去v对应的行及1所在列

e4e7v110v411v501(2)寻含1最多的顶v归于K(例v3K)(4).在剩余矩阵内重复以上过程直至矩阵空K={v2v3v4}59

支配集：DV(G),若图G中任意顶vD，则v必与D内一顶相邻，则D为G的一个支配集。若D是G的覆盖集，若D的任意子集不是支配集。则D是G的极小支配集。含顶最少的支配集为最小支配集。最小支配集中所含顶数为图G的支配数。

例2:如图6个城镇v1v2v6建立通信系统,,从中选几座城镇建中心台站,要求它们与各城镇相邻,为减少造价使中心台站数目最少.请提供建立方案.若在造价最低的条件下,建两套通信中心,以备出故障时启用另一套请提供建立方案.v6v2v1v3v4v560归为求最小支配(1)写出邻接矩阵A,将主对角线元素全改为1.即A+E.v1v2v3v4v5v6v1111100v4111111v2110100v3101100v5000111v6000111(3)划去A+E中v对应的行及1所在列(2)寻含1最多的顶v归于D(例v4D)(4).在剩余矩阵内重复以上过程直至矩阵空

若建两套通信中心,可在A+E划去v4对应的行,在剩余矩阵(A+E)2中重复以上过程v1v2v3v4v5v6v1111100v2110100v3101100v5000111v600011161v5v6v200v300v511v611D={v1v5}

独立集：IV(G),I中任意两顶不相邻，则I为G的一个独立集。若I是G的独立集，对与任意uV(G),I{u}不是独立集。则I是G的极大独立集。含顶最多的独立集为最大独立集。最大独立集中所含顶数为图G的独立数。定理：K为极小覆盖V－K为极大独立集。极大独立集必为极小支配集,反之不成立.62

例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)不能放在一起,公司必须把仓库分成若干个区,以便把不相容的制品分开,问至少分几个区,怎样存放才能保证安全.

以顶vavb

vg表示7种化学制品,在不相容制品间连边得图Gvfvavbvcvdvgve归为求最大独立集(也可用顶点着色)先求最小覆盖K1,则S1=V-K1为一个最大独立集.再求最小覆盖V-S1,最大独立集S2.再求最小覆盖V-S1-S2,最大独立集S3..63问题归结为求最小覆盖(1)建立关联矩阵(2