图论-数学建模

null数学模型 ------图论模型数学模型 ------图论模型1 引言 1 引言 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 的“哥尼斯堡的七座桥”。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。 哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。 nullnull 当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。 欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。null 我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP－shortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？例3 指派问题（assignment problem） 一家公司经理准备安排员工去完成项任务， 每人一项。由于各员工的特点不同，不同的员 工去完成同一项任务时所获得的回报是不同的。 如何分配工作 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 可以使总回报最大？ 例4 中国邮递员问题（CPP－chinese postman problem） 一名邮递员负责投递某个街区的邮件。如何为他 （她） 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 一条最短的投递路线（从邮局出发， 经过投递区内每条街道至少一次，最后返回邮局） ？由于这一问题是我国管梅谷教授1960年首先 提的，所以国际上称之为中国邮递员问题。例3 指派问题（assignment problem） 一家公司经理准备安排员工去完成项任务， 每人一项。由于各员工的特点不同，不同的员 工去完成同一项任务时所获得的回报是不同的。 如何分配工作方案可以使总回报最大？ 例4 中国邮递员问题（CPP－chinese postman problem） 一名邮递员负责投递某个街区的邮件。如何为他 （她）设计一条最短的投递路线（从邮局出发， 经过投递区内每条街道至少一次，最后返回邮局） ？由于这一问题是我国管梅谷教授1960年首先 提的，所以国际上称之为中国邮递员问题。null例5 运输问题（transportation problem） 某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？ 上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化 （network optimization）问题。 2 图与网络的基本概念 2 图与网络的基本概念 2.1 无向图 一个无向图(undirected graph)是由一个非空有限集合 和 中某些元素的无序对集合 构成的二元组，记为 。 其中 称为图的顶点集（vertex set）或节点集（node set）， 中的每一个元素 称为该图的一个顶点（vertex）或节点（node）； 称为图的边集 （edge set）， 中的每一个元素  记为 或 ，被称为该图的一条从 到 的边（edge）null一个图称为有限图，如果它的顶点集和边集都有 限。图的顶点数用符号 或 表示，边数用 或 表示。 当讨论的图只有一个时，总是用G来表示这个图。从而在图论符号中我们常略去字母G，例如:分别用 代替 。 端点重合为一点的边称为环(loop)。 一个图称为简单图(simple graph)，如果它既没有环也没有两条边连接同一对顶点。null2.2 有向图 定义 一个有向图（directed graph或 digraph）G是由一个非空有限集合V和V中某些元素的有序对集合构成的二元组，记为 其中 称为图的顶点集或节点集 . 称为图的弧集（arc set），A中的每一个元素(即中某两个元素的有序对) 记为 或 ， 当弧 时， 称为尾（tail）， 为头（head）.null2.3 完全图、二分图 每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n个顶点的完全图记为 。 若 ， ， （这里 表示集合X中的元素个数），X中无相邻顶点对，Y中亦然，则称G为二分图(bipartite graph)；特别地，若 ，则 ，则称G为完全二分图，记成 。 nullnull2.4 子图 如果 , ,图H叫做图G的子图（subgraph），记作 。若H是G的子图，则G称为H的母图。 2.5 顶点的度 设 ，G中与v关联的边数（每个环算作两条边）称为v的度(degree)，记作 。若 是奇数，称v是奇顶点(odd point)；若是偶数，称v是偶顶点(even point)。关于顶点的度，我们有如下结果： (i) (ii) 任意一个图的奇顶点的个数是偶数。null例：在任意六个人的聚会上，要么有三个人 曾相识，要么有三个人不曾相识。这道题是Ramsey定理，是一道简单的图论问题。 证明如下： 首先，把这6个人设为A、B、C、D、E、F六个点。由A点可以引出AB、AC、AD、AE、AF五条线段。设：如果两个人识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色。由抽屉原则可知：这五条线段中至少有三条是同色的。不妨设AB、AC、AD为红色。若BC或CD为红色，则结论显然成立。若BC和CD均为蓝色，则若BD为红色，则一定有三个人相互认识；若BD为蓝色，则一定有三个人互相不认识。 2.6 图与网络的数据结构2.6 图与网络的数据结构网络优化研究的是网络上的各种优化模型与算法．为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。 这里我们介绍计算机上用来描述图与网络的5种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。 在下面数据结构的讨论中，我们首先假设 是一个简单有向图 ， ，并假设V中的顶点用自然数1,2,…n表示或编号，A中的弧用自然数1,2,…m表示或编号。 nullnullnullnull（i）邻接矩阵表示法（i）邻接矩阵表示法邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图 的邻接矩阵是如下定义的：C是一个n*n的0-1矩阵，即 也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。 null例1 对于所示的图，可以用邻接矩阵表示为 同样，对于网络中的权，也可以用类似邻接矩阵的矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。（ii）弧表示法（ii）弧表示法弧表表示法将图以弧表（arc list）的形式存储在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。 例3，假设弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的权分别为8，9，6，4，0，3，6和7，则弧表表示如下： （iii）邻接表表示法（iii）邻接表表示法邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。 所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。 null 对于有向图 ，一般用 表示节点的邻接表，即节点的所有出弧构成的集合或链表（实际上只需要列出弧的另一个端点，即弧的 头）。例如上面例子， ， 等。（iv）星形表示法（iv）星形表示法星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。 记录弧信息的数组§3 应用—最短路问题§3 应用—最短路问题3.1 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数 —直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图G的各边的权和。 问题就是求赋权图中指定的两个顶点 间的具最小权的轨。这条轨叫做 间的最短路，它的权叫做 间的距离，亦记作 。null求最短路已有成熟的算法：迪克斯特拉（Dijkstra） 算法，其基本思想是按距 从近到远为顺序，依次 求得 到的G各顶点的最短路和距离，直至（或直 至的所有顶点）算法结束。为避免重复并保留每 一步的计算信息，下面是该算法。 令 ，对 令 ， ， 。 (ii) 对每个 ,用 代替 计算 ，把达到这个最小值的一个顶点 记为 ，令 。 (iii)若 ，停止；若 ，用i+1代替 i，转(ii)。找出 到其他各点的最短路径找出 到其他各点的最短路径null3.2 每对顶点之间的最短路径3.2 每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。 第二种解决这一问题的方法是由Floyd R W提出的算法，称之为Floyd算法。 null假设图权的邻接矩阵为， 来存放各边长度，其中： ； 之间没有边，在程序中以各边都不 可能达到的充分大的数代替； 是 i,j之间边的长度， 。nullFloyd算法的基本思想是：递推产生一个矩阵序列 ，其中 表示从顶点 到顶点 的路径上所经过的顶点序号不大于k 的最短路径长度。 计算时用迭代公式： k是迭代次数， 。 最后，当k=n时， 即是各顶点之间的最短通路值。 (例题见附件)null*例 求v1到v6的最短路(双标号法)（1）首先给v1以P标号：（0，V1)（0，V1) 标号以（ ）形式标在结点旁边 0：表示从V1到该点的最短距离 V1：表示从V1到该点的最短路中上一个顶点。null*（2） S：{V1} S’：{V2，V3，V4， V5，V6} 求出（S→ S’）所有弧，分别计算： S12 =0 + 3=3, S13 =0 + 5=5, Min Sij=S12 给V2 标号（3，V1）（3，V1)（0，V1)null*（3） S：{V1，V2} S’：{V3，V4，V5，V6} 求出（S→ S’）所有弧，分别计算： S13 =0 + 5=5 S23 =3 + 1=4 S24 =3 + 6=9 Min Sij=S23 给V3 标号（4，V2）（3，V1)（4，V2)（0，V1)null*（4） S：{V1，V2，V3} S’：{V4，V5，V6} 求出（S→ S’）所有弧，分别计算： S24 =3 + 6=9 S34 =4 + 4=8 S35 =4 + 1=5 Min Sij=S35 给V5 标号（5，V3）（3，V1)（4，V2)（5，V3)（0，V1)null*（0，V1)（5） S：{V1，V2，V3，V5} S’：{V4，V6} 求出（S→ S’）所有弧，分别计算： S24 =3 + 6=9 S34 =4 + 4=8 S54 =5 + 2=7 S56=5 + 6=11 Min Sij=S54 给V4 标号（7，V5）（3，V1)（4，V2)（5，V3)（7，V5)null*（6） S：{V1，V2，V3，V4，V5} S’：{V6} 求出（S→ S’）所有弧，分别计算： S46 =7 + 3=10 S56= 5 + 6=11 Min Sij=S46 给V6 标号（10，V4）（3，V1)（4，V2)（5，V3)（7，V5)（10，V4)（0，V1)null*(7) 标出最短路 最短路径是： V1→V2→V3→V5→V4→V6 路长10。同时得到起点到其余各点的最短路。 注意： 双标号法只适用于所有wij ≥0的情形，当赋权有向图中存在负权时，则算法失效。 (10)null*求天然气管道最优路径 筹建中的天然气管道网设计如图所示： 解为： ★ 例:null*应用：设备更新问题 某企业每年年初,都要作出决定,如果继续使用旧设备,要付维修费；若购买一台新设备,要付购买费.试制定一个5年更新 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 ,使总支出最少。 已知设备在每年年初的购买费分别为11,11, 12,12,13。使用不同时间设备所需的维修费分别为5,6,8,11,18（万元）。 null* 解 设bi 表示设备在第i 年年初的购买费,ci 表示设备使用i 年后的维修费, V={v1, v2, … , v6},点vi表示第i 年年初购进一台新设备,虚设一个点v6表示第5年年底。 E ={vivj | 1≤i＜j≤6}。 null* 这样上述设备更新问题就变为：在有向赋权图G = (V, E, F )(图解如下)中求v1到v6的最短路问题。null*从上图中容易得到v1到v6有两条最短路：v1v3v6和v1v4v6。