第6章 图上的最优化问题

第6章 图上的最优化问题图论是近几十年来较为活跃的一个应用数学分支，它应用广泛，在物理化学生物等学科领域都有许多成功应用的范例，特别是计算机科学，更有其重要的地位，在生产技术经营管理投资决策乃至社会科学和日常生活中，也可以找到用其思想方法计算方法解决有关问题的例子。用图求实际问题具有直观明了的特点，这一特点促进了讨论方法应用范围不断的扩大。初步掌握图论的基本理论和方法，并不要求有较深的数学基础，对中学生而言也并不是十分困难。这一章将介绍图论的初步知识及其在最优化问题中的一些应用。6.1图和子图早些年，中国科技大学招收少年班的测试题中有这样一道题：假定有6个点，其中任意3个点都不共线，用红蓝两种颜色的直线将这些点两两连接起来，要证明必定存在一个三角形，他的三条边的颜色是相同的，我们用图论的方法来讨论这道题。首先，我们任取6个点v1,v2,.,v6. 如果v1和 v2两点间用红线连接，那么就在该两点间连一条边；如果是用蓝线连接的，就不连边。这样就得到一个图，图61就表示一种连接方法。在这张图上，和v1有边相连的点有v2，v4，v6，显然， 如果这3个点之间至少有一条边相连，那么这条边得两 个端点加上v1就构成一个红色的三角形；反之（如图 所示）这3个点就将形成一个蓝色的三角形。以上用点以及连接一堆点的线（图论中称为边）所构成的图形就是图论的研究对象图。这种图，有别于通常意义上的图，如几何图形机械零件图等等。他可以用来表示很多离散对象之间的内在联系。现实生活中有许多离散的对象：例如一个国家或地区内的城市化化工厂的各类产品某次竞赛中的参赛队等等；这些对象之间有存在着某种特定的关系：城市之间是否存在直达航空线，化工厂的产品能否储藏在同一个仓库内，参赛队之间在比赛中是否会相遇等等。这些关系又带来一些相应的数学问题。首先，我们把离散的研究对象称为元，并且用点来表示元和元之间可能存在的这种特定关系称为二元关系：如果某两个元之间存在这种关系，就在代表着两个元的点之间连一条线（称为边）。如果不存在这种关系，相应的点对之间就不连线。所谓图，就是有点集V（G）边集E(G)两个集合构成的数学结构。记为G=(V(G),E(G),除了某些带有特定意义的情况外，点的位置边的画法都是无关紧要的，只要保证点和边的关联关系。由于图可以代表各种离散对象之间的二元关系，因此它的应用就非常广泛，即使某些问题可以用其他方法解决，采用图的表示方法也可以是问题得到直观明了的解释，这就是图的应用面更广泛。在图G中，边是点的无序对。如果e=uv,那么就称边e连接 u和v，也称点u和点v是e的两个端点，假若u是e的一个端点，则称u和e相互关联，关联同一点的两条边称为是相邻的。与同一条边关联的两个点也称为相邻点。关联关系是指点和边的关系；相邻关系则可能是边和边的关系，也可能点和点的关系，例如，在图61所示的图中，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的一个子图，记为H G。简单的说，子图就是原来图的一部分。图62给出一个图G和它的一个子图H。子图的概念非常重要，图论所讨论的就是各种各样的子图，下面我们也将看到，图上的一些最优化问题，就是在具有某种特性的子图类当中寻找最优子图的问题。 6.2最短问题在实际生活中，存在许多需要求出图上从一点到另一点的最近“走法”的问题，例如要从甲地到乙地，希望在交通图上找出一条距离最短的路。要把货物从某一城市运到另一城市，也许有许多转运的途径，希望找到一种方案，或者要求总的运输时间最短，或者要求总的费用最省。这些问题，抽象到图上，就是最短问题。图论中所说的路，是指一列以点开始并以点结束的点和边的交错序列：P=v0e1v1.v(n-1)e(n)v(n),其中v0，v1，.vn是图上的点，e1，e2，.，e(n)是图上的边，并且ei是连接v（i-1）与vi的边，这个序列P称为一条v0vn路，v0是他的起点，vn是它的终点。严格的说，还要求路上各点都不相同。就图所带边的实际意义而言，路可以代表从甲地到乙地的不同走法，也可以代表货物的转运方案。为寻求最优走法或最优方案，自然要考虑数量关系。这种数量关系，是建立在图上的各条边所对应的“数”的基础之上。这个数可能代表交通图上公路段的实际长度，也可能代表货物运输过程中通过该段路径的时间，花费的代价等等。从实际问题中抽象出来，就是对于图中的每一条边e属于E,都确定一个实数W（e）与之对应。这种定义在图的边集E上的实值函数，称为图的边权函数，W（e）就是边e的权，定义了边权函数的图，称为赋权图。在赋权图上，路就有了“长度”的概念。对于一条路P=v0e1v1.v（n-1）e（n）v(n),记E（P）=e1,e2,.,en,(E(P)表示路P上的边的集合)，路P上所有边的边权的和，即就是路p的长度，记为W（p）。他表示实际问题中的某条交通路线的路程总长，或某种运输方案花费的总时间或总费用，等等。容易看出，在一张图上，从一个点u到达另一个点v的路通常不止一条，这些路的长度又往往各不相同。其中总长度最小的那条路就称为uv间的最短路。特定的长度称为uv间的距离，记作d（u，v），用数学式子表示，就是d(u,v)=minW(P)= 这里，E(p)是P上所有边的集合，W（e）是边e的权， 是对P上的所有边求和，而极小化min是对所有的uv-路而言的。寻找赋权图上的最短路，戴斯特拉（Dijkstra）在1959年提出了一个算法。他的步骤是：（1） 置L（u0）=0，对所有的vu0，置L（v）=，s0=u0，i=0；（2） 对于每一个v，即不属于集合Si的点），以L（ui）+W（uiv）取代L（v）。计算，并记使之达到最小的一个点为ui+1，置Si+1=Sui+1；（3） 以V(G)表示图G的点的总数。假若i=V(G)1,则算法终止，否则（即当iV(G)1时）用ui+1取代ui，i+1取代i，并转回步骤（2）。用戴斯特拉算法可以计算从点u0到其余各点的最短路。例1在6-3给出的图中，试计算从点u0到其余各点的最短路。图中各边旁所给出的数为该边的权。解 采用戴斯特拉算法：（1）置L（u0）=0，L（vj）=（1，2，、，7），S0=u0，i=0； (2) 由L（u0）+W（u0vj）和L(vj)相比，用较小者取代L(vj)，得L（v1）=2，L（v2）=4，L（v3）=3，其余的点L（vj）保持不变（注意，如果边uiv不存在，则视W(uiv)=）。计算即L（v1），故取u1=v1，S1=u0，v1；（3）用u1取代u0，转回步骤（2），用L(u1)+W（u1vj）和原有的L（vj）进行比较，可得L(v4)=L（v1）+W（v1v4）=5，其余点的L(vj)仍然不变。此时。故取u2=v3，S2=u0，v1，v3。如此往复，直到所有的点都归到Si中去用这样的方式表述起来很不方便。为使表达简洁明了，我们可以吧每次往复计算的结果列成一张表，并把有些只记录过程的信息不在表中列出。这样可以得到表6-1.表中底下画短线的数字就是从u0到该店的距离d（u0，vj）。表6-1U0V1V2V3V4V5V6V7i=00i=1343u1=v1i=2435U2=v3i=3459U3=v2i=4587U4=v4i=58712U5=v6i=6811U6=v5i=7810U7=v7此外，我们还可以用向上追溯的方法从数字变化情况方向推出从u0到过点的最短路。例如要求从u0到v6的最短路。我们从v6列最后的数字7追溯上去，得知它是从v2得来的，即L(v2)+W(v2v6)=7，可见u0到v6的最短路必定是u0到v2的最短路加上边v2v6组成。类似地，我们可以求出u0到其余各点的最短路（见图6-3中用粗线表示的路线）。这里应当指出，戴斯特拉算法只对所有边的权都是非负实数的赋权图适用。在某些特许殊问题中，有些边的权可能会出现负值，这是戴斯特拉算法是行不通的。此外，上述算法给出的是从一点u0到其余各点的最短路。图中只要求出u0到某个指定点的最短路，那么只要计算到给指定点被归到Si中去，也就是表中改点所在的列下面的数字被加上短线就可以终止了。例2图6-4所示是某县级市A及其邻近几个乡镇之间的公路示意图（图中各边上的数字为个公路段的公里数）。试求出从A到各乡的最短路（上海市2004年初赛）。 解 用戴斯特拉算法，列成表6-2.表6-2ABCDEFGHIJK010.16.212.97.69.37.810.112.97.69.37.810.112.916.29.315.57.810.112.916.29.315.520.310.112.916.218.115.516.812.916.218.115.516.816.216.115.516.816.216.116.816.216.816.8 下面画线的数字表示A到各乡的最短距离，用追溯方法可以得到各条路（图）6.3 最小生成树问题 图论的另一类最优化问题是最小连接问题，就是要在赋权图的边集之中选出一些边，既能把图上所有的点连接起来，又要使它们的边权之和达到最小，这就是求赋权图的最小生成树问题。 要讨论这个问题，首先解释图论中树的概念。 树是指一类连通且没有圈的图。树是最基本、最重要的图类之一。图6-5所示就是具有6个点的各种树。所谓树是连通的，是指图中任意两点之间都可以找到一条路。而所谓圈，是指起点和终点重合的“路”（也称回路）。而树要求不存在任何圈。 连通和无圈是树这类图的特征。具有这两条基本性质的图都有点类似自然界中树的形状，这类图也因此得名。 由这两条基本性质，还可以推出树的许多性质。首先，树上任意两点间恰有一条路连接。这是因为树的连通性保证了任意两点间路的存在性。而若存在两条不同的路，那么有这两条路组成的图中必然会包含圈，这与树的无圈性质矛盾。其次可以用数学归纳法证明，树的边数一定等于点数减1。此外，在树上任意的两点间添上一条边，就会得到恰有唯一的一个圈的图，这个圈就是由添上去的边加上原先连接这两个点的那条唯一的路构成。 树又是一种“最小的连通”图。树原来是连通的，但是在树上任意去掉一条边，树就变成不连通的图了（图论中称这种边为割边，也就是说树上的每条边都是割边），因为在原来的树上连接该边两个端点的唯一的路就是这条边。一旦去掉这条边，这两点间就没有路可连通。类似的，任意去掉树上的一个点（同时也去掉和它关联的边）。只要这个点不是悬挂点*（只同一条边关联的点），树也将失去原有的连通性（类似地这种点也称为割点）。因此从连通的意义上看，树具有极小型。既然树是最小的连通图，那么要把一些点用最少的边连接起来，就一定至少要连成一个树。反过来，对于任意一张连通的图来说，要找到一个既能保持原有的连通性，又是尽可能小的子图也必然是一个树。这就是这一节要讨论的连接问题。连接问题显然有它的应用背景。一家跨国公司为保持其分布在世界各地子公司与总公司的信息传递，至少必须由一个作为“热线”的树保持联系。学校里要把全部计算机连成校园网，也必须至少连接成一个树。 在连接问题中，如果进一步考虑边的代价，也就是说既要考虑点的连通性，又要考虑连一条边所花费的代价，这种要求总代价最小的问题，就是最小连接问题，在赋权图中，就是最小生成树问题。 第一节中，我们介绍了子图的概念。对于一个图G ，如果存在图H，使V（H）V（G），E(H) E(G),并且E(H)中的边保留在G中的关联关系，就称H是G的一个子图。若进一步要求H中所有的点就是G中所有的点，即V(H)=V(G)，则子图H 就称为G的一个生成子图，如果G的一个生成子图T又是一个树，那么T就叫做G的一个生成树。图6-6中用粗线标出的子图分别是原图的一个生成子图（图6-6（a）和一个生成树（图6-6（b）。容易看到，连通的图一定包含生成树，而且在通常情况下，生成树还不止一个。由树的性质可知，这些不同的生成树的边数都是一样的（都等于点数减1）。然而，在一个赋权的连通图里，不同的生成树，他们所含的边的权的总和将是不一样的。其中，边权之和最小的生成树就是最小生成树。在一个赋权图G中求最小生成树的问题可以表示为 MinW(T)=T是G的生成树对于前面所说的最小连接问题，只要把连接起来的点以及可能连接的方案用一张图来表示，每条连线的代价就是各条边的权，于是最小生成树就是总代价最小的连接方案。1956年，克鲁斯考尔（krustal）提出了赋权图最小生成树的算法。这个算法的核心可以简单地用一句话来概括，就是在不构成任何圈的前提下，依次挑选出权最小的边，直到挑选不出别的边位置。可以证明，对于连通图来说，克鲁斯卡尔算法终止时。所挑选出的边一定够成原图的一个最小生成树。例3 寻找图6-7所示的最小生成树（图中各边上的数字为各边的权）。解 由克鲁斯卡尔算法。逐次选出边权为1，2，2，3，5，6的各条边。这些边就构成原图的一个最小生成树（图中用粗线表示）。 当然，同一个连通图中可能会有若干个不全相同的最小生成树。在上例中，用另一条边权为3的边取代原来所取的那条边，或者将边权为6的那条边换成另一条边权相同的边，都可以得到另外的生成树。由于他们的权和是一样的，也就是说都是最小的生成树，只是在执行算法的过程中按不同的顺序挑“最小”边所得到的不同结果。 下面再举两个实例。例4. 在图6-4所示的是县级市A及其邻近几个乡镇之间公路示意图中，如果要建城镇之间的一个通讯网络，连线要求沿公路布置。费用与长度成正比，问：如何连接可以使总费用最省？（上海市2004年初赛题） 解 根据题意，这是一个最小生成树问题，由克鲁斯卡尔算法，依次选择BF，AC，GD等边。按这些边连接，就可以得到是费用最小的通讯网络建设方案（如图6-8所示）。例5. 某区下属5个街道，他们的相对位置及距离由图6-9表示（单位：千米）。区政府准备投资建设一个网络以传输内部文件。假定建设费用与距离成正比。请为它们设计一个费用最省的建造方案。解 根据题意。此题依然是一个最小连接问题。有克鲁斯卡尔算法，依次选择GE，CD，BC，GC，GA各条边，便可得到使总费用最省的连接方案（图略）。在前面两节中我们分别讨论了图的最短路和最小生成树两类最优化问题。这两类问题的数学表达式完全类似。这种共同的属性也是图上的其他最优化问题所共有的。这就是从图（一般是指赋权图）的具体某种属性的一类子图（例如，最短路问题中所有的uv-路，最小生成树问题中所有的生成树等等）中寻找一个最优解（就是指使边权和达到最小或者最大的一个子图）。用数学式子表示，就是： min(或max)W(H)=H式中，是指图中具有某种特定属性的所有子图。6.4 边的行遍性和邮递路线问题邮递路线问题是我国数学家管梅谷教授在1960年提出并解决的一个实际问题，一位邮递员要从邮局出发，走遍他所管辖的投递范围的大街小巷，然后回到邮局。这个问题属于图上边的行遍问题。对于边的行遍问题的研究，起源于欧拉关于七桥问题的讨论。格尼斯堡是东普鲁士联邦的一个城市。在18世纪初，当地居民提出这样一个问题：一位旅行者能否从其中一块陆地出发，去游览这7座桥。要求既不遗漏又不重复，然后回到出发点。当时，这个问题难倒了当地的居民。后来，是欧拉把它等价地表示为如图6-10（b）所示这样一张图上的一笔问题，并且给出了符合条件走法的一个必要条件：图上每个点关联的边数必须是偶数（这种点被称为偶点），从而解决了这个问题。欧拉的结果，用图论的术语可以进行如下表述：首先，我们把图上首尾相接的一列边称为一个通道，起点和终点重合的通道称为闭通道。能包含所有边的闭通道称为图的一个环游。显然，在满足一定条件时，边数最少的环游是经过图上每条边都恰好一次的情况。这种环游（如果存在）被称为欧拉环游。而欧拉的结论便是：欧拉环游存在的必有条件是图上每个点都是偶点。后人还补充证明了这个条件对于连通图而言是充分的。习惯上把这种图称为欧拉图。如果把上述条件适当放宽点，改为不要求回到出发点。图上经过每条边并且都只经过一次的通道（如果存在）称为欧拉迹。容易看到，一个图存在欧拉迹的充要条件是：联通并且恰好有两个奇点。这种图有时也被称为半欧拉图。欧拉图和半欧图都是可以一笔画的图。回到前面所说的邮递路线问题上来。一般情况下，邮递员投递范围i的图不可能恰好是一个欧拉图。这就意味着要走遍所有的边必定有些边会有重复。从优化的角度看，当然希望重复的路程越短越好。用图论的语言来说，就是添加一些重复边，以消除原来图上的奇点，把它改成欧拉图，并且要求添加边的边权之和最小。这个问题在国际上被称为中国邮递员问题。管先生1960年发表在数学的实践和认识上的文章指出，只要添加上去的重复边满足条件：（1） 没有重叠的添加边，即任意一段路不走3次或3次以上；（2） 在任意的圈上，添加边的总长不超过圈长的一半。那么这样的添法一定是最优的。对于一个欧拉图，从任何一个点开始都能找到走遍所有边然后回到出发点的方法。只要走法符合弗洛瑞（Fleury）给出的一个判定条件：不走剩下图的割边（割边的意义见6.3）。例6 一位邮递员的投递范围如图6-11所示（单位：百米）。请为他设计最佳投递路线。解 图上一共有14个奇点，可以添加一些重复的边来消除这些奇点。图6-12中粗线给出的是一种添法。在这个图上已经不再有奇点了，因此满足欧拉环游。并且容易见到，所添加的边满足管先生给出的两个条件，添法是最优的。遵照弗洛瑞的原则，环游的任何一种走法都是邮递员的最佳路线。 6.5 点的行遍性和旅行商问题在图上，如果有关于边的问题，通常就会有类似的关于点的问题。行遍性问题也不例外。1859年，英国的哈密尔顿（Hamilton）爵士称他发明了一种游戏，叫做“周游世界”。就是将一个正十二面体的20个顶点看成世界上的20个城市，正十二面体上的30条棱看成城市之间的交通线，游戏是从其中一个城市出发，沿着交通线既不遗漏又不重复地走遍所有城市然后回到出发点。游戏的结果非常简单，很轻易的就能找到满足条件的走法。但是游戏却提出了历经一个半世纪没有能解决，并且已经被公认为解决不了的问题。这就是任意一张图上，是否存在包含所有点的圈（或路，如果不要求回到出发点）的判定条件。当然，这里的圈或路上的边和点都不能重复。图论中把这种圈（路）称为哈密尔顿圈（路），这种点的行遍性问题也就称为哈密尔顿问题。这里我们不准备讨论哈密尔顿圈（路）的存在性问题，只讨论与它相关的一个最优化问题旅行销售员问题。旅行销售员问题是一个非常著名的世界难题。问题的原型是：一个推销员，要到若干个城市去推销他的商品，然后回到出发点。如果已经知道每两个城市之间的旅行费用，应如何设计他的旅行路线，才能使他总的旅行费用最省？首先，我们用n个点表示他所要到的各城市（不妨也包括触发点），用连接这些点对的边表示城市间的旅行路线（如直达航班）。边权就是给段旅行路线的代价、时间或费用等。假定任意两个城市之间都有直达路线（在没有直达路线的情况下是可用该两地的最短路代替，就问题的原型而言，允许点有重复的情况下是可行的），俺么所得到的图就是一张有n个定点我的完全图Kn(任意一对点间恰有一条边的图称为完全图)。容易看到，旅行销售员问题就是在这样一张赋权完全图上寻找权最小的哈密尔顿圈。用数学式子报时就是：MinW(H)= W(e)H是Kn的哈密尔顿圈显然在完全图Kn上，点的人已排序都对应着一个哈密尔顿圈。容易证明，Kn中不同的哈密尔顿圈共有个。TSP就是在这样的一个有限的集合上寻找最优的问题。对于较小的n，我们可以把所有的哈密尔顿圈都找出来，然后对他们的权进行比较，从中找出最优解，但是，当n比较大时，由于n！的增长速度非常快，用这种枚举方法求解的工作量将变得连最先进的电子家算计都无法在合理的时间内完成。为此，许多专门研究组合最优化的专家，学者都曾经试图寻找TSP的有效算法，结果都未获得成功。知道20世纪60年代后期，人们才发现TSP是一类被称为NP完全类问题的核心问题之一。这类问题都是不存在（至少就人们当前的能力而言）有效地算法的。于是人们就转而研究一些方法，能在较短的时间内找到近似结果。这种结果虽然通常不是最佳方案，但相对来说是比较好的。这种方法称为近似算法。在TSP的近似算法中，最简单的方法称为”最近邻点法”:先从一点v1出发，在与v1相邻的点中找到最近（即边权最小）的点v2；再从v2出发，从剩下的点中找到最近的邻点作为v3，、，一次类推，知道走遍所有的点，最后回到出发点。这样所得到的哈密尔顿圈当然不一定是TSP的最优解，而只能当作“近似最优解”。TSP的另一种近似算法称为“最小插入法”。这种方法是先找一条权最小的边，记咗v1v2。在再剩下的点中选择v3，是W(v1v3)+W（v2v3）尽可能小，这样就形成一个由3点组成的圈v1v2v3；接着再在剩下的点中挑选v4，是MinW(v1v4)+W（v2v4），W（v2v4）+W（v3v4），W（v3v4）+W（v1v4）尽可能的小，并且把它插进去而得到哈密尔顿圈。这种方法的计算工作量比最近邻点发所需的工作量要大得多。但是相对来说，其效果也要比最近邻点法好。、下面举例说明这两种方法。例7 表6-3给出了6大城市伦敦（L）、巴黎（P）、北京（B）、东京（T）、纽约（N）和墨西哥（M）之间的航空距离（单位：千米）。试求最佳TSP路线。表6-3LMNPBTL8943558234481649588M8943363392121247511319N5582336358501101210872P3449212585082389739B8164124751110282382103T9588113191087297392103解 假若从北京出发，采用最近邻点法，依次可以得到打喔东京伦敦巴黎纽约墨西哥城，然后回到北京，总里程为33723千米。、若给从巴黎出发，同样采用最近邻点法，则可得到路线巴黎伦敦纽约墨西哥城东京北京，然后回到巴黎，其总长度为30949千米。由此可见，同样的方法不同的起点，可能导致不同的近似最优解。如果改用最小插入法，首先选择最小边巴黎伦敦，然后选起纽约插入，称为PLNP的圈，在意墨西哥城插入纽约巴黎之间，形成PLNMP的圈，再一次将东京、北京插入得到与上面第二条路线相同的结果。事实上，用枚举法可以证明，第二种方案是原问题真正的最优解。例8 图6-13所示为某交警支队所辖管区交通岗分布情况，图上各边旁的数字为该短路的长度（单位：百米），今年高温天持续时间较长，市公安局领导前来管区慰问一线交警，请为他们设计一条最佳的访问线路（从队部出发，途径所有岗位，然后回到队部）。又：如果PH段路上突发事故，交通严重堵塞，那么至少将多走多少路？（上海市2005年决赛题）解 访问路线是一个点的行遍性问题，采用最近邻点法，克的最佳线路：PHGEFABDC P。总长度为24.2千米。、PH路线堵塞，相当于图中删去了该条边，同样采用最近邻点法，应该走PDBAEFGHCP 总长度为26.1千米，将多走1.9千米。哈密尔顿问题的另一个应用背景是一类加工顺序安排问题。假定有J1,J2,.Jn共n件工件要在同一台床上加工，而加工完Ji工件后紧接着加工Jj工件需要花费一定的准备时间tij（ij，i，j=1，2，、，n）。应当怎样安排加工顺序，才能使完成者n件工作加工而消耗在准备工作上时间最短粗看起来，它与TSP问题一样，但事实上且有一些区别。这是因为一般情况下，tijtji。因此，再用前面所说的完全图来描述这里的情景就存在问题。图论中的做法是用从Ji到Jj和从Jj到Ji两条带方向的边来表示两种不同的顺序。这种由带方向的边（称为右向边）构成的图称为有向图。相应的就有有向路、有向圈等概念。而这类加工顺序的问题就是在一个有方向图撒很难改寻找有向哈密尔顿路的数学模型，这里不准备再做详细的讨论，只是指出，他的困难程度与TSP相当，近似算法也可相互通用。例9 有6个工件需要在一台机床上加工，准备工作时间tij见表6-4（单位：分钟）。试求最加工顺序。表6-4ijJ1J2J3J4J5J6J21-1232J325-123J4144-12J51345-5J644231 解 从J1开始，用最近邻点法可得哈密尔顿路J1J6J5J2J3J4，消耗时间7分钟，比按自然顺序加工消耗时间13分钟要好许多。 若改由J2开始，则最近邻点法给出的加工顺序为J2J3J4J5J1J6,消耗时间仅为5分钟，显然这个结果必定是最优解。6.6 工作的合理安排 倘若有n个不同的工作岗位，需要安排n为工人去分别承担，而每位工人都只能胜任其中的某几项工作。问：是否存在一种分配办法，使每位工人都担任一项他力所能及的工作，而每项工作都有人去完成？这个问题就是所谓的指派问题。 我们还是用图的方法俩表示。首先，我们去2n个点x1，x2，.，xn和y1，y2,.yn分别代表着n位工人和n项工作。假若第i位工人能够胜任第j项工作，我们就在代表这位工人的点xi和代表该项工作的点yj之间连一条边，否则就不连边。这样，就够再出一张表示能胜任工作的关系图。如图614所示。容易看到，这一类图具有一种特殊的结构。首先他的顶点集V被分成X和Y两个非空且不交的子集，其次它的边集中任意一条边的两个端点都是一个在X中，另一个在Y中我们把具有这种结构的图称为二分图。如果安排某位工人去承担一项他能胜任的工作，就相当于在这张图上跳出一条相应的边。而若每位工人至多被分配担任一项工作，每项工作至多由一位工人承担，那么这样挑出来的边将没有公共端点。例如图6-14中粗线表示：x2承担y4,x3承担y3、x4承担y5、x5承担y1.这种没有公共端点的边子集在图论中称为对集。一般来讲，如果存在一个边的子集M E，使M中的任意两条边都没有公共端点，则称M是图的一个对集。 M中的任一条边的两个端点称为在M中配对，被配对的点称为M饱和的；否则称为M未饱和的。如果图中所有定点都是M饱和的。那么这个对集就曾为是图的一个完美对集。对于n为工人和n项工作的指派问题，就是研究一个X=Y的二分图中完美妒忌是否存在的问题（这里X示集合X中的元素个数）。根据霍尔在1935年得到的结果，在一个具有顶点集的二分图X和Y的二分图中，存在一个对集饱和X中所有顶点的充分必要条件是：对于X的任意一个子集S，都有 N(S) Y其中，N(S)是指和S中的点有边相连的所有顶点 所构成的集合，称为S的邻集。显然，由S X,有N(S) Y。这个结果称为霍尔定理，它是研究二分图对集问题最重要的结论。理解霍尔定理并不困难，如果S是指部分工人的集合，倘若存在一种分配使S中每位工人都分别承担一项他们所胜任的工作，那么至少他们能胜任的工作集合不可能少于这些工人的人数。对于一般二分图对集而言，当然结构是一样的。利用霍尔定理的思想可以求得图中边输尽可能多的对集（图论中称为最大对数）。首先，任意找一个对集M。检查它是否已经饱和了X的所有顶点。如果是的，那么这个对集显然已经是最大对集了；如果不是，我们就取一个M未饱和的点uX。把和它有边相连的点都画出来。吐过其中有一个M未饱和的点v（vY）,那么在M中填上一条uv边，得到的边子集仍是一个对集，于是我们得到一个边数更多的对集。于是由取代原来的M重新开始寻找。如果所有和u相邻的点都是M饱和的，那么在由u和它相邻的点所画成的子图上填上与那些点配对的点和相应的边，从这些配对的点出发再找相邻的点。如此往复，得到一个像树一样的子图。我们用例子来开始来解释。先看图6-14所示的二分图以及用粗线标出的对集M。由于M没有饱和X的所有顶点，我们挑出x1X，它是M没饱和的，然后将与x1相邻的点y3 和y4画上。由于y3，y4都是M饱和的，我们就把和他们配对的点x3和x2以及边y3x3和y4x2（都属于M）添上。再从x3和x2出发画出与它们相邻的其他的点。在看这些点是否M饱和，然后重复以上过程。我们可以得到一个树（图6-15（a）画出的这个树的前面一部分）。这个树有其特殊性：意识从u（图上的x1）开始，点和边都是有层次的。点是依次属于X、属于Y交替出现，边则是不属于M交替出现。这种基于M的数称为M交错树。一旦这个树上再出现一个M未饱和的点（根据做这个树的方法可知，这个点必定属于Y.如图中的点y6）。那么它在交错树上和u相连的那条码唯一的路也是一条M交错路，并且在这条路上不属于M的边比属于M的边多一天。我们把这些属于M的边从M中删去，把不属于M的添进去，就可以得到一个新的对集。这个对集将比M多一条边。本例中就是用边x3y6和x1y3取代议案来对集上的边x3y3，所得的如图6-15（b）所示。重复以上过程就可能找出饱和所有X的顶点的对集。如图6-16（a）和图6-16（b）所示。然而，有时候在交错树上出来u意外，再也找不到去他的M未饱和点，而交错树那些属于X的点，除了树上的点以外也再也没有其他的邻点了这个树也就无法在生长了。于是，就有一个S X即树上属于X的点的集合，有N（S）=S1.根据霍尔定理的结论，原来图上一定找不到能饱和X所有顶点的对集。如入6-17所