图论-数学建模

《图论-数学建模》由会员分享，可在线阅读，更多相关《图论-数学建模（43页珍藏版）》请在金锄头文库上搜索。

1、图论山东建筑大学 贺长伟1 引言 图论起源于18世纪。第一篇图论论文是瑞士 数学家欧拉于1736 年发表的“哥尼斯堡的七座桥” 。 图论中所谓的“图”是指某类具体事物和这些 事物之间的联系。如果我们用点表示这些具体事 物，用连接两点的线段（直的或曲的）表示两个 事物的特定的联系，就得到了描述这个“图”的几 何形象。图论为任何一个包含了一种二元关系的 离散系统提供了一个数学模型，借助于图论的概 念、理论和方法，可以对该模型求解。 哥尼斯堡七桥问题就是一个典型的例子。在 哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛 与河岸联结起来。问题是要从这四块陆地中的任 何一块开始通过每一座桥正好一次，再回到起

2、点 。 当然可以通过试验去尝试解决这个问题，但 该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模 型的方法。他将每一块陆地用一个点来代替，将 每一座桥用连接相应两点的一条线来代替，从而 得到一个有四个“点”，七条“线”的“图”。问题成 为从任一点出发一笔画出七条线再回到起点。欧 拉考察了一般一笔画的结构特点，给出了一笔画 的一个判定法则：这个图是连通的，且每个点都 与偶数线相关联，将这个判定法则应用于七桥问 题，得到了“不可能走通”的结果，不但彻底解决 了这个问题，而且开创了图论研究的先河。我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPPshortest p

3、ath problem）一名货柜车司机奉命在最短的时间内将一车货物 从甲地运往乙地。从甲地到乙地的公路网纵横交 错，因此有多种行车路线，这名司机应选择哪条 线路呢？假设货柜车的运行速度是恒定的，那么 这一问题相当于需要找到一条从甲地到乙地的最 短路。 例2 公路连接问题某一地区有若干个主要城市，现准备修建高速公 路把这些城市连接起来，使得从其中任何一个城 市都可以经高速公路直接或间接到达另一个城市 。假定已经知道了任意两个城市之间修建高速公 路的成本，那么应如何决定在哪些城市间修建高 速公路，使得总成本最小？例3 指派问题（assignment problem）一家公司经理准备安排名员工去完成

4、项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的 。如何分配工作方案可以使总回报最大？例4 中国邮递员问题（CPPchinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局 ）？由于这一问题是我国管梅谷教授1960年首先 提的，所以国际上称之为中国邮递员问题。 例5 运输问题（transportation problem）某种原材料有个产地，现在需要将原材料从产地 运往个使用这些原材料的工厂。假定个产地的产 量和家工厂的需要量已知，单位产品

5、从任一产地 到任一工厂的运费已知，那么如何安排运输方案 可以使总运输成本最低？ 上述问题有两个共同的特点：一是它们的目的都 是从若干可能的安排或方案中寻求某种意义下的 最优安排或方案，数学上把这种问题称为最优化 或优化（optimization）问题；二是它们都易于 用图形的形式直观地描述和表达，数学上把这种 与图相关的结构称为网络（network）。与图和网 络相关的最优化问题就是网络最优化或称网络优 化 （netwok optimization）问题。 2 图与网络的基本概念 2.1 无向图一个无向图(undirected graph)是由一个非空有限 集合 和 中某些元素的无序对集合 构

6、成 的二元组，记为 。其中 称为图的顶点集（vertex set）或节点集（node set）， 中的每一个元素称为该图的一个顶点（vertex）或节 点（node）； 称为图的边集（edge set）， 中的每一个元素 记为 或 ，被称为 该图的一条从 到 的边（edge） 一个图称为有限图，如果它的顶点集和边集都有限。图的顶点数用符号 或 表示，边数用或 表示。 当讨论的图只有一个时，总是用G来表示这个图。 从而在图论符号中我们常略去字母G，例如:分别 用 代替 。 端点重合为一点的边称为环(loop)。 一个图称为简单图(simple graph)，如果它既没 有环也没有两条边连接同一对

7、顶点。 2.2 有向图 定义 一个有向图（directed graph或 digraph） G是由一个非空有限集合V和V中某些元素的有序对 集合构成的二元组，记为 其中 称为图的顶点集或节点集 .称为图的弧集（arc set），A中 的每一个元素(即中某两个元素的有序对) 记为 或 ，当弧 时， 称为尾（tail）， 为头（ head）. 2.3 完全图、二分图 每一对不同的顶点都有一条边相连的简单图称为 完全图(complete graph)。n个顶点的完全图记为 。 若 ， ， （这里 表示集合X中的元素个数），X中无相邻顶点对，Y 中亦然，则称G为二分图(bipartite graph)

8、；特 别地，若 ，则 ，则称 G为完全二分图，记成 。 2.4 子图如果 , ,图H叫做图G的子 图（subgraph），记作 。若H是G的子图， 则G称为H的母图。 2.5 顶点的度设 ，G中与v关联的边数（每个环算作两 条边）称为v的度(degree)，记作 。若 是奇数，称v是奇顶点(odd point)；若是偶数， 称v是偶顶点(even point)。关于顶点的度，我们 有如下结果： (i) (ii) 任意一个图的奇顶点的个数是偶数。2.6 图与网络的数据结构 网络优化研究的是网络上的各种优化模型与算法 为了在计算机上实现网络优化的算法，首先我 们必须有一种方法（即数据结构）在计算机

9、上来 描述图与网络。 这里我们介绍计算机上用来描述图与网络的5种常 用表示方法：邻接矩阵表示法、关联矩阵表示法 、弧表表示法、邻接表表示法和星形表示法。 在下面数据结构的讨论中，我们首先假设 是一个简单有向图 ， ，并假设V中的 顶点用自然数1,2,n表示或编号，A中的弧用自 然数1,2,m表示或编号。 （i）邻接矩阵表示法 邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图 的 邻接矩阵是如下定义的：C是一个n*n的0-1矩阵， 即 也就是说，如果两节点之间有一条弧，则邻接矩 阵中对应的元素为1；否则为0。 例1 对于所示的图，可以用邻接矩阵表示为 同

10、样，对于网络中的权，也可以用类似邻接矩阵 的矩阵表示。只是此时一条弧所对应的元素不再 是1，而是相应的权而已。如果网络中每条弧赋有 多种权，则可以用多个矩阵表示这些权。（ii）关联矩阵表示法 关联矩阵表示法是将图以关联矩阵（incidence matrix）的形式存储在计算机中图 的关联矩阵B是如下定义的：B是一个 n*m的矩阵，即 如果一个节点是一条弧的起点，则关联矩阵中对 应的元素为1；如果一个节点是一条弧的终点，则 关联矩阵中对应的元素为-1；如果一个节点与一 条弧不关联，则关联矩阵中对应的元素为0。例2 对于例1所示的图，如果关联矩阵中每列对应 弧的顺序为(1,2)，(1,3)，(2,

11、4)，(3,2)，(4,3) ，(4,5)，(5,3)和(5,4)，则关联矩阵表示为（列单位为弧） （iii）弧表示法 弧表表示法将图以弧表（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，则弧表表示如下： 起点11234455终终点23423534权权89640367（iv）邻接表表示法 邻接表表示法将图以邻接表（adjacency lists ）的形式存储在计算机中。 所谓图的邻接表，也就是图的

12、所有节点的邻接表 的集合；而对每个节点，它的邻接表就是它的所 有出弧。邻接表表示法就是对图的每个节点，用 一个单向链表列出从该节点出发的所有弧，链表 中每个单元对应于一条出弧。为了记录弧上的权 ，链表中每个单元除列出弧的另一个端点外，还 可以包含弧上的权等作为数据域。图的整个邻接 表可以用一个指针数组表示。 对于有向图 ，一般用 表示节点 的邻接表，即节点的所有出弧构成的集合或链表 （实际上只需要列出弧的另一个端点，即弧的 头）。例如上面例子， ， 等 。（v）星形表示法 星形（star）表示法的思想与邻接表表示法的思 想有一定的相似之处。对每个节点，它也是记录 从该节点出发的所有弧，但它不是

13、采用单向链表 而是采用一个单一的数组表示。 记录 弧信息的数组弧编号12345678起点11234455终点23423534权896403673 应用最短路问题 3.1 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网 络，在这个网络的两个指定城镇间，找一条最短 铁路线。 以各城镇为图G的顶点，两城镇间的直通铁路为图 G相应两顶点间的边，得图G。对G的每一边e，赋 以一个实数 直通铁路的长度，称为e的权 ，得到赋权图G。G的子图的权是指子图G的各边的 权和。 问题就是求赋权图中指定的两个顶点 间的具 最小权的轨。这条轨叫做 间的最短路，它 的权叫做 间的距离，亦记作 。求

14、最短路已有成熟的算法：迪克斯特拉（Dijkstra） 算法，其基本思想是按距 从近到远为顺序，依次 求得 到的G各顶点的最短路和距离，直至（或直 至的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。(i) 令 ，对 令 ， ， 。 (ii) 对每个 ,用 代替 计算 ，把达到这个最小值的一个顶点记为 ，令 。 (iii)若 ，停止；若 ，用i+1代替i，转(ii)。找出u0到其他各点的最短路径3.2 每对顶点之间的最短路径 计算赋权图中各对顶点之间最短路径，显然可以 调用Dijkstra算法。具体方法是：每次以不同的 顶点作为起点，用Dijkstra算法求出从该起点到 其余顶点的最短路径，反复执行次这样的操作， 就可得到从每一个顶点到其它顶点的最短路径。 第二种解决这一问题的方法是由Floyd R W提出的 算法，称之为Floyd算法。 假设图权的邻接矩阵为，来存放各边长度，其中：；之间没有边，在程序中以各边都不可能达到的充分大的数代替；是 i,j之间边的长度， 。 Floyd算法的基本思想是：递推产生一个矩阵序列 ，