数学建模-司守奎04第4章--图与网络

基础部数学教研室第4章图与网络模型及方法数学建模算法与应用基础部数学教研室3/110数学建模图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22nnCH+的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈、近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学、生物遗传学、心理学、经济学、社会学等学科中。基础部数学教研室4/110数学建模图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来，问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。基础部数学教研室5/110数学建模图4.1哥尼斯堡七桥问题基础部数学教研室6/110数学建模4.1图的基本概念与数据结构4.1.1基本概念所谓的图，直观地讲就是在平面上n个点，把其中的一些点对用曲线或直线连接起来，不考虑点的位置与连线曲直长短，这样形成一个关系结构就是一个图。记成(,)GVE=，V是以上述点为元素的顶点集，E是以上述连线为元素的边集。如果各条边都加上方向，则称为有向图，否则称为无向图。如果有的边有方向，有的边无方向，则称为混合图。如果任两顶点间最多有一条边，且每条边的两个端点皆不重合的图，称为简单图。基础部数学教研室7/110数学建模如果图的两顶点间有边相连，则称此两顶点相邻，每一对顶点都相邻的图称为完全图，否则称为非完全图，完全图记为VK。若VXY=U，XYF=I，0XY坠（这里X表示顶点集X中元素的个数），且X中无相邻的顶点对，Y中亦然，则称图G为二分图；特别地，若对任意uXÎ，u与Y中每个顶点相邻，则称图G为完全二分图，记为,XYK。基础部数学教研室8/110数学建模设vVÎ是边eEÎ的端点，则称v与e相关联，与顶点v关联的边数称为该顶点的度，记为()dv，度为奇数的顶点称为奇顶点，度为偶数的顶点称为偶顶点。可以证明()()2vVGdvEÎ=å，即所有顶点的度数之和是边数的两倍，且由此可知奇顶点的总数是偶数。基础部数学教研室9/110数学建模设0112kkWveveev=L，其中ieEÎ，1ik＃，jvVÎ，0jk＃，ie与1iv-和iv关联，称W是图G的一条道路，k为路长，0v为起点，kv为终点；各边相异的道路称为迹；各顶点相异的道路称为轨道。若W是一轨道，可记为0(,)kPvv；起点与终点重合的道路称为回路；起点与终点重合的轨道称为圈，即对轨道0(,)kPvv，当0kvv=时成为一圈；图中任两顶点之间都存在道路的图，称为连通图。图中含有所有顶点的轨道称为Hamilton轨，闭的Hamilton轨称为Hamilton圈；含有Hamilton圈的图称为Hamilton图。基础部数学教研室10/110数学建模称两顶点,uv分别为起点和终点的最短轨道之长为顶点,uv的距离；在完全二分图,XYK中，X中两顶点之间的距离为偶数，X中的顶点与Y中的顶点的距离为奇数。赋权图是指每条边都有一个（或多个）实数对应的图，这个（些）实数称为这条边的权（每条边可以具有多个权）。赋权图在实际问题中非常有用。根据不同的实际情况，权数的含义可以各不相同。例如，可用权数代表两地之间的实际距离或行车时间，也可用权数代表某工序所需的加工时间等。基础部数学教研室11/110数学建模4.1.2图与网络的数据结构为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的2种主要表示方法：邻接矩阵表示法和稀疏矩阵表示法。在下面数据结构的讨论中，首先假设(,)GVE=是一个简单无向图，顶点集合1{,,}nVvv=L，边集1{,,}mEee=L，记||Vn=，||Em=。基础部数学教研室12/110数学建模1.邻接矩阵表示法邻接矩阵是表示顶点之间相邻关系的矩阵，邻接矩阵记作()ijnnWw´=，当G为赋权图时0.ijvvijvvijw¥ìïïï=íïïïî权值，当与之间有边时，或，当与之间无边时当G为非赋权图时，10.ijvvijvvijw=ìïïïíïïïî，当与之间有边时，，当与之间无边时采用邻接矩阵表示图，直观方便，通过查邻接矩阵元素的值可以很容易地查找图中任两个顶点iv和jv之间有无边，以及边上的权值。当图的边数m远小于顶点数n时，邻接矩阵表示法会造成很大的空间浪费。基础部数学教研室13/110数学建模2.稀疏矩阵表示法稀疏矩阵是指矩阵中零元素很多，非零元素很少的矩阵。对于稀疏矩阵，只要存放非零元素的行标、列标、非零元素的值即可，可以按如下方式存储（非零元素的行地址，非零元素的列地址），非零元素的值。在Matlab中无向图和有向图邻接矩阵的使用上有很大差异。对于有向图，只要写出邻接矩阵，直接使用Matlab的命令sparse命令，就可以把邻接矩阵转化为稀疏矩阵的表示方式。基础部数学教研室14/110数学建模对于无向图，由于邻接矩阵是对称阵，Matlab中只需使用邻接矩阵的下三角元素，即Matlab只存储邻接矩阵下三角元素中的非零元素。稀疏矩阵只是一种存储格式。Matlab中，普通矩阵使用sparse命令变成稀疏矩阵，稀疏矩阵使用full命令变成普通矩阵。基础部数学教研室15/110数学建模4.2最短路问题4.2.1两个指定顶点之间的最短路径问题如下，给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。构造赋权图(,,)GVEW=，其中顶点集1{,,}nVvv=L，这里1,,nvvL表示各个小城镇，E为边的集合，邻接矩阵()ijnnWw´=，这里ijw表示顶点iv和jv之间直通铁路的距离，若顶点iv和jv之间无铁路，则ijw=?。问题就是求赋权图G中指定的两个顶点00,uv间的具有最小权的路。这条路叫做00,uv间的最短路，它的权叫做00,uv间的距离，亦记作00(,)duv。基础部数学教研室16/110数学建模求最短路已有成熟的算法，如迪克斯特拉（Dijkstra）算法，其基本思想是按距0u从近到远为顺序，依次求得0u到G的各顶点的最短路和距离，直至0v（或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。基础部数学教研室17/110数学建模（1）令0()0lu=，对0vu¹，令()lv=?，00{}Su=，0i=。（2）对每个ivSÎ（\iiSVS=），用min{(),()()}iuSlvluwuvÎ+代替()lv，这里()wuv表示顶点u和v之间边的权值。计算min{()}ivSlvÎ，把达到这个最小值的一个顶点记为1iu+，令11{}iiiSSu++=U。（3）若||1iV=-，停止；若||1iV-，用1i+代替i，转（2）。算法结束时，从0u到各顶点v的距离由v的最后一次标号()lv给出。在v进入iS之前的标号()lv叫T标号，v进入iS时的标号()lv叫P标号。基础部数学教研室18/110数学建模例4.1某公司在六个城市126,,,cccL中有分公司，从ic到jc的直接航程票价记在下述矩阵的(,)ij位置上。（¥表示无直接航路），请帮助该公司设计一张城市1c到其他城市间的票价最便宜的路线图。050402510500152025150102040201001025252010055102525550轾¥犏犏¥犏犏ゥ犏犏犏犏¥犏犏¥臌基础部数学教研室19/110数学建模用矩阵nna´（n为顶点个数）存放各边权的邻接矩阵，行向量pb、1index、2index、d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量1;()0;iPpbiiP=ìïïíïïî当第顶点的标号已成为标号当第顶点的标号未成为标号2()indexi存放始点到第i顶点最短通路中第i顶点前一顶点的序号；()di存放由始点到第i顶点最短通路的值。求得1c到26,,ccL的最便宜票价分别为35，45，35，25，10。基础部数学教研室20/110数学建模4.2.2两个指定顶点之间最短路问题的数学规划模型假设有向图有n个顶点，现需要求从顶点1v到顶点nv的最短路。设()ijnnWw´=为邻接矩阵，其分量为,,,,ijvvvvEijijwÎ=¥ìïïíïïî边的权值其它决策变量为ijx，当1ijx=，说明弧ijvv位于顶点1v至顶点nv的最短路上；否则0ijx=。其数学规划表达式为minijijijvvEwxÎå，s.t.111,1,1,,0,1,,ijjinnijjijjvvEvvEixxinin==挝ì=ïïïï-=-=íïï¹ïïî邋10ijx=或.基础部数学教研室21/110数学建模例4.2在图4.2中，用点表示城市，现有12123,,,,,,ABBCCCD共7个城市。点与点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市A到城市D铺设一条天然气管道，请设计出最小长度管道铺设方案。图4.27个城市间的连线图求得最短铺设方案是铺设1111,,ABBCCD段，最短铺设长度为6。基础部数学教研室22/110数学建模例4.3（无向图的最短路问题）求图4.3中1v到11v的最短路。分析例4.2处理的问题属于有向图的最短路问题，本例是处理无向图的最短路问题，在处理方式上与有向图的最短路问题有一些差别，这里选择赋权邻接矩阵的方法编写LINGO程序。图4.3赋权无向图基础部数学教研室23/110数学建模与有向图相比较，在程序中只增加了一个语句@sum(cities(j):x(j,1))=0，即从顶点1离开后，再不能回到该顶点。求得的最短路径为1→2→5→6→3→7→10→9→11，最短路径长度为13。基础部数学教研室24/110数学建模4.2.3每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行1n-次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为3()On。第二种解决这一问题的方法是由Floyd,R.W.提出的算法，称之为Floyd算法。基础部数学教研室25/110数学建模对于赋权图0(,,)GVEA=，其中顶点集1{,,}nVvv=L，邻接矩阵1112121222012nnnnnnaaaaaaAaaa轾犏犏犏=犏犏犏臌LLMMLML，这里,vvijaijvvij=¥ìïïïíïïïî权值，当与之间有边时，，当与之间无边时（ij¹）0iia=，1,2,,in=L.对于无向图，0A是对称矩阵，ijjiaa=。基础部数学教研室26/110数学建模Floyd算法的基本思想是递推产生一个矩阵序列1,,,,knAAALL，其中矩阵kA的第i行第j列元素(,)kAij表示从顶点iv到顶点jv的路径上所经过的顶点序号不大于k的最短路径长度。计算时用迭代公式111(,)min((,),(,)(,))kkkkAijAijAikAkj---=+，k是迭代次数，,,1,2,,ijkn=L。最后，当kn=时，nA即是各顶点之间的最短通路值。基础部数学教研室27/110数学建模例4.4用Floyd算法求解例4.1。基础部数学教研室28/110数学建模4.3最小生成树问题4.3.1基本概念连通的无圈图叫做树，