数学建模图论模型省名师优质课获奖课件市赛课一等奖课件

数学建模图论模型(1)数学与统计学院李书选

shuxuanli@126.com/07/17第1页不积硅步，无以至千里--荀子·劝学第2页1.几个引例2.基本概念

1.基本概念3.最短路问题及算法

4.简单应用

第3页ABCD哥尼斯堡七桥示意图问题1:七桥问题

能否从任一陆地出发经过每座桥恰好一次而回到出发点？1.几个引例第4页七桥问题模拟图ABDC欧拉指出：假如每块陆地所连接桥都是偶数座，则从任一陆地出发，必能经过每座桥恰好一次而回到出发地。第5页

莱昂哈德·欧拉(LeonhardEuler，1707.4.5-1783.9.18)瑞士数学家和物理学家。他被称为历史上最伟大两位数学家之一（另一位是卡尔·弗里德里克·高斯）。欧拉出生于瑞士，在那里受教育。他是一位数学神童。作为数学教授，他先后任教于圣彼得堡(1727-1741)和柏林，尔后再返圣彼得堡(1766)。欧拉一生很虔诚。然而，那个广泛流传传说却不是真。传说中说到，欧拉在叶卡捷琳娜二世宫廷里，挑战德尼·狄德罗：“先生，(a+b)n/n

=

x；所以上帝存在，这是回答！”欧拉离世也很尤其：听说当初正是下午茶时间，正在逗孙儿玩时候，被一块蛋糕卡在喉头窒息而死。欧拉是第一个使用“函数”一词来描述包含各种参数表示式人，比如：y=F(x)(函数定义由莱布尼兹在1694年给出)。他是把微积分应用于物理学先驱者之一。欧拉是有史以来最多产数学家，他全集共计75卷。欧拉实际上支配了18世纪数学，对于当初新创造微积分，他推导出了很多结果。在他生命最终7年中，欧拉双目完全失明，尽管如此，他还是以惊人速度产出了生平二分之一著作。小行星欧拉是为了纪念欧拉而命名。莱昂哈德·欧拉第6页问题2:哈密顿圈（环球旅行游戏）十二面体20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最终回到出发点？第7页问题3:四色问题对任何一张地图进行着色，两个共同边界国家染不一样颜色，则只需要四种颜色就够了。德·摩尔根致哈密顿信（1852年10月23日）

我一位学生今天请我解释一个我过去不知道，现在仍不甚了了事实。他说假如任意划分一个图形并给各部分着上颜色，使任何含有公共边界部分颜色不一样，那么需要且仅需要四种颜色就够了。下列图是需要四种颜色例子（图1）。……第8页问题4(关键路径问题)

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

这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度要害工序是哪几个？

第9页2.图论基本概念1)图概念2)赋权图与子图3)图矩阵表示4)图顶点度5)路和连通第10页1)图概念

定义

一个图G是指一个二元组(V(G),E(G))，其中:其中元素称为图G顶点.组成集合，即称为边集,其中元素称为边.

定义图G阶是指图顶点数|V(G)|,用来表示；图边数目|E(G)|用来表示.也用来表示边是非空有限集，称为顶点集，1)2)

E(G)是顶点集V(G)中无序或有序元素偶对表示图，简记用第11页

定义若一个图顶点集和边集都是有限集，则称其为有限图.只有一个顶点图称为平凡图，其它全部图都称为非平凡图.第12页

定义若图G中边均为有序偶对,称G为有向边为无向边，称e连接和，顶点和称图.称边为有向边或弧,称是从连接，称为e尾，称为e头.若图G中边均为无序偶对，称G为无向图.称为e端点.现有没有向边又有有向边图称为混合图.第13页

惯用术语1)边和它两端点称为相互关联.2)与同一条边关联两个端点称为相邻顶点，与同一个顶点点关联两条边称为相邻边.3)端点重合为一点边称为环，端点不相同边称为连杆.4)若一对顶点之间有两条以上边联结，则这些边称为重边．5)既没有环也没有重边图，称为简单图．第14页

惯用术语6)任意两顶点都相邻简单图,称为完全图.记为Kv.7)若，

，且X中任意两顶点不，

相邻，Y中任意两顶点不相邻，则称为二部图或偶图；若X中每一顶点皆与Y中一切顶点相邻,称为完全二部图或完全偶图,记为(m=|X|,n=|Y|)．8)图叫做星.二部图第15页2)赋权图与子图

定义若图每一条边e都赋以一个实数w(e)，称w(e)为边e权，G连同边上权称为赋权图.

定义设和是两个图.1)若,称是一个子图,记2)若，，则称是生成子图.

3)若，且，以为顶点集，以两端点均在中边全体为边集图子图，称为由导出子图，记为.4)若，且，以为边集，以端点集为顶点集图子图，称为由导出边导出子图，记为.第16页3)若，且，以为顶点集，以两端点均在中边全体为边集图子图，称4)若，且，以为边集，以端点集为顶点集图子图，称为由导出边导出子图，记为.为由导出子图，记为.第17页3)图矩阵表示

邻接矩阵:1)对无向图，其邻接矩阵，其中：(以下均假设图为简单图).第18页2)对有向图,其邻接矩阵,其中：第19页其中：3)对有向赋权图,其邻接矩阵,对于无向赋权图邻接矩阵可类似定义.第20页关联矩阵1)对无向图，其关联矩阵,其中：第21页2)对有向图，其关联矩阵,其中：第22页⑴

邻接矩阵

A=(aij)n×n,例写出右图邻接矩阵解：图矩阵表示第23页⑵权矩阵A=(aij)n×n例写出右图权矩阵：解：图矩阵表示第24页4)图顶点度定义1)在无向图G中，与顶点v关联边数目(环算两次),称为顶点v度或次数，记为d(v)或dG(v).称度为奇数顶点为奇点，度为偶数顶点为偶点.2)在有向图中，从顶点v引出边数目称为顶点

v出度，记为d+(v)，从顶点v引入边数目称为

v入度，记为d-(v).称d(v)=d+(v)+d-(v)为顶点v

度或次数．定理个数为偶数．推论任何图中奇点第25页5)路和连通定义1)无向图G一条路径（或通道或链）是指一个有限非空序列，它项交替

地为顶点和边，使得对，端点是和,称W是从到一条路径，或一条路径.整数k称为W长.顶点和分别称为起点和终点,而称为W内部顶点.2)若路径W边互不相同但顶点可重复，则称W为迹或简单链.3)若路径W顶点和边均互不相同，则称W为路或路径.一条起点为,终点为路称为路记为第26页定义1)路径中由相继项组成子序列称为路径W节.

2)起点与终点重合路径称为闭路径.

3)起点与终点重合路称为圈(或回路)，长为k圈称为k阶圈，记为Ck.

4)若在图G中存在(u,v)路，则称顶点u和v在图G中连通.

5)若在图G中顶点u和v是连通，则顶点u和v之之间距离d(u,v)是指图G中最短(u,v)路长；若没没有路连接u和v，则定义为无穷大.第27页

6)图G中任意两点皆连通图称为连通图．

7)对于有向图G，若，且有类似地，可定义有向迹，有向路和有向圈.头和尾，则称W为有向路径.例在右图中：路径或链：迹或简单链：路或路径：圈或回路：第28页例一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，因为船小，一次只能带一物过河，而且，狼与羊，羊与菜不能独处，给出渡河方法。第29页解：用四维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)也是不允许，图论基本概念第30页人在河西：（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）终止，得到有向图即是。图论基本概念第31页3．最短路问题及算法最短路问题是图论应用基本问题，很多实际问题，如线路布设、运输安排、运输网络最小费用流等问题,都可经过建立最短路问题模型来求解.最短路定义最短路问题两种方法：Dijkstra和Floyd算法.1)求赋权图中从给定点到其余顶点最短路.2)求赋权图中任意两点间最短路.第32页

2)在赋权图G中，从顶点u到顶点v含有最小权定义1)若H是赋权图G一个子图，则称H各边权和为H权.类似地，若称为路P权．若P(u,v)是赋权图G中从u到v路,称路P*(u,v)，称为u到v最短路．

3)把赋权图G中一条路权称为它长，把(u,v)路最小权称为u和v之间距离，并记作d(u,v).第33页1)赋权图中从给定点到其余顶点最短路假设G为赋权有向图或无向图，G边上权均非负．若，则要求最短路是一条路，且最短路任一节也是最短路．求下面赋权图中顶点u0到其余顶点最短路．第34页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第35页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第36页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第37页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第38页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第39页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第40页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第41页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第42页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第43页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第44页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第45页Dijkstra算法:求G中从顶点u0到其余顶点最短路.

1)置，对，，且.

2)对每个，用代替，计算，并把到达这个最小值一个顶点记为，置

3)若，则停顿；若，则用i+1代替i，并转2).第46页第47页定义依据顶点v标号l(v)取值路径，使到v最短路中与v相邻前一个顶点w，称为v先驱点，记为z(v),即z(v)=w.先驱点可用于追踪最短路径.例5标号过程也可按以下方式进行：首先写出左图带权邻接矩阵因G是无向图，故W是对称阵．第48页第49页第50页Dijkstra算法：求G中从顶点u0到其余顶点最短路设G为赋权有向图或无向图，G边上权均均非负.对每个顶点，定义两个标识（l