梧州学院培训课件2第五章图与网络

《梧州学院培训课件2第五章图与网络》由会员分享，可在线阅读，更多相关《梧州学院培训课件2第五章图与网络（50页珍藏版）》请在金锄头文库上搜索。

1、 -68- 第五章第五章 图与网络模型及方法图与网络模型及方法 1 概论 图论起源于 18 世纪。第一篇图论论文是瑞士数学家欧拉于 1736 年发表的“哥尼 斯堡的七座桥” 。1847 年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857 年，凯莱在计数烷 22 +nnH C的同分异构物时，也发现了“树” 。哈密尔顿于 1859 年提 出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈、近几十年 来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和 方法已经渗透到物理、化学、通讯科学、建筑学、运筹学，生物遗传学、心理学、经济 学、社会学等学科中。

2、 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示 这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到 了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了 一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问 题就是一个典型的例子。 在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结 起来，问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。 图 1 哥尼斯堡七桥问题 当然可以通过试验去尝试解决这个问题， 但该城居民的任何尝试均未成功。 欧拉为了解 决这个问题，采用了建立数

3、学模型的方法。他将每一块陆地用一个点来代替，将每一座 桥用连接相应两点的一条线来代替，从而得到一个有四个“点” ，七条“线”的“图” 。 问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特 点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将 这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问 题，而且开创了图论研究的先河。 图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的 问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等 诸多领域。下面将要讨论的最

4、短路问题、最大流问题、最小费用流问题和匹配问题等都 是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例 1 最短路问题（SPPshortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。 从甲地到乙地的 公路网纵横交错， 因此有多种行车路线， 这名司机应选择哪条线路呢？假设货柜车的运 行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例 2 公路连接问题 某一地区有若干个主要城市， 现准备修建高速公路把这些城市连接起来， 使得从其 -69- 中任何一个城市都可以经高速公路直接或间接到达另一个城市。 假定已经知道了

5、任意两 个城市之间修建高速公路的成本， 那么应如何决定在哪些城市间修建高速公路， 使得总 成本最小？ 例 3 指派问题（assignment problem） 一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点 不同， 不同的员工去完成同一项任务时所获得的回报是不同的。 如何分配工作方案可以 使总回报最大？ 例 4 中国邮递员问题（CPPchinese postman problem） 一名邮递员负责投递某个街区的邮件。 如何为他 （她） 设计一条最短的投递路线 （从 邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管 梅谷教授 1960 年首先提

6、出的，所以国际上称之为中国邮递员问题。 例 5 旅行商问题（TSPtraveling salesman problem） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线 （从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠 久，通常称之为旅行商问题。 例 6 运输问题（transportation problem） 某种原材料有M个产地， 现在需要将原材料从产地运往N个使用这些原材料的工 厂。假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂 的运费已知，那么如何安排运输方案可以使总运输成本最低？ 上述问题有两个共同的特点：

7、 一是它们的目的都是从若干可能的安排或方案中寻求 某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization） 问题； 二是它们都易于用图形的形式直观地描述和表达， 数学上把这种与图相关的结构 称为网络（network） 。与图和网络相关的最优化问题就是网络最优化或称网络优化 （netwok optimization）问题。所以上面例子中介绍的问题都是网络优化问题。由于多 数网络优化问题是以网络上的流（flow）为研究的对象，因此网络优化又常常被称为网 络流（network flows）或网络流规划等。 下面首先简要介绍图与网络的一些基本概念。 2 图与网络的基本概

8、念 2.1 无向图 一个无向图(undirected graph)G是由一个非空有限集合)(GV和)(GV中某些元素 的 无 序 对 集 合)(GE构 成 的 二 元 组 ， 记 为)(),(GEGVG =。 其 中 ,)( 21n vvvGVL=称为图G的顶点集（vertex set）或节点集（node set） ， )(GV中 的每一个元素), 2 , 1(niviL=称为该图的一个顶点（vertex）或节点（node） ； ,)( 21m eeeGEL=称为图G的边集 （edge set） ，)(GE中的每一个元素 k e(即)(GV 中某两个元素 ji vv ,的无序对) 记为),(

9、jik vve =或 ijjik vvvve= ), 2 , 1(mkL=， 被称为该图的一条从 i v到 j v的边（edge） 。 当边 jik vve =时，称 ji vv ,为边 k e的端点，并称 j v与 i v相邻（adjacent） ；边 k e称 为与顶点 ji vv ,关联（incident） 。如果某两条边至少有一个公共端点，则称这两条边在 图G中相邻。 边上赋权的无向图称为赋权无向图或无向网络（undirected network） 。我们对图和 网络不作严格区分，因为任何图总是可以赋权的。 -70- 一个图称为有限图有限图，如果它的顶点集和边集都有限。图G的顶点数用符

10、号|V或 )(G表示，边数用|E或)(G表示。 当讨论的图只有一个时，总是用G来表示这个图。从而在图论符号中我们常略去 字母G，例如，分别用,EV和代替)(),(),(GGEGV和)(G。 端点重合为一点的边称为环环(loop)。 一个图称为简单图简单图(simple graph)，如果它既没有环也没有两条边连接同一对顶点。 2.2 有向图 定义定义 一个有向图 （directed graph 或 digraph）G是由一个非空有限集合V和V中 某些元素的有序对集合A构成的二元组，记为),(AVG =。其中, 21n vvvVL=称 为图G的顶点集或节点集， V中的每一个元素), 2 , 1(

11、niviL=称为该图的一个顶点 或节点；, 21m aaaAL=称为图G的弧集（arc set） ，A中的每一个元素 k a(即V中 某两个元素 ji vv ,的有序对) 记为),( jik vva =或), 2 , 1(nkvva jik L=，被称为该图 的一条从 i v到 j v的弧（arc） 。 当弧 jik vva =时，称 i v为 k a的尾（tail） ， j v为 k a的头（head） ，并称弧 k a为 i v的 出弧（outgoing arc） ，为 j v的入弧（incoming arc） 。 对应于每个有向图D，可以在相同顶点集上作一个图G，使得对于D的每条弧， G

12、有一条有相同端点的边与之相对应。 这个图称为D的基础图。 反之， 给定任意图G， 对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图，这 样的有向图称为G的一个定向图。 以下若未指明“有向图”三字， “图”字皆指无向图。 2.3 完全图、二分图 每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n个顶点 的完全图记为 n K。 若YXGVU=)(，=YXI，0|YX（这里| X表示集合X中的元素个 数） ，X中无相邻顶点对，Y中亦然，则称G为二分图(bipartite graph)；特别地，若 YyXx,，则)(GExy，则称G为完全二分图

13、，记成 | |,|YX K。 2.4 子图 图H叫做图G的子图（子图（subgraph） ，记作GH，如果)()(GVHV， )()(GEHE。若H是G的子图，则G称为H的母图母图。 G的支撑子图（spanning subgraph，又成生成子图）是指满足)()(GVHV=的子 图H。 2.5 顶点的度 设)(GVv，G中与v关联的边数（每个环算作两条边）称为v的度(degree)，记 作)(vd。若)(vd是奇数，称v是奇顶点(odd point)；)(vd是偶数，称v是偶顶点(even point)。关于顶点的度，我们有如下结果： (i) = Vv vd2)( (ii) 任意一个图的奇顶点

14、的个数是偶数。 2.6 图与网络的数据结构 -71- 网络优化研究的是网络上的各种优化模型与算法。 为了在计算机上实现网络优化的 算法， 首先我们必须有一种方法 （即数据结构） 在计算机上来描述图与网络。 一般来说， 算法的好坏与网络的具体表示方法， 以及中间结果的操作方案是有关系的。 这里我们介 绍计算机上用来描述图与网络的 5 种常用表示方法： 邻接矩阵表示法、 关联矩阵表示法、 弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中，我们首先假设 ),(AVG =是一个简单有向图，mAnV=| ,|， 并假设V中的顶点用自然数n, 2 , 1L 表示或编号，A中的弧用自然数m, 2

15、 , 1L表示或编号。对于有多重边或无向网络的情 况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。 （i）邻接矩阵表示法 邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图 ),(AVG =的邻接矩阵是如下定义的：C是一个nn的10矩阵，即 nn nnij cC =1 , 0)(， = .),(, 0 ,),(, 1 Aji Aji cij 也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为 1；否则为 0。 可以看出， 这种表示法非常简单、 直接。 但是， 在邻接矩阵的所有 2 n个元素中， 只有m 个为非零元。如果网络比较稀疏，这

16、种表示法浪费大量的存储空间，从而增加了在网络 中查找弧的时间。 图 2 有向图 例 7 对于图 2 所示的有向图，可以用邻接矩阵表示为 01100 10100 00010 01000 00110 同样，对于网络中的权，也可以用类似邻接矩阵的nn矩阵表示。只是此时一条 弧所对应的元素不再是 1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以 用多个矩阵表示这些权。 （ii）关联矩阵表示法 关联矩阵表示法是将图以关联矩阵（incidence matrix）的形式存储在计算机中图 ),(AVG =的关联矩阵B是如下定义的：B是一个mn的矩阵，即 mn mnik bB =1 , 0 , 1)(， -72- = = = ., 0 ,),(, , 1 ,),(, 1 其它 AijkVj AjikVj