数学建模-图论篇

1、涉及图论的历年数学建模题目2、图论简介3、图的定义和术语4、图的存储结构5、最短路径算法6图论的应用实例图论篇(1)图论方法在历年数学建模中的应用经常出现，下面总结如下表2、历年数学建模与图论方法有关题目年份题目解法93B足球队排名图论、层次分析、整数规划94A逢山开路图论、插值、动态规划94B锁具装箱问题图论、组合数学95B天车与冶炼炉的作业调度图论,动态规划、排队论、97B截断切割图论、组合优化98B灾情巡视的最佳路线图论、组合优化99B钻井布局0-1规划、图论00B管道订购图论，优化04A奥运会临时超市网点设计图论，组合优化07B公交车问题多目标规划、动态规划、图论、0-1规划11B交巡警服务平台的设置与调度0-1规划、计算机模拟、图论13B碎纸片的拼接复原最优Hamilton圈（即TSP）优化模型、图论、聚类分析GraphTheoryinMathematicalModeling2、图论简介现实生活中许多问题都可归结为由点和线组成的图形的问题，例如，铁路交通图，公路交通图，市区交通图，自来水管网系统，甚至电路图在研究某些问题时也可简化为由点和线组成的图形。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论就是研究这些由点和线组成的图形的问题。2图的定义和术语ABCDABCDE有向图G1无向图G2•结点或顶点：•有向边（弧）、弧尾或初始结点、弧头或终止结点ABAB•有向图：G1=（V1，{A1}）V1={A,B,C,D}A1={A,B,A,C,C,D,D,A}•结点或顶点：•无向边或边AB•无向图：G2=（V2，{A2}）V2={A,B,C,D,E}A2={(A,B),(A,C),(B,D),(B,E,(C,E),(D,E)}AB图的定义和术语ABCD无向图G2ABCDACABCD有向图G1的子图ABCDEABDEAABCDABCDE无向图G2的子图有向图G1图的定义和术语无向图的连通性ABCDE•路径：在无向图G=(V,{E})中由顶点v至v‘’的顶点序列。•回路或环：第一个顶点和最后一个顶点相同的路径。•简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。•连通：顶点v至v‘’之间有路径存在•连通图：无向图图G的任意两点之间都是连通的，则称G是连通图。•连通分量：极大连通子图FGIJLHMKABCDEHMFGIJLK无向图G无向图G的三个连通分量图的定义和术语有向图的连通性•路径：在有向图G=(V,{E})中由顶点v经有向边至v‘’的顶点序列。•回路或环：第一个顶点和最后一个顶点相同的路径。•简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。•连通：顶点v至v‘’之间有路径存在•强连通图：有向图图G的任意两点之间都是连通的，则称G是强连通图。•强连通分量：极大连通子图有向图G有向图G的两个强连通分量ABCDABCD图的定义和术语•生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环，但是含有n-1条边的图不一定是生成树ABCDEHMABCDEHM无向图G无向图G的生成树有向图的生成树：有若干个有向树组成，含有图中的全部顶点，但是构成若干个互不相交的有向树图的定义和术语•完全图：有n(n-1)/2条边的无向图。其中n是结点个数。•有向完全图：有n(n-1)条边的有向图。其中n是结点个数。•边的权值，边有权的图称之为网络。邻接点：边用顶点的无序偶对（vi,vj）来表示，称顶点vi和顶点vj互为邻接点•稠密图、稀疏图。若一个图接近完全图，称为稠密图；称边数很少的图为稀疏图•无向图结点的度:指依附于某顶点v的边数记为TD(v)•有向图结点的出度和入度:顶点v的入度是指以顶点为终点的弧的数目。记为ID(v)ABCDEHM无向图G1图的其它术语有向图G2ABCD有向图顶点v出度是指以顶点v为始点的弧的数目，记为OD(v)。有TD(v)=ID(v)＋OD(v)。n个顶点的图中顶点度和边的关系niivTDe1)(2图的存储结构图的四种常用的存储形式：数组表示法（邻接矩阵和加权邻接矩阵matrix）邻接表十字链表邻接多重表1、邻接矩阵和加权邻接矩阵（labeledadjacencymatrix）ABCD•无权值的有向图的邻接矩阵设有向图具有n个结点，则用n行n列的布尔矩阵A表示该有向图；并且A[i,j]=1,如果i至j有一条有向边；A[i,j]=0如果i至j没有一条有向边注意：A[i,i]=0。出度:i行之和。入度:j列之和。表示成右图矩阵01100000000110002021/2/411邻接矩阵表示法对求顶点的度很方便。在无向图中：顶点的度数=矩阵中对应该顶点的行或列中非零元素的个数。在有向图中：顶点的出度=矩阵中对应该顶点的行中非零元素的个数。顶点的入度=矩阵中对应该顶点的列中非零元素的个数。2021/2/412V1V3V2V4V1V3V2V4V1V2V3V4V10010V20001V30001V41000V1V2V3V4V10111V21001V31000V41100入度出度11112101度数3212图的存储结构1、邻接矩阵和加权邻接矩阵（labeledadjacencymatrix）（续）•无权值的无向图的邻接矩阵设无向图具有n个结点，则用n行n列的布尔矩阵A表示该无向图；并且A[i,j]=1,如果i至j有一条无向边；A[i,j]=0如果i至j没有一条无向边注意：A[i,i]=0。i结点的度:i行或i列之和。上三角矩阵或下三角矩阵。表示成右图矩阵0110010011100010100101110ABCDE图的存储结构1、邻接矩阵和加权邻接矩阵（labeledadjacencymatrix）（续）•有向图的加权邻接矩阵设有向图具有n个结点，则用n行n列的矩阵A表示该有向图；并且A[i,j]=a,如果i至j有一条有向边且它的权值为a。A[i,j]=无穷，如果i至j没有一条有向边。ABCD表示成右图矩阵∞ab∞∞∞∞b∞∞∞ba∞a∞aaabbb优点：判断任意两点之间是否有边方便，仅耗费O(1)时间。缺点：即使n2条边，也需内存n2/2单元，太多;仅读入数据耗费O(n2)时间，太长。ABCDABCD图的存储结构2、邻接表（adjacencylist）•设有向图或无向图具有n个结点，则用结点表、边表表示该有向图或无向图。•结点表：用数组或单链表的形式存放所有的结点。如果结点数n已知，则采用数组形式，否则应采用单链表的形式。•边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表。•优点：内存＝结点数＋边数•缺点：确定i--j是否有边，最坏需耗费O(n)时间。无向图同一条边表示两次边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。datafirstarc结点表中的结点的表示：•用数组data:结点的数据场，保存结点的数据值。firstarc:结点的指针场，给出自该结点出发的的第一条边的边结点的地址。图的存储结构2、邻接表（adjacencylist）datafirstarc结点表中的结点的表示：续•用单链表data:结点的数据场，保存结点的数据值。firstarc:结点的指针场，给出自该结点出发的的第一条边的边结点的地址。nextvex:结点的指针场，给出该结点的下一结点的地址。nextvexinfoadjvexnextarc边结点表中的结点的表示：info:边结点的数据场，保存边的权值等。adjvex:边结点的指针场，给出本条边依附的另一结点（非出发结点）的地址。nextarc:结点的指针场，给出自该结点出发的的下一条边的边结点的地址。图的存储结构2、邻接表（adjacencylist）•实例：ABCD无向图G2ABCDE向图G1ABCD12030123nullnullnullnulldatafirstarcadjvexnextvexAB1201234nulldatafirstarc03041412CDE43nullnullnullnullAdjvex指针场之值为相应结点数的组元素的下标!!!六条边却用了12个边结点!!!改进：建立邻接多重表寻找进入结点的边非常困难!!!改进：建立逆邻接表或十字链表adjvexnextvex图的存储结构2、邻接表（adjacencylist）•逆邻接表实例：ABCD有向图G1AB320123^l002CD^^^图的存储结构3、十字链表datafirstinfirstoutinfotailvexheadvex•边结点表中的结点的表示：•结点表中的结点的表示：data:结点的数据域，保存结点的数据值。firstin:结点的指针域，给出自该结点出发的的第一条边的边结点的地址。firstout:结点的指针域，给出进入该结点的第一条边的边结点的地址。info:边结点的数据域，保存边的权值等。hlinktlinktailvex:本条边的出发结点的地址。headvex:本条边的终止结点的地址。hlink:出发结点相同的边中的下一条边的地址。tlink:终止结点相同的边中的下一条边的地址。图的存储结构3、十字链表•实例：ABCD向图G10123ABCD01022220033331∧∧∧∧∧∧∧∧datafirstinfirstouttailvexheadvexhlinktlink•用途：用于有向图，查询进入结点和离开结点的边容易。图的存储结构4、邻接多重表datafirstedgemarkivexilink•边结点表中的结点的表示：•结点表中的结点的表示：data:结点的数据域，保存结点的数据值。firstedge:结点的指针域，给出自该结点出发的的第一条边的边结点的地址。info:边结点的数据域，保存边的权值等。mark:边结点的标志域，用于标识该条边是否被访问过。jvexinfoivex:本条边依附的一个结点的地址。ilink:依附于该结点（地址由ivex给出）的边中的下一条边的的地址。jlinkjvex:本条边依附的另一个结点的地址。jlink:依附于该结点（地址由jvex给出）的边中的下一条边的的地址。图的存储结构4、邻接多重表•实例：无向图G2•用途：用于无向图，边表中的边结点只需存放一次，节约内存。ABCDEAB01234datafirstedgeCDE012441310234∧∧∧∧markivexilinkjvexjlink∧2021/2/423练习：给出下图的1）邻接矩阵、2）邻接表和3）十字链表表表示ACBFED010000000000010010100000010100001010Edge012345ABCDEFDatafinfout^^^0103121425313454^^^^^^^^^1)2)邻接表要求出和入边两种2021/2/424（二）给出右图的邻接多重表ADCB01^0A1B2C3D23^020312^^GraphTheoryinMathematicalModeling5图的最短路径算法-Dijkstra算法最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.求解最短路问题的两种方法：Dijkstra和Floyd算法.(1)求赋权图中从给定点到其余顶点的最短路;(2)求赋权图中任意两点间的最短路.上级目录GraphTheoryinMathematicalModeling求赋权图中从给定点到其余顶点的最短路——Dijkstra算法解决上述问题的一个方法是由Dijkstra(迪杰斯特拉)于1959年提出的算法，此算法不仅能求出赋权图指定两点间的最短路，而且能求出从指定点到其余各顶点的最短路.目前它是求无负权图最短路的最好方法.Dijkstra算法是一种迭代算法，它依据的是一个重要而明显的性质：最短路是一条路，