《第二章节图论模型幻灯片》由会员分享，可在线阅读，更多相关《第二章节图论模型幻灯片（90页珍藏版）》请在金锄头文库上搜索。
1、数学建模简明教程,国家精品课程,第二章 图论模型,一、问题引入与分析,二、图论的基本概念,三、最短路问题及算法,四、最小生成树及算法,五、旅行售货员问题,六、模型建立与求解,1. 98年全国大学生数学建模竞赛B题“最佳灾,今年(1998年)夏天某县遭受水灾. 为考察灾情、,组织自救，县领导决定，带领有关部门负责人到,全县各乡（镇）、村巡视. 巡视路线指从县政府,所在地出发，走遍各乡（镇）、村，又回到县政,府所在地的路线.,情巡视路线”中的前两个问题是这样的：,一、问题引入与分析,1）若分三组（路）巡视，试设计总路程最,短且各组尽可能均衡的巡视路线.,2）假定巡视人员在各乡（镇）停留时间T=2,
2、小时，在各村停留时间t=1小时，汽车行驶速度V,=35公里/小时. 要在24小时内完成巡视，至少应分,几组；给出这种分组下最佳的巡视路线.,公路边的数字为该路段的公里数.,2.问题分析：,本题给出了某县的公路网络图，要求的是在不,同的条件下，灾情巡视的最佳分组方案和路线.,将每个乡（镇）或村看作一个图的顶点，各乡,镇、村之间的公路看作此图对应顶点间的边，各,次再回到点O，使得总权（路程或时间）最小.,条公路的长度（或行驶时间）看作对应边上的权，,所给公路网就转化为加权网络图，问题就转化图论,中一类称之为旅行售货员问题，即在给定的加权网,络图中寻找从给定点O出发，行遍所有顶点至少一,如第一问是三
3、个旅行售货员问题，第二问是四,本题是旅行售货员问题的延伸,-多旅行售货员问题.,本题所求的分组巡视的最佳路线，也就是m条,众所周知，旅行售货员问题属于NP完全问题，,显然本问题更应属于NP完全问题. 有鉴于此，,经过同一点并覆盖所有其他顶点又使边权之和达,到最小的闭链（闭迹）.,个旅行售货员问题.,即求解没有多项式时间算法.,一定要针对问题的实际特点寻找简便方法，想找到,解决此类问题的一般方法是不现实的，对于规模较,大的问题可使用近似算法来求得近似最优解.,二、图论的基本概念,1) 图的概念,2) 赋权图与子图,3) 图的矩阵表示,4) 图的顶点度,5) 路和连通,定义 一个图G是指一个二元组
4、(V(G),E(G)，其中:,其中元素称为图G的顶点.,组成的集合，即称为边集,其中元素称为边.,2) E(G)是顶点集V(G)中的无序或有序的元素偶对,1) 图的概念,定义 若一个图的顶点集和边集都是有限集，则称,其为有限图. 只有一个顶点的图称为平凡图，其他的,所有图都称为非平凡图.,定义若图G中的边均为有序偶对(vi,vj)，称G为有向,图. 称边 为有向边或弧,称 是从,连接 , 称 为e的尾， 称 为e的头.,若图G中的边均为无序偶对 ，称G为无向图.称,为e的端点.,边 为无向边，称e连接 和 ，顶点 和 称,既有无向边又有有向边的图称为混合图.,常用术语,1) 边和它的两端点称为
5、互相关联.,2)与同一条边关联的两个端点称,为相邻的顶点，与同一个顶点,点关联的两条边称为相邻的边.,3) 端点重合为一点的边称为环，,端点不相同的边称为连杆.,4) 若一对顶点之间有两条以上的边联结，则这些边,称为重边,5) 既没有环也没有重边的图，称为简单图,常用术语,6) 任意两顶点都相邻的简单图,称为完全图. 记为Kv.,7) 若 ， ，且X 中任意两顶点不,相邻，Y 中任意两顶点不相邻，则称为二部图或,偶图；若X中每一顶点皆与Y 中一切顶点相邻,称,为完全二部图或完全偶图,记为 (m=|X|,n=|Y|),8) 图 叫做星.,定义 若图G=(V(G),E(G) 的每一条边e 都赋以,
6、一个实数w(e)，称w(e)为边e的权，G 连同边上的权,称为赋权图.,定义 设 和 是两个图.,1) 若 ,称 是 的一个子图,记,2) 若 ， ，则称 是 的生成子图.,3) 若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,为 的由 导出的子图，记为 .,4) 若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的由 导出的,边导出的子图,记为 .,2) 赋权图与子图,3) 若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,4) 若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的由 导出的,边导出的子
7、图,记为 .,为 的由 导出的子图，记为 .,1) 对无向图 ，其邻接矩阵 ，其中：,3) 图的矩阵表示,2) 对有向图 ,其邻接矩阵 ,其中：,其中：,3) 对有向赋权图 ,其邻接矩阵 ,对于无向赋权图的邻接矩阵可类似定义.,1) 对无向图 ，其关联矩阵 ,其中：,关联矩阵,2) 对有向图 ，其关联矩阵 ,其中：,定义 1) 在无向图G中，与顶点v关联的边的数目(环,算两次),称为顶点v的度或次数，记为d(v)或 dG(v).,称度为奇数的顶点为奇点，度为偶数的顶点为偶点.,2) 在有向图中，从顶点v引出的边的数目称为顶点,v的出度，记为d+(v)，从顶点v引入的边的数目称为,v的入度，记为
8、d -(v). 称d(v)= d+(v)+d -(v)为顶点v的,度或次数,定理,的个数为偶数,推论 任何图中奇点,4) 图的顶点度,定义1) 无向图G的一条途径（或通道或链）是指,一个有限非空序列 ，它的项交替,地为顶点和边，使得对 ， 的端点是 和 ,称W是从 到 的一条途径，或一条 途径.,整数k称为W的长. 顶点 和 分别称为起点和终点,而 称为W的内部顶点.,2) 若途径W的边互不相同但顶点可重复，则称W,为迹或简单链.,3) 若途径W的顶点和边均互不相同，则称W为路,或路径. 一条起点为 ,终点为 的路称为,路记为,5) 路和连通,定义,1) 途径 中由相继项构成子序列,称为途径W
9、的节.,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，则定义为无穷大.,6) 图G中任意两点皆连通的图称为连通图,类似地，可定义有向迹，有向路和有向圈.,例 在右图中：,途径或链：,迹或简单链：,路或路径：,圈或回路：,三、最短路问题及算法,最短路问题是图论应用的基本问题，很多实际,问题，如线路的布设、运输安排、运输网络最小费,
10、用流等问题,都可通过建立最短路问题模型来求解.,最短路的定义,最短路问题的两种方法：Dijkstra和Floyd算法 .,1) 求赋权图中从给定点到其余顶点的最短路.,2) 求赋权图中任意两点间的最短路.,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).,1)求赋权图中从给定点到其余顶点的最短路,解决上述问
11、题的一个方法是由Dijkstra于1959,年提出的算法，此算法不仅能求出赋权图指定两点,最短路.目前它是求无负权图最短路的最好方法.,间的最短路，而且能求出从指定点到其余各顶点的,中从 到 的最短路，则 必为从 到,的最短路，则称 是 的先驱点,记为 ,它可用于追踪最短路的路径.,最短路是一条路，且最短路的任一节也是最短路,假设G为赋权有向图或无向图，G边上的权均非,负若 ，则规定,求下面赋权图G中顶点v0到其余顶点的最短路,输入：图G的带权邻接矩阵W.,Dijkstra算法: 求G中从顶点 到其余顶点的最短路.,对每个顶点，定义两个标记（l(v),t(v)），其中:,l(v)表示从顶点到的
12、一条路的权,t(v)表示的先驱点，它可用以确定最短路的路径.,算法的过程就是在每一步改进这两个标记(l(v),t(v),使最终l(v)为从顶点v0到v的最短路的权,S：具有永久标号的顶点集.,Dijkstra算法步骤:,用上述算法求出的l(v)就是v0到v的最短路的权,(1) 初始化操作:置S=v0,l(v0)=0,对每个 ,令,(2)设v*是使l(v)取最小值的 中的顶点，即,，则令 ， .,若 ，停止. 否则，转（3）.,(3)更新l(v)、t(v)：对每个 ，若l(v),l(u)+w(u,v), 则令l(v)=l(u)+w(u,v),转(2) .,从v的先驱点标记t(v)追溯到v0, 就
13、得到v0到v的最短,路的路径.,(1) 初始化操作:置S=v0,l(v0)=0 ,对每个,令,停止. 否则，转（3）.,则令 ， .若 ,(3)更新l(v) 、t(v) :对每个 ,若l(v) l(u)+w(u,v),则令l(v)=l(u)+w(u,v),转(2) .,(2)设v*是使l(v)取最小值的 中的顶点，即,(2)设v*是使l(v)取最小值的 中的顶点,即,置S=v0,l(v0)=0,方框把0框起来.,给与v0相邻的顶点,分别标以l(v1)=,w(v0v1)=w011,l(v2)=2, l(v4)=7,l(v6)=4, l(v7)=8.,v1, v2, v4, v6, v7,其余顶点
14、均标以 ,即l(v3)= , l(v5)= .,(1) 初始化操作:置S=v0,l(v0)=0 ,对每个,令,停止. 否则，转（3）.,则令 ， .若 ,(3)更新l(v) 、t(v) :对每个 ,若l(v) l(u)+w(u,v),则l(v)=l(u)+w(u,v),转(2) .,(2)设v*是使l(v)取最小值的 中的顶点，即,(2)设v*是使l(v)取最小值的 中的顶点,即,对每个,记t(v)=v0 ,即它们的,先驱点均为v0。在,中取标号最小者l(v1)=1.,用方框把1框起来.,令,(1) 初始化操作:置S=v0,l(v0)=0 ,对每个,令,停止. 否则，转（3）.,则令 ， .若 ,(3)更新l(v) 、t(v) :对每个 ,若l(v) l(u)+w(u,v),则l(v)=l(u)+w(u,v),转(2) .,(2)设v*是使l(v)取最小值的 中的顶点，即,的算法步骤(3)重新,(2)设v*是使l(v)取最小值的 中的顶点,即,令,用Dijkstra,的标号l(v)、t(v) .经计,改进顶点,算只有v3满足条件:,则给v3标以l(v3)=4.,
