10数模图论方法

2021/8/212021/8/22数学建模中的图论方法数学建模中的图论方法一、图论基本概念一、图论基本概念二、算法的概念二、算法的概念三、图论问题及其算法列举三、图论问题及其算法列举参考资料：参考资料：数学实验数学实验 重庆大学数学系编重庆大学数学系编 科学出版社科学出版社20002000年出版年出版四、图论常用算法简介四、图论常用算法简介2021/8/23一、图论基本概念一、图论基本概念顶点顶点（Vertex）边边（Edge）欧拉（欧拉（Euler）图图G：由：由顶点顶点和和边边（连接（连接两个两个顶点之间的线）组成，记做顶点之间的线）组成，记做G（V，E），），其中其中V为为G中所有顶点的集合，中所有顶点的集合，E为为G中所有边的集合。中所有边的集合。Konigsberg 七桥问题七桥问题2021/8/24点与边的关联点与边的关联(incident)点与点的相邻（点与点的相邻（adjacent）边与边的相邻边与边的相邻 边的端点（边的端点（end vertices）环环(loop)重边重边(multi edge)简单图简单图(simple graph)顶点顶点v的度的度(degree)：d(v)=顶点顶点v 所关联的边的数目（环边计两次）所关联的边的数目（环边计两次）一些概念和术语一些概念和术语图的顶点数图的顶点数 （图的阶）、边数（图的阶）、边数 2021/8/25无向图与有向图无向图与有向图e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9123456123456789(,),GV EVv vvvvvEe e e e e e e e e 123456123456789(,),DV EVv vvvvvEe e e e e e e e e 2021/8/26图的数学表示：邻接矩阵（图的数学表示：邻接矩阵（adjacency matrixadjacency matrix）A 1211112122122212vvvvvvvaaavaaavaaa():ijijA GaGvv为为无无向向图图 中中连连接接顶顶点点 和和 的的边边的的个个数数():ijijA DaDvv为为有有向向图图 中中以以顶顶点点 为为起起点点和和顶顶点点 为为 终终点点的的边边的的个个数数用用顶顶点点与与边边的的关关联联关关系系关关联联矩矩阵阵：来来表表示示图图2021/8/27无向图的邻接矩阵无向图的邻接矩阵022100200100200100()111110000100000000()A GA G 是是对对称称矩矩阵阵e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9123456123456789(,),GV EVv vvvvvEe e e e e e e e e 2021/8/28有向图的邻接矩阵有向图的邻接矩阵011100100100000000()001110000000000000()A DA D 一一般般不不是是对对称称矩矩阵阵123456123456789(,),DV EVv vvvvvEe e e e e e e e e e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e92021/8/29()()chainwalk链链或或途途径径：图图中中顶顶点点和和边边交交替替出出现现的的序序列列()trail迹迹：边边不不重重复复的的链链称称为为迹迹链、迹、路、回、圈链、迹、路、回、圈()path路路：顶顶点点不不重重复复的的链链称称为为路路或或轨轨简简单单图图中中的的路路可可以以只只用用顶顶点点来来表表示示()()closed trailcircuit回回（闭闭迹迹）：两两个个端端点点（起起点点和和终终点点）相相同同 的的迹迹，也也称称为为回回路路()cycle圈圈：两两个个端端点点（起起点点和和终终点点）相相同同的的路路()length链链的的长长度度：链链中中边边的的个个数数2021/8/210无向图中的无向图中的链、迹、路、回、圈链、迹、路、回、圈e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e91 122143413495v e v e v e v e v e v e v1 122143513495v e v e v e v e v e v e v1 126495v e v e v e v1 12214351v e v e v e v e v1 126431v e v e v e v2021/8/211加权图、带权邻接矩阵加权图、带权邻接矩阵()ew ee对对图图中中的的每每条条边边 都都赋赋以以一一个个实实数数，称称之之为为边边 的的权权。067.560107.506.9106.9017170 带带权权邻邻接接矩矩阵阵以下开始只考虑简单图！以下开始只考虑简单图！2021/8/212加权图的数学表示：边权矩阵加权图的数学表示：边权矩阵112342344567.5106.9172021/8/213完全图、竞赛图完全图、竞赛图任两个顶点间有且只有一条边任两个顶点间有且只有一条边有向的完全图有向的完全图2021/8/214二部图、连通图、树二部图、连通图、树顶点分为两部分顶点分为两部分任两点间有路任两点间有路无圈连通图无圈连通图2021/8/215子图、生成树、最小生成树子图、生成树、最小生成树连通图连通图v6v5v2v3v4v1v6v5v2v3v4v1生成树生成树最小生成树：加权图的权最小的生成树最小生成树：加权图的权最小的生成树2021/8/216k-k-正则图，最大独立集正则图，最大独立集k-k-正则图：每个顶点的度数相同，均为正则图：每个顶点的度数相同，均为k k独立集：图的一个顶点集，集中任意两个独立集：图的一个顶点集，集中任意两个顶点均不相邻（无边相连）。顶点均不相邻（无边相连）。最大独立集：图的一个顶点集，集中任意两最大独立集：图的一个顶点集，集中任意两个顶点均不相邻（无边相连），但不属于该个顶点均不相邻（无边相连），但不属于该集的图的顶点，至少与该集中一点相邻。集的图的顶点，至少与该集中一点相邻。2021/8/217GG图图 的的一一个个匹匹配配：的的一一个个边边的的集集合合，其其中中任任意意两两条条边边无无公公共共顶顶点点。GGG图图的的完完备备匹匹配配：的的一一个个匹匹配配，其其中中边边的的顶顶点点包包括括了了图图的的所所有有顶顶点点图的匹配，完备匹配图的匹配，完备匹配2021/8/218EulerEuler图、图、HamiltonHamilton图图EulerEuler图：有经过每个顶点和每条边的回（闭迹）图：有经过每个顶点和每条边的回（闭迹）HamiltonHamilton图：有经过每个顶点的圈（闭路）图：有经过每个顶点的圈（闭路）2021/8/219 一个算法就是解决某一特定问题的方法，一个算法就是解决某一特定问题的方法，是一系列确定步骤，它必须在有限的时间内终止。是一系列确定步骤，它必须在有限的时间内终止。表述一个算法一般有两种方式表述一个算法一般有两种方式（1 1）步骤描述；步骤描述；（2 2）框图。框图。二、算法的概念二、算法的概念2021/8/220例例 求正整数求正整数m,n的最大公因子的的最大公因子的Euclid算法算法：Step1:求余数求余数m除以除以n，令，令r为所得的余数为所得的余数(0=rmaxn maxn=number(i)endend记 T(n)=c1+c2n 为这个算法的时间复杂度。通常记T(n)=O(n).2021/8/223时间复杂度分别是时间复杂度分别是O(1),O(n),O(nO(1),O(n),O(n2 2)。例：对下面三个简单的程序段，求时间复杂度。例：对下面三个简单的程序段，求时间复杂度。1)x=x+12)for i=1:n x=x+1 end3)for i=1:n for j=1:n x=x+1 end end2021/8/224典型算法的执行时间时间复杂度n2n32nn!计算时间1/64秒2秒274世纪5*2662世纪n=128时各典型算法的执行时间2021/8/225典型算法的处理规模算法时间复杂度一小时能处理的实例规模提高速度210倍一小时能处理的实例规模A1nN11024N1A2n2N232N2A32nN3N3+10A48nN4N4+3.32021/8/226P P、NPNP、NPCNPC判定问题：其答案不是判定问题：其答案不是“是是”就是就是“否否”的问题的问题P：已有多项式时间算法的判定问题：已有多项式时间算法的判定问题NP：已有指数时间算法的判定问题，包括：已有指数时间算法的判定问题，包括P类问题类问题NPC：NP中的一类问题，如果其中一个有多项式时间算中的一类问题，如果其中一个有多项式时间算法，则该类问题都有多项式时间算法法，则该类问题都有多项式时间算法图论中有大量的图论中有大量的NPC问题问题2021/8/227三、图论问题及其算法列举三、图论问题及其算法列举在实际中有一类问题具有如下的特点：在实际中有一类问题具有如下的特点：目的：是目的：是从若干可能的安排或方案中寻求某种意义从若干可能的安排或方案中寻求某种意义下的最优安排或方案下的最优安排或方案，数学上把这种问题称为最优化，数学上把这种问题称为最优化或优化问题；或优化问题；易于用图形的形式直观地描述和表达易于用图形的形式直观地描述和表达，这种与图相，这种与图相关的结构可以用图或网络来表示。关的结构可以用图或网络来表示。与图和网络相关的最优化问题就是网络最优化或称与图和网络相关的最优化问题就是网络最优化或称网络优化问题。多数网络优化问题是以网络上的流为网络优化问题。多数网络优化问题是以网络上的流为研究的对象，常常被称为网络流或网络流规划等。研究的对象，常常被称为网络流或网络流规划等。2021/8/228何时考虑使用图论方法？何时考虑使用图论方法？图图论论方方法法常常常常用用在在描描述述多多个个离离散散对对象象之之间间的的关关系系上上，可可以以刻刻划划某某种种关关系系的的有有无无，刻刻划划对对象象间间的的顺顺序序关关系系，刻刻划划某某种种关关系系的的关关系系度度等等。2021/8/2291.最短路问题最短路问题一名货柜车司机奉命在最短的时间内将一车货物从甲一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。要找到一条从甲地到乙地的最短路。有效算法：有效算法：DijkstraDijkstra算法、算法、FloydFloyd算法算法G问问题题描描述述：在在加加权权图图 中中，求求两两个个顶顶点点之之间间的的具具有有最最小小权权的的路路2021/8/2302.公路连接问题公路连接问题某一地区有若干个主要城市，现准备修建高速公路把某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最如何决定在哪些城市间修建高速公路，使得总成本最小？小？GGT()min()Te TW Tw e 问问题题描描述述：在在加加权权图图 中中，求求权权最最小小的的生生成成树树。即即求求 的的一一棵棵生生成成树树，使使得得有效算法：有效算法：Kruskal算法、算法、prim算法算法2021/8/2313.指派问题指派问题一家公司经理准备安排一家公司经理准备安排N名员工去完成名员工去完成N项任务，每项任务，每人一项。由于各员工的特点不同，不同的员工去完成人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？方案可以使总回报最大？问问题题描描述述：在在加加权权完完全全二二部部图图中中，求求最最大大权权完完备备匹匹配配。有效算法有效算法：匈牙利算法匈牙利算法2021/8/2324.中国邮递员问题中国邮递员问题一名邮递员负责投递某个街区的邮件。如何为他（她）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？这一问题是内每条街道至少一次，最后返回邮局）？这一问题是我国管梅谷教授我国管梅谷教授1960年首先提出，国际上称之为中年首先提出，国际上称之为中国邮递员问题。国邮递员问题。问问题题描描述述：在在加加正正权权的的连连通通图图中中，求求经经过过每每边边至至少少一一次次，且且具具有有最最小小权权的的闭闭链链。有效算法：有效算法：EdmondsJohnson算法算法2021/8/2335.旅行商问题（货郎担问题）旅行商问题（货郎担问题）一名推销员准备前往若干城市推销产品。如何为他设一名推销员准备前往若干城市推销产品。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次（或至少一次），最后返回驻地）？这一问恰好一次（或至少一次），最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。题的研究历史十分悠久，通常称之为旅行商问题。Hamilton问问题题描描述述：在在加加正正权权的的连连通通图图中中，求求具具有有最最小小权权的的圈圈（每每个个城城市市恰恰好好一一次次）或或具具有有最最小小权权的的闭闭链链（每每顶顶点点至至少少一一次次）。NPC问题：无通用的有效算法问题：无通用的有效算法2021/8/234四、图论常用算法简介四、图论常用算法简介1 1、最短路问题的、最短路问题的Dijkstra算法与算法与Floyd算法算法2、求最小生成树的、求最小生成树的Kruskal算法与算法与prim算法算法3、图的搜索：广度优先搜索与深度优先搜索、图的搜索：广度优先搜索与深度优先搜索2021/8/2351 1、最短路问题的、最短路问题的Dijkstra算法与算法与Floyd算法算法Dijkstra算法是典型最短路算法，用算法是典型最短路算法，用于计算于计算一个一个顶顶点到其他所有点到其他所有顶顶点的最短路径点的最短路径。主要特点是以起始点为中心向外层层扩展，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。直到扩展到终点为止。Dijkstra算法能得出算法能得出最短路径的最优解，但由于它遍历计算的最短路径的最优解，但由于它遍历计算的顶顶点很多，所以效率低。点很多，所以效率低。Dijkstra算法算法对有负权的图无效。对有负权的图无效。2021/8/236DijkstraDijkstra算法思想算法思想设设G=(V,E)是一个是一个加加权图，把图中顶点集合权图，把图中顶点集合V分成两分成两组，组，第一组为已求出最短路径的顶点集合第一组为已求出最短路径的顶点集合（用（用S表示，初表示，初始时始时S中只有一个中只有一个起始起始点，以后每求得一条最短路径点，以后每求得一条最短路径,就将就将相应的顶点相应的顶点加入到集合加入到集合S中，直到全部顶点都加入到中，直到全部顶点都加入到S中，中，算法就结束了），算法就结束了），第二组为其余未确定最短路径的顶点集第二组为其余未确定最短路径的顶点集合合（用（用U表示），按表示），按最短路径长度的递增次序最短路径长度的递增次序依次把第二依次把第二组的顶点加入组的顶点加入S中。在加入的过程中，中。在加入的过程中，总保持从源点总保持从源点v到到S中各顶点的最短路径长度不大于从源点中各顶点的最短路径长度不大于从源点v到到U中任何顶点的中任何顶点的最短路径长度最短路径长度。此外，每个顶点对应一个距离，。此外，每个顶点对应一个距离，S中的顶中的顶点的距离就是从点的距离就是从v到此顶点的最短路径长度，到此顶点的最短路径长度，U中的顶点的中的顶点的距离，是从距离，是从v到此顶点只包括到此顶点只包括S中的顶点为中间顶点的当前中的顶点为中间顶点的当前最短路径长度。最短路径长度。2021/8/2371 1、初始时初始时，S S只包含源点只包含源点v v，v v的距离为的距离为0 0。U U包含除包含除v v外外的其他顶点，的其他顶点，U U中顶点中顶点u u距离为边上的权（若距离为边上的权（若v v与与u u有边）有边）或或“无穷大无穷大”（若若v v与与u u无边无边）；2、从从U U中选取一个距离中选取一个距离v v最小的顶点最小的顶点k k，把，把k k加入加入S S中（中（该该选定的距离选定的距离就是就是v v到到k k的最的最短路径长短路径长度度）；3、以以k k为新考虑的中间点，为新考虑的中间点，修改修改U U中各顶点的距离中各顶点的距离：若从源点若从源点v v到顶点到顶点u u（u u属于属于U U）的距离（经过顶点）的距离（经过顶点k k）比原来距离（不经过顶点比原来距离（不经过顶点k k）短，则修改顶点）短，则修改顶点u u的距离的距离值，修改后的距离值值，修改后的距离值为为顶点顶点k k的距离加上边上的权的距离加上边上的权；4、重复步骤（重复步骤（2 2）和（）和（3 3）直到所有顶点都包含在）直到所有顶点都包含在S S中。中。DijkstraDijkstra算法算法具体步骤具体步骤2021/8/2382021/8/2392021/8/2402021/8/2412021/8/2422021/8/2432021/8/2442021/8/245A A=0A C=3A C B=5A C D=6A C E=7A C D F=9结果结果2021/8/2462021/8/247FloydFloyd算法算法求每一对顶点间的最短路径求每一对顶点间的最短路径1 1、利用二维数组利用二维数组D0.n-10.n-1,DijD0.n-10.n-1,Dij记录当前记录当前vivi到到vjvj的最短路径长度，数组的最短路径长度，数组D D的初值等于图的带权邻接的初值等于图的带权邻接矩阵矩阵;2、集合集合S S记录当前允许的中间顶点，初值记录当前允许的中间顶点，初值S=;S=;3、依次向依次向S S中加入中加入v0,v1 vn-1v0,v1 vn-1，每加入一个顶点，每加入一个顶点，对对DijDij进行一次修正：设进行一次修正：设S=v0,v1 vk-1S=v0,v1 vk-1，加，加入入vkvk，则，则D(k)ij=min D(k-1)ijD(k)ij=min D(k-1)ij，D(k-D(k-1)ik+D(k-1)kj1)ik+D(k-1)kj。D(k)ij的含义：允许中间顶点的序号最大为的含义：允许中间顶点的序号最大为k时从时从vi到到vj的最短路径长度。的最短路径长度。2021/8/2480063602532034D530234205350 2021/8/2490063602532034D530234205350 1063602532034D530234205350 2021/8/2501063602532034D530234205350 2063602532034D5302342051113510 2021/8/251206311602532034D11530234205350 30302532034D53023420535056756676 2021/8/2523053675025632034D653023764205350 4053675025632034D6530237649869862053502021/8/2534053679502568320346D653023764205986350 5053679502568320346D6530237642059863502021/8/2545053679502568320346D653023764205986350 6053679502568320346D6530237642059863502021/8/255 Kruskal算法粗略描述算法粗略描述2、求最小生成树的、求最小生成树的Kruskal算法与算法与prim算法算法 如何判断是否形成圈？如何判断是否形成圈？2021/8/2562021/8/257 Prim算法粗略描述算法粗略描述2021/8/2582021/8/259 Kruskal算法和Prim算法都蕴涵了贪心法的思想；贪心法的基本思想：把解看成是由若干个部件构成，每一步求出解的一个部件（不是从整体或长远的角度考虑，只是局部或当前的最好选择）。求出的一个个部件组合而作为最终的解。贪心法贪心法2021/8/260 贪心法可被用于各种各样问题的处理。贪心法只是一种试探法，计算上简便，有效，可提供正确解的一个近似。但一般情况下，不能保证输出的解是正确的。其正确性需要证明，这往往比较困难。2021/8/261 3、图的搜索：广度优先搜索与深度优先搜索、图的搜索：广度优先搜索与深度优先搜索从指定的起始顶点出发搜索特定的顶点从指定的起始顶点出发搜索特定的顶点广度优先搜索广度优先搜索广度优先搜索广度优先搜索2021/8/262深度优先搜索深度优先搜索深度优先搜索深度优先搜索部分资料从网络收集整理而来，供大家参考，感谢您的关注！