第6章 图上的最优化问题

《第6章 图上的最优化问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章图上的最优化问题图论是近几十年来较为活跃的一个应用数学分支，它应用广泛，在物理·化学·生物等学科领域都有许多成功应用的范例，特别是计算机科学，更有其重要的地位，在生产技术·经营管理·投资决策乃至社会科学和日常生活中，也可以找到用其思想方法·计算方法解决有关问题的例子。用图求实际问题具有直观明了的特点，这一特点促进了讨论方法应用范围不断的扩大。初步掌握图论的基本理论和方法，并不要求有较深的数学基础，对中学生而言也并不是十分困难。这一章将介绍图论的初步知识及其在最优化问题中的一些应用。6.1图和子图早些年，中国科技大学招收少年班的测试题中有这样一道题：假定有6个点，其中任意3个点都不共线，

2、用红蓝两种颜色的直线将这些点两两连接起来，要证明必定存在一个三角形，他的三条边的颜色是相同的，我们用图论的方法来讨论这道题。首先，我们任取6个点v1,v2,….,v6.如果v1和v2两点间用红线连接，那么就在该两点间连一条边；如果是用蓝线连接的，就不连边。这样就得到一个图，图6—1就表示一种连接方法。在这张图上，和v1有边相连的点有v2，v4，v6，显然，如果这3个点之间至少有一条边相连，那么这条边得两个端点加上v1就构成一个红色的三角形；反之（如图所示）这3个点就将形成一个蓝色的三角形。以上用点以及连接一堆点的线（图论中称为边）所构成的图形就是图论的研究对象——图。这种图，有别于通常意义上

3、的图，如几何图形——机械零件图等等。他可以用来表示很多离散对象之间的内在联系。现实生活中有许多离散的对象：例如一个国家或地区内的城市·化化工厂的各类产品·某次竞赛中的参赛队等等；这些对象之间有存在着某种特定的关系：城市之间是否存在直达航空线，化工厂的产品能否储藏在同一个仓库内，参赛队之间在比赛中是否会相遇等等。这些关系又带来一些相应的数学问题。首先，我们把离散的研究对象称为元，并且用点来表示元和元之间可能存在的这种特定关系称为二元关系：如果某两个元之间存在这种关系，就在代表着两个元的点之间连一条线（称为边）。如果不存在这种关系，相应的点对之间就不连线。所谓图，就是有点集V（G）边集E(G)两

4、个集合构成的数学结构。记为G=(V(G),E(G)),除了某些带有特定意义的情况外，点的位置·边的画法都是无关紧要的，只要保证点和边的关联关系。由于图可以代表各种离散对象之间的二元关系，因此它的应用就非常广泛，即使某些问题可以用其他方法解决，采用图的表示方法也可以是问题得到直观明了的解释，这就是图的应用面更广泛。在图G中，边是点的无序对。如果e=uv,那么就称边e连接u和v，也称点u和点v是e的两个端点，假若u是e的一个端点，则称u和e相互关联，关联同一点的两条边称为是相邻的。与同一条边关联的两个点也称为相邻点。关联关系是指点和边的关系；相邻关系则可能是边和边的关系，也可能点和点的关系，例如

5、，在图6—1所示的图中，v1和边e1，e6，e7关联；v1也和点v2，v4，v6相邻；而边e1则和e2，e7，e8，e6相邻。由于图由点集V和边集E组成，它本身也是一个集合。因此，和一般集合存在子集一样，它也有子图的概念。对于一个图G，如果有另一个图H，它的点集V（H）是G的点集V（G）的子集，它的边集E（H）也是G边集E（G）的子集，即V（Ｈ）V（G），E（H）V（G），并且E（H）中的边仍然保持它在G中关联关系，也就是说，E（H）中各条边e的端点和这条边在G中的端点一样，那么我们就称H是G的一个子图，记为HG。简单的说，子图就是原来图的一部分。图6—2给出一个图G和它的一个子图H。子图的

6、概念非常重要，图论所讨论的就是各种各样的子图，下面我们也将看到，图上的一些最优化问题，就是在具有某种特性的子图类当中寻找最优子图的问题。6.2最短问题在实际生活中，存在许多需要求出图上从一点到另一点的最近“走法”的问题，例如要从甲地到乙地，希望在交通图上找出一条距离最短的路。要把货物从某一城市运到另一城市，也许有许多转运的途径，希望找到一种方案，或者要求总的运输时间最短，或者要求总的费用最省。这些问题，抽象到图上，就是最短问题。图论中所说的路，是指一列以点开始并以点结束的点和边的交错序列：P=v0e1v1….v(n-1)e(n)v(n),其中v0，v1，….vn是图上的点，e1，e2，…..

7、，e(n)是图上的边，并且ei是连接v（i-1）与vi的边，这个序列P称为一条v0vn路，v0是他的起点，vn是它的终点。严格的说，还要求路上各点都不相同。就图所带边的实际意义而言，路可以代表从甲地到乙地的不同走法，也可以代表货物的转运方案。为寻求最优走法或最优方案，自然要考虑数量关系。这种数量关系，是建立在图上的各条边所对应的“数”的基础之上。这个数可能代表交通图上公路段的实际长度，也可能代表货物运输过程中