数学建模图论模型.pptx

不积硅步，无以至千里不积硅步，无以至千里-荀子荀子劝学劝学第1页/共74页1.几个引例2.基本概念1.1.基本概念基本概念3.最短路问题及算法4.简单应用第2页/共74页ABCD哥尼斯堡七桥示意图问题1:七桥问题 能否从任一陆地出发通过每座桥恰好一次而回到出发点？1.几个引例几个引例第3页/共74页七桥问题模拟图ABDC欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。第4页/共74页问题2:哈密顿圈（环球旅行游戏）十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？第6页/共74页问题3:四色问题 对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了。德摩尔根致哈密顿的信（1852年10月23日）我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。第7页/共74页问题4(关键路径问题)一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？第8页/共74页2.2.图论的基本概念图论的基本概念1)图的概念2)赋权图与子图3)图的矩阵表示4)图的顶点度5)路和连通第9页/共74页1)1)图的概念图的概念定义一个图G是指一个二元组(V(G),E(G)，其中:其中元素称为图G的顶点.组成的集合，即称为边集,其中元素称为边.定义图G的阶是指图的顶点数|V(G)|,用来表示；图的边的数目|E(G)|用来表示.也用来表示边是非空有限集，称为顶点集，1)2)E(G)是顶点集V(G)中的无序或有序的元素偶对表示图，简记 用第10页/共74页 定义 若一个图的顶点集和边集都是有限集，则称其为有限图.只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图.第11页/共74页 定义若若图图G中的边均为有序偶中的边均为有序偶对对,称G为有向边为无向边，称e连接和，顶点和称图.称边为有向边或弧,称是从连接，称为e的尾，称为e的头.若图G中的边均为无序偶对，称G为无向图.称为e的端点.既有无向边又有有向边的图称为混合图.第12页/共74页 常用术语1)边和它的两端点称为互相关联.2)与同一条边关联的两个端点称为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边.3)端点重合为一点的边称为环，端点不相同的边称为连杆.4)若一对顶点之间有两条以上的边联结，则这些边称为重边5)既没有环也没有重边的图，称为简单图第13页/共74页 常用术语常用术语6)任意两顶点都相邻的简单图,称为完全图.记为Kv.7)若，且X 中任意两顶点不，相邻，Y 中任意两顶点不相邻，则称为二部图或偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为完全二部图或完全偶图,记为(m=|X|,n=|Y|)8)图叫做星.二部图第14页/共74页2)2)2)2)赋权图与子图赋权图与子图 定义定义 若图若图 的每一条边的每一条边e 都都赋以赋以一个实数w(e)，称w(e)为边e的权，G 连同边上的权称为赋权图.定义设和是两个图.1)若,称是的一个子图,记 2)若，则称是的生成子图.3)若，且，以为顶点集，以两端点均在中的边的全体为边集的图的子图，称为的由导出的子图，记为.4)若 ，且 ，以 为边集，以 的端点集为顶点集的图的子图，称为的由导出的边导出的子图，记为.第15页/共74页 3)若，且，以为顶点集，以两端点均在中的边的全体为边集的图的子图，称4)若 ，且 ，以 为边集，以 的端点集为顶点集的图的子图，称为的由导出的边导出的子图，记为.为的由导出的子图，记为.第16页/共74页3)3)3)3)图的矩阵表示图的矩阵表示 邻接矩阵:1)对无向图，其邻接矩阵，其中：(以下均假设图为简单图).第17页/共74页2)对有向图,其邻接矩阵,其中：第18页/共74页其中：3)对有向赋权图,其邻接矩阵,对于无向赋权图的邻接矩阵可类似定义.第19页/共74页关联矩阵 1)对无向图，其关联矩阵,其中：第20页/共74页2)对有向图，其关联矩阵,其中：第21页/共74页 邻接矩阵 A=(aij)nn,例 写出右图的邻接矩阵解：图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示第22页/共74页 权矩阵A=(aij)nn 例 写出右图的权矩阵：解：图的矩阵表示图的矩阵表示第23页/共74页4)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的度或次数定理的个数为偶数推论任何图中奇点第24页/共74页5)5)路和连通路和连通定义1)无向图G的一条途径（或通道或链）是指一个有限非空序列，它的项交替 地为顶点和边，使得对，的端点是和,称W是从到的一条途径，或一条途径.整数k称为W的长.顶点和分别称为的起点和终点,而称为W的内部顶点.2)若途径W的边互不相同但顶点可重复，则称W为迹或简单链.3)若途径W的顶点和边均互不相同，则称W为路或路径.一条起点为,终点为的路称为路记为第25页/共74页定义 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，则定义为无穷大.第26页/共74页6)图G中任意两点皆连通的图称为连通图 7)对于有向图G，若，且有类似地，可定义有向迹，有向路和有向圈.头和尾，则称W为有向途径.例在右图中：途径或链：迹或简单链：路或路径：圈或回路：第27页/共74页例 一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。第28页/共74页解：用四维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)也是不允许的，图论的基本概念图论的基本概念第29页/共74页人在河西：（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）终止，得到有向图即是。图论的基本概念图论的基本概念第30页/共74页3 3最短路问题及算法最短路问题及算法最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.最短路的定义最短路问题的两种方法：Dijkstra和Floyd算法.1)1)求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路.2)求赋权图中任意两点间的最短路.第31页/共74页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).第32页/共74页1)1)赋权图中从给定点到其余顶点的最短赋权图中从给定点到其余顶点的最短路路假设G为赋权有向图或无向图，G边上的权均非负若，则规定最短路是一条路，且最短路的任一节也是最短路求下面赋权图中顶点u0到其余顶点的最短路第33页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第34页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第35页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第36页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第37页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第38页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第39页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第40页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第41页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第42页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第43页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第44页/共74页Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1 代替i，并转2).第45页/共74页第46页/共74页定义根据顶点v的标号l(v)的取值途径，使到v的最短路中与v相邻的前一个顶点w，称为v的先驱点，记为z(v),即z(v)=w.先驱点可用于追踪最短路径.例5的标号过程也可按如下方式进行：首先写出左图带权邻接矩阵因G是无向图，故W是对称阵第47页/共74页第48页/共74页第49页/共74页Dijkstra算法：求G中从顶点u0到其余顶点的最短路设G为赋权有向图或无向图，G边上的权均均非负.对每个顶点，定义两个标记（l(v)，z(v)），其中:l(v)：表从顶点u0到v的一条路的权 z(v)：v的先驱点，用以确定最短路的路线.l(v)为从顶点u0到v的最短路的权算法的过程就是在每一步改进这两个标记，使最终S：具有永久标号的顶点集.输入:G的带权邻接矩阵w(u,v)备用-将求最短路与最短路径结合起来:第50页/共74页算法步骤：l(v)u0vl(u)uw(u,v)第51页/共74页首先写出带权邻接矩阵例求下图从顶点u0到其余顶点的最短路因G是无向图，故W是对称阵第52页/共74页第53页/共74页第54页/共74页2)2)求赋权图中任意两顶点间的最短路求赋权图中任意两顶点间的最短路算法的基本思想（I）求距离矩阵的方法.（II）求路径矩阵的方法.（III）查找最短路路径的方法.Floyd算法：求任意两顶点间的最短路.举例说明第55页/共74页算法的基本思想算法的基本思想第56页/共74页（I I）求距离矩阵的方法）求距离矩阵的方法.第57页/共74页（II II）求路径矩阵的方法）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵R第58页/共74页（IIIIII）查找最短路路径的方法）查找最短路路径的方法.然后用同样的方法再分头查找若：第59页/共74页（IVIV）FloydFloyd算法：求任意两顶点间的最短算法：求任意两顶点间的最短路路.第60页/共74页例求下图中加权图的任意两点间的距离与路径.第61页/共74页插入点v1，得：矩阵中带“=”的项为经迭代比较以后有变化的元素.第62页/共74页插入点v2，得：矩阵中带“=”的项为经迭代比较以后有变化的元素.第63页/共74页插入点v3，得：第64页/共74页插入点v4，得：插入点v5，得：第65页/共74页插入点v6，得：第66页/共74页故从v5到v2的最短路为8由v6向v5追溯:由v6向v2追溯:所以从到的最短路径为：第67页/共74页学而时习之，不亦说乎学而时习之，不亦说乎-论语论语学而学而第68页/共74页4 4最短路问题的简单应用最短路问题的简单应用最短路问题的简单应用最短路问题的简单应用第69页/共74页返回第70页/共74页 选址问题-中心问题第71页/共74页S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7S(v3)=6,故应将消防站设在v3处.返回第72页/共74页 选址问题-重心问题返回第73页/共74页感谢您的观看！第74页/共74页