数学建模培训2(图论)

null数学建模培训数学建模培训图论与网络模型§1 概论 §1 概论 图论起源于18世纪。第一篇图论 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 §1 概论 §1 概论 §1 概论 §1 概论 图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 涉及经济管理、工业 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 §1 概论 §1 概论 例1 最短路问题（SPP－shortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 §1 概论 §1 概论 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？ §1 概论 §1 概论 例3 指派问题（assignment problem） 一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 可以使总回报最大？ §1 概论 §1 概论 例4 中国邮递员问题（CPP－chinese postman problem） 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。 §1 概论 §1 概论 例5 旅行商问题（TSP－traveling salesman problem） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。 §1 概论 §1 概论 例6 运输问题（transportation problem） 某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？ §1 概论 §1 概论 上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化 （netwok optimization）问题。所以上面例子中介绍的问题都是网络优化问题。 §2 图与网络的基本概念 §2 图与网络的基本概念 2.1 无向图 一个无向图(undirected graph)是由一个非空有限集合和中某些元素的无序对集合构成的二元组，记为G=(V(G),E(G))。其中V(G)称为图的顶点集（vertex set）或节点集（node set），V(G)中的每一个元素称为该图的一个顶点（vertex）或节点（node）；E(G)称为图的边集（edge set），E(G)中的每一个元素(即中某两个元素的无序对) ，被称为该图的一条从到的边（edge）。 §2 图与网络的基本概念 §2 图与网络的基本概念 2.2 有向图 一个有向图（directed graph或 digraph）是由一个非空有限集合和集合中某些元素的有序对集合构成的二元组，记为G=(V,A)。其中V称为图的顶点集或节点集，V中的每一个元素称为该图的一个顶点或节点；A称为图的弧集（arc set），A中的每一个元素(即中某两个元素的有序对) ，被称为该图的一条从到的弧（arc）。 §2 图与网络的基本概念 §2 图与网络的基本概念 2.3 完全图、二分图 每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n个顶点的完全图记为Kn。 若V(G)=XUY， X∩Y=Φ,集合中的元素个数不为零，X中无相邻顶点对，Y中亦然，则称G为二分图(bipartite graph)；特别地，若X中任意顶点与Y中任意顶点之间有边存在，则称G为完全二分图。 §2 图与网络的基本概念 §2 图与网络的基本概念 2.4 子图 图H叫做图G的子图（subgraph），记作H  G ，如果V(H) V(G) ，E(H)  E(G)。若H是G的子图，则称G为H的母图。 G的支撑子图（spanning subgraph，又成生成子图）是指满足V(H)=V(G)的子图H。§2 图与网络的基本概念 §2 图与网络的基本概念 2.5 顶点的度 度(degree) 若度是奇数，称是奇顶点(odd point)；度是偶数，称是偶顶点(even point)。 §2 图与网络的基本概念 §2 图与网络的基本概念 2.6 图与网络的数据结构 （i）邻接矩阵表示法 邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。 §2 图与网络的基本概念 §2 图与网络的基本概念 例7 对于右图所示的图，可以用邻接矩阵表示为§2 图与网络的基本概念 §2 图与网络的基本概念 （ii）关联矩阵表示法 关联矩阵表示法是将图以关联矩阵（incidence matrix）的形式存储在计算机中． 在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。 §2 图与网络的基本概念 §2 图与网络的基本概念 例8 对于例7所示的图，如果关联矩阵中每列对应弧的顺序为(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，则关联矩阵表示为 §2 图与网络的基本概念§2 图与网络的基本概念（iii）弧表示法 弧表表示法将图以弧表（arc list）的形式存储在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需2m个存储 单元 初级会计实务单元训练题天津单元检测卷六年级下册数学单元教学设计框架单元教学设计的基本步骤主题单元教学设计 ，因此当网络比较稀疏时比较方便。此外，对于网络图中每条弧上的权，也要对应地用额外的存储单元表示。 §2 图与网络的基本概念§2 图与网络的基本概念例如，例7所示的图，假设弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的权分别为8，9，6，4，0，3，6和7，则弧表表示如下： §2 图与网络的基本概念§2 图与网络的基本概念（iv）邻接表表示法 邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。 §2 图与网络的基本概念§2 图与网络的基本概念例如，例7所示的图，邻接表表示为 §2 图与网络的基本概念§2 图与网络的基本概念2.7 轨与连通 道路(walk) 若道路的边互不相同，则称为迹(trail)。若道路的顶点互不相同，则称为轨(path)。 称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做圈(cycle)。 §3 应用—最短路问题 §3 应用—最短路问题 3.1 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法 null算法步骤：§3 应用—最短路问题 §3 应用—最短路问题 例9 某公司在六个城市中有分公司C1-C6，从Ci到Cj的直接航程票价记在下述矩阵的位置(i,j)上。（∞表示无直接航路），请帮助该公司设计一张城市C1到其它城市间的票价最便宜的路线图。 nulld = 0 35 45 35 25 10 index1 = 1 6 5 2 4 3 index2 = 1 6 5 6 1 1§3 应用—最短路问题 §3 应用—最短路问题 3.2 每对顶点之间的最短路径 §3 应用—最短路问题§3 应用—最短路问题例10 用Floyd算法求解例9。 矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号。 §3 应用—最短路问题§3 应用—最短路问题b = 0 35 45 35 25 10 35 0 15 20 30 25 45 15 0 10 20 35 35 20 10 0 10 25 25 30 20 10 0 35 10 25 35 25 35 0 path = 0 6 5 5 0 0 6 0 0 0 4 0 5 0 0 0 0 4 5 0 0 0 0 0 0 4 0 0 0 1 0 0 4 0 1 0§4 树 §4 树 4.1 基本概念 连通的无圈图叫做树，记之为T。若图G满足V(G)=V(T)，E(T)  E(G)，则称T是G的生成树。图G连通的充分必要条件为G有生成树。 §4 树 §4 树 4.2 应用—连线问题 欲修筑连接n个城市的铁路，已知城i与城j之间的铁路造价为Cij，设计一个线路图，使总造价最低。 连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。 §4 树 §4 树 4.2.1 prim算法构造最小生成树 prim算法如下： （i），（ii）while end§4 树 §4 树 例11 用prim算法求下图的最小生成树。 §4 树§4 树我们用result的第一、二、三行分别表示生成树边的起点、终点、权集合。 result = 1 2 5 4 4 7 2 5 4 6 7 3 50 40 50 30 42 45§4 树§4 树4.2.2 Kruskal算法构造最小生成树 Kruskal算法如下: (i)选，使得(ii)若已选好，则从中选取，使得中无圈，且(iii)直到选得为止。 §4 树§4 树例12 用Kruskal算法构造例3的最小生成树。 我们用index存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号μ改记为此边的另一序号ν，同时把后面边中所有序号μ为的改记为ν 。 §4 树§4 树result = 4 2 4 3 1 4 6 5 7 7 2 5 30 40 42 45 50 50§5 匹配问题 §5 匹配问题 定义 若ME(G)，∀ei,ej∈M，ei与ej无公共端点（i≠j），则称M为图G的一个对集；M中的一条边的两个端点叫做在对集M中相配；M中的端点称为被M许配；G中每个顶点皆被M许配时，M称为完美对集；M中已无更大对集，则称M为最大对集；若G中有一轨，其边交替地在对集M内外出现，则称此轨为M的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。 §5 匹配问题§5 匹配问题1957年，贝尔热(Berge)得到最大对集的充要条件： 定理2 M是图G中的最大对集当且仅当G中无M可增广轨。 1935年，霍尔(Hall)得到下面的许配定理： 定理3 G为二分图，X与Y是顶点集的划分，G中存在把X中顶点皆许配的对集的充要条件是，∀SX，则|N(S)|≥|S|，其中N(S)是S中顶点的邻集。 §5 匹配问题§5 匹配问题推论1：若G是k(k>0)正则2分图，则G有完美对集。 所谓k正则图，即每顶点皆度k的图。 由此推论得出下面的婚配定理： 定理4 每个姑娘都结识k(k≥1)位小伙子，每个小伙子都结识k位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。 §5 匹配问题§5 匹配问题人员分派问题等实际问题可以化成对集来解决。 人员分派问题：工作人员x1,x2, …,xn去做n件工作y1,y2, …,yn，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？ §5 匹配问题§5 匹配问题这个问题的数学模型是：G是二分图，顶点集划分为V(G)=XUY，X={x1,x2, …,xn}，Y={y1,y2, …,yn}，当且仅当xi适合做工作yi时，xiyi∈E(G)，求G中的最大对集。 解决这个问题可以利用1965年埃德门兹(Edmonds)提出的匈牙利算法。 §5 匹配问题§5 匹配问题匈牙利算法： （i）从G中任意取定一个初始对集M。 （ii）若M把X中的顶点皆许配，停止，M即完美对集；否则取X中未被M许配的一顶点μ，记S={μ}，T=Φ。 （iii）若N(S)=T，停止，无完美对集；否则取y∈N(S)-T。 （iv）若y是被M许配的，设yz∈M，S=SU{z}，T=TU{y}，转（iii）；否则，取可增广轨P(μ,y)，令M=(M-E(P))U(E(P)-M)，转（ii）。 §5 匹配问题§5 匹配问题最优分派问题：在人员分派问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。 这个问题的数学模型是：在人员分派问题的模型中，图G的每边加了权w(xiyj)≥0，表示xi干yj工作的效益，求加权图G上的权最大的完美对集。 解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。………….§5 匹配问题§5 匹配问题例 5人做5件事,工作的效益如下矩阵所示: a[37.7 32.9 38.8 37 35.4 43.4 33.1 42.2 34.7 41.8 33.3 28.5 38.9 30.4 33.6 29.2 26.4 29.6 28.5 31.1 33.1 40.5 60.5 50.2 44.6] 求最优分配.§5 匹配问题§5 匹配问题z = 161.3000 ans = 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0§6 Euler图和Hamilton图 §6 Euler图和Hamilton图 6.1 基本概念 定义 经过G的每条边的迹叫做G的Euler迹；闭的Euler迹叫做Euler回路或E回路；含Euler回路的图叫做Euler图。 直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。 null定义 包含G的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton轨叫做Hamilton圈或H圈；含Hamilton圈的图叫做Hamilton图。 直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。 null6.2 Euler回路的Fleury算法 1921年，Fleury给出下面的求Euler回路的算法。 Fleury算法： 1. ∀v0∈V(G)，令W0=v0。 2. 假设迹Wi=v0e1v1…eivi已经选定，那么按下述方法从E-{e1, …,ei}中选取边ei+1： null（i）ei+1和vi相关联； （ii）除非没有别的边可选择，否则ei+1不是Gi=G- {e1, …,ei}的割边(cut edge)。(所谓割边是一条删除后使连通图不再连通的边)。 3. 当第2步不能再执行时，算法停止。 null6.3 应用 6.3.1 邮递员问题 中国邮递员问题 一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。 上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。 显然，若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求。 null多邮递员问题： 邮局有k(k≥2)位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成kPP。 null6.3.2 旅行商（TSP）问题 一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。 null例13 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表： nullnullcircle = 5 6 2 3 1 4 sum = 160