问题、模型与求解算法问题、模型与求解算法云南大学数学系云南大学数学系李建平李建平二二OO九年十一月九年十一月内容摘要内容摘要l基础知识基础知识l最小支撑树问题最小支撑树问题l最短路问题最短路问题l匹配问题匹配问题l欧拉问题欧拉问题l中国邮递员问题中国邮递员问题l一些可计算性为一些可计算性为NP-完备的组合最优化问完备的组合最优化问题及数学模型题及数学模型一、基础知识一、基础知识1.1 图与支撑子图图与支撑子图 定义定义1.1 所谓一个（无向）图是指给了所谓一个（无向）图是指给了一个集合一个集合V，以及，以及V中的不同元素的无序对构中的不同元素的无序对构成的集合成的集合E，并记图为，并记图为G =(V，E)。称。称V中的中的元素为图元素为图G的顶点，称的顶点，称E中的元素为图中的元素为图G的边的边。连接两顶点。连接两顶点u和和v的边记作的边记作uv（或者（或者vu），），也称边也称边uv（或者（或者vu）与顶点）与顶点u,v相关联，同时相关联，同时称两顶点称两顶点u和和v是相邻的。是相邻的。太原太原重庆重庆武汉武汉南京南京徐州徐州连云港连云港上海上海郑州郑州石家庄石家庄塘沽塘沽青岛青岛济南济南天津天津北京北京图1.1 定义定义1.2 所谓一个有向图是指给了一个所谓一个有向图是指给了一个集合集合V，以及，以及V中的不同元素的有序对构成的中的不同元素的有序对构成的集合集合A，并记有向图为，并记有向图为D =(V，A)。称。称V中的中的元素为有向图元素为有向图D的顶点，称的顶点，称A中的元素为有向中的元素为有向图图D的弧。以顶点的弧。以顶点u为起点和以顶点为起点和以顶点v为终点为终点的弧记作（的弧记作（u，v），也称与弧（），也称与弧（u，v）与顶）与顶点点u, v相关联。相关联。v3v1v2v4v6v5图图1.2 定义定义1.3给定两个图给定两个图G=(V, E)和和H=(V*, E*)，称，称H是是G的一个支撑（生成）子图，如果的一个支撑（生成）子图，如果V*=V和和E* E。1.2 图的连通性图的连通性 定义定义1.4 （路）给定图路）给定图G=(V, E)，一个点，一个点、边交错的序列、边交错的序列P=（v0 ,e1 ,v1 , e2 , v2 ，e3 , v3 , ,vk-1, ek,vk)，如果满足，如果满足ei=vi-1vi, i=1,2,k,则则称称P为一条连结为一条连结v0和和vk的路，简记为的路，简记为P=v0 v1v2v3 vk-1vk；称；称v0 ，vk分别称为路分别称为路P的起点和终点，的起点和终点，其余称为中间点。其余称为中间点。 定义定义1.5（回路）设回路）设P为一条连结为一条连结v0和和vk的的路，路，如果如果v0 = vk，称该路，称该路P为回路；如果为回路；如果v0vk，称该路，称该路P为为(严格的严格的)路。路。 定义定义1.6（圈）如果路圈）如果路P除起点和终点相除起点和终点相同，中间所含的点均不相同，称这样的同，中间所含的点均不相同，称这样的回路回路P为圈。为圈。 定义定义1.7（连通图）如果图连通图）如果图G中任意两点中任意两点之间均至少有一条路相连，称之间均至少有一条路相连，称G为连通图；为连通图；否则称图为不连通图。否则称图为不连通图。 问题问题1.1：给定图：给定图G，问，问G是连通的吗？是连通的吗？二、最小支撑树问题二、最小支撑树问题2.1 树树 定义定义2.1 一个无圈的连通图称为树。一个无圈的连通图称为树。 树具有如下一些性质：树具有如下一些性质：性质性质2.1 设图设图G=（V，E）是一棵树，）是一棵树，n2， 则图则图G中至少有两个悬挂点。中至少有两个悬挂点。性质性质2.2 图图G=（V，E）是一棵树的充要条件）是一棵树的充要条件 是是G不含圈，并且有且仅有不含圈，并且有且仅有n-1条边。条边。性质性质2.3 图图G=（V，E）是一棵树的充要条件）是一棵树的充要条件 是是G是连通图，并且有且仅有是连通图，并且有且仅有n-1条边。条边。性质性质2.4 图图G是一棵树的充分必要条件是任意是一棵树的充分必要条件是任意 两个顶点之间有且仅有一条路。两个顶点之间有且仅有一条路。2.2 支撑树支撑树 定义定义2.2 设图设图T=(V,E)是图是图G=(V,E)的一的一个支撑子图，如果图个支撑子图，如果图T=(V,E)是一棵树，那是一棵树，那么称么称T是是G的一棵支撑树。的一棵支撑树。v6v5v2v3v4v1图图2.1（a）（b）v6v5v3v1v2v42.3 最小支撑树问题最小支撑树问题 定义定义2.3 设有图设有图G =（V，E；w），如果），如果对于对于G中的每一条边中的每一条边vivj，相应地有一个数，相应地有一个数wij，那么称这样的图，那么称这样的图G为赋权图，为赋权图，wij称为边称为边vivj的权。的权。 这里所指的权，是具有广义的数量值。这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的根据实际研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。含义。例如长度，费用、流量等等。 定义定义2.4 如果图如果图T =（V，E）是赋权图是赋权图G 的一棵支撑树，那么的一棵支撑树，那么E中所有边的权重之和中所有边的权重之和称为支撑树称为支撑树T 的权重，记作的权重，记作w(T)。 如果图如果图G 中支撑树中支撑树T* 的权重的权重w(T*)是在是在G的所有支撑树的所有支撑树T中的权重达到最小者，即中的权重达到最小者，即w(T*) = minw(T) | T为为G的支撑树的支撑树，那么称，那么称T*是是G 的一棵最小支撑树。的一棵最小支撑树。 类似可定义最大支撑树问题。类似可定义最大支撑树问题。 问题问题2.1：给定图：给定图G，如何求，如何求G的一棵最的一棵最小支撑树？小支撑树？ 常用的有破圈算法和避圈算法：常用的有破圈算法和避圈算法：Algorithm 破圈算法破圈算法Input: 赋权图赋权图 G =（V，E；w）Output: G的最小支撑树的最小支撑树TBegin 在图中寻找一个圈。若不存在圈，则已经在图中寻找一个圈。若不存在圈，则已经得到最小支撑树或说明该图不连通，后者不存得到最小支撑树或说明该图不连通，后者不存在支撑树（当然没有最小支撑树）；在支撑树（当然没有最小支撑树）； 若存在圈，去掉该圈中权数最大的边；若存在圈，去掉该圈中权数最大的边； 反复重复反复重复、两步，直到找到最小支撑两步，直到找到最小支撑树或说明该图不连通（故没有最小支撑树）。树或说明该图不连通（故没有最小支撑树）。Endv6v5v2v3v4（a）v162753544v3v2v1v4v6v5513142（b）图图2.2 避圈算法：避圈算法： 从图中依次寻找权重较小的边，寻找过从图中依次寻找权重较小的边，寻找过程中，节点不得重复，即不得构成圈。注意程中，节点不得重复，即不得构成圈。注意在找较小权重边时不考虑已选过的边和可能在找较小权重边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最小造成圈的边。如此反复进行，直到得到最小支撑树或者说明该图不连通，后者不存在支支撑树或者说明该图不连通，后者不存在支撑树（当然没有最小支撑树）。撑树（当然没有最小支撑树）。2.4 顶点加细限制性的最小支撑树问题顶点加细限制性的最小支撑树问题 定义定义 2.5 给定图给定图G =（V，E），在），在G的的某些边内部增加一些顶点，所得到的新图称某些边内部增加一些顶点，所得到的新图称为原图为原图G的顶点加细图（的顶点加细图（subdivision）。）。 问题问题2.2（顶点加细限制性的最小支撑树（顶点加细限制性的最小支撑树问题）给定赋权图问题）给定赋权图G =（V，E；w）及常数）及常数d，寻找图，寻找图G的一棵最小支撑树的一棵最小支撑树T，在，在T上增加上增加尽可能少的顶点，使得到新的（最小）顶点尽可能少的顶点，使得到新的（最小）顶点加细支撑树加细支撑树T*上每条边的权重不超过给定的上每条边的权重不超过给定的常数常数d。 顶点加细限制性的最小支撑树问题的算法顶点加细限制性的最小支撑树问题的算法(1). 利用已有的算法，对赋权图利用已有的算法，对赋权图G求最小支撑求最小支撑树树T，记，记T上权重大于上权重大于d的边为的边为ei1,ei2,eik;(2). 对边对边eij按照下面方式插入按照下面方式插入insert(eij)顶点，顶点，其中当其中当w(eij)是是d的倍数，取的倍数，取insert(eij) = w(eij)/d-1，当，当w(eij)不是不是d的倍数，取的倍数，取insert(eij)=w(eij)/d；(3). 输出支撑树输出支撑树T及插入的顶点。及插入的顶点。 定理定理 2.1（李建平等，（李建平等，Theoretical Computer Science 410 (2009), 877-885）上述）上述算法能够求得顶点加细限制性的最小支撑树算法能够求得顶点加细限制性的最小支撑树问题的最优解，其算法复杂性就是求最小支问题的最优解，其算法复杂性就是求最小支撑树问题的算法复杂性。撑树问题的算法复杂性。 问题问题2.3（顶点加细限制性的支撑树问题）（顶点加细限制性的支撑树问题）给定赋权图给定赋权图G =（V，E；w；c），及常数），及常数B和和d，寻找图，寻找图G的一棵支撑树的一棵支撑树T，满足（，满足（1）eTw(e) B；（；（2）支撑树）支撑树T的顶点加细图的顶点加细图T*上每条边的权重不超过给定的常数上每条边的权重不超过给定的常数d。其。其目标是使得目标是使得eT insert(e)c(e)到达最小。到达最小。 定理定理 2.2（李建平等，（李建平等，Theoretical Computer Science 410 (2009), 877-885） 顶点加细限制性的支撑树问题是顶点加细限制性的支撑树问题是NP-完备完备的；的； 上述问题多项式等价于限制性的最小支撑上述问题多项式等价于限制性的最小支撑树问题（树问题（SIAM Journal on Computing, Vol.33, no.2, 261-268, 2004）；）； 我们能够设计多项式时间算法解决顶点加我们能够设计多项式时间算法解决顶点加细限制性的支撑树问题的三种特殊情形，细限制性的支撑树问题的三种特殊情形，其算法复杂性就是求最小支撑树问题的算其算法复杂性就是求最小支撑树问题的算法复杂性。法复杂性。三、最短路问题三、最短路问题3.1 最短路问题最短路问题 定义定义3.1 设有赋权图设有赋权图G =（V，E; w），），vs,vt是是G中的两个顶点，中的两个顶点，P是是G中从中从vs到到vt的任意一条的任意一条路，路路，路P的权重是指的权重是指P 中所有边的权重之和，记中所有边的权重之和，记作作w(P)。 问题问题3.1（最短路问题）在所有从（最短路问题）在所有从vs到到vt的路的路中，寻找一条权重最小的路中，寻找一条权重最小的路P0，即，即w(P0)=minw(P)。P0称为从称为从vs到到vs的最短路。的最短路。P0的权重的权重w(P0)称为从称为从vs到到vt的距离，记作的距离，记作d（vs，vt）。）。 类似可定义赋权有向图类似可定义赋权有向图D中的最短路问题。中的最短路问题。3.2 反圈反圈 定义定义3.2 给定（无向）图给定（无向）图G =（V,E; w）,若若S V，集合，集合 称为由称为由S确定的反圈（确定的反圈（anticircuit）。）。 类似地，有向图类似地，有向图D=（V，A）,若若S V，集合集合 称为由称为由S确定确定的正向反圈，集合的正向反圈，集合 称为由称为由S确定的反向（或逆向）反圈。确定的反向（或逆向）反圈。3.3 一般形式的反圈算法一般形式的反圈算法 给定图给定图G=（V，E），设），设X(k),E(k)分别是分别是V,E的子集合（初始的子集合（初始k=0时，取时，取X(0)是是V的某个的某个非空子集合非空子集合,E(0)为空集合）。若由为空集合）。若由X(k)确定的确定的反圈不为空集合，根据某些确定的限制条件反圈不为空集合，根据某些确定的限制条件，从该反圈中选取一条或多条边，使得这些，从该反圈中选取一条或多条边，使得这些所选边在所选边在V-X(k)中的端点互不相同。记被选边中的端点互不相同。记被选边的集合为的集合为F(k)，它们在，它们在V-X(k)中的端点集合为中的端点集合为Y(k)。令。令对对 ， 重复上述过程或者终止。重复上述过程或者终止。3.4 利用反圈算法求解最短路问题利用反圈算法求解最短路问题(1) 初值初值X(0)=vs，L(vs)=0;(2)在在 中选一条边中选一条边vivj,使得使得 L(vi)+ w(vi,vj)=minL(vi)+w(vi,vj) 令令L(vj)= L(vi) + w(vi,vj)。(3)当出现下面情形之一时，停止。当出现下面情形之一时，停止。 当当 ，得到从，得到从vs到到vt的最短路；的最短路； 当当 ，但是，但是 ，说明没有，说明没有从从vs到到vt的（最短）路。的（最短）路。3.5 顶点加细限制性的最短路问题顶点加细限制性的最短路问题 定义定义3.3（顶点加细限制性的最短路问题）（顶点加细限制性的最短路问题）给定赋权图给定赋权图G=（V，E；w；vs,vt），及常数），及常数d，寻找图，寻找图G中从中从vs到到vt的一条最短路的一条最短路P(vs,vt)，在在P(vs,vt)上增加尽可能少的顶点，使得到的最上增加尽可能少的顶点，使得到的最短路短路P(vs,vt)上每条边的权重不超过给定的常数上每条边的权重不超过给定的常数d。 顶点加细限制性的最短路问题的（标号）顶点加细限制性的最短路问题的（标号）算法：算法：(1) 取取X(0)=vs，E(0)=空集，空集，L(vs)=0；(2) 在在X(k)确定的反圈确定的反圈 中选取满足条件中选取满足条件的全部边的全部边uv放入放入F(k)， 这里这里u属于属于X(k)，v不不属于属于X(k)L(u)+w(u,v)=minL(u)+w(u,v)|u属于属于X(k)，v不属于不属于X(k)直到直到vt属于某个属于某个X(k),转转(3)；或者无边可选；或者无边可选（停止）；（停止）；(3) 当存在当存在vt属于某个属于某个X(k)，在，在E(k)中（递归）中（递归）去掉那些不能到达去掉那些不能到达vt的顶点及其关联的边；的顶点及其关联的边；(4) 在新图在新图Gk=(X(k), E(k)中构造新的权重，对中构造新的权重，对边边e属于属于E(k)，当，当w(e) d时，取时，取w(e)=0，当，当w(e)d时，取时，取w(e)= insert(e)，其中当，其中当w(e)是是d的倍数，取的倍数，取insert(e)= w(e)/d-1，当，当w(e)不是不是d的倍数，取的倍数，取insert(e)= w(e)/d；(5) 相应地，在新图相应地，在新图Gk=(X(k), E(k)中，对边中，对边e属属于于E(k)，当，当w(e)d时时, 插入插入insert(e)个新的顶个新的顶点；点；(6) 在新图在新图Gk=(X(k), E(k)中按照新的权重中按照新的权重w，计算从计算从vs到到vt的一条最短路的一条最短路P(vs,vt)；(7) 输出最短路输出最短路P(vs,vt)及插入的顶点，这里最及插入的顶点，这里最短路短路P(vs,vt) 关于关于w的权重就是所求路的权重，的权重就是所求路的权重，关于关于w的权重就是所增加定点的数目。的权重就是所增加定点的数目。 定理定理 3.1（李建平等，（李建平等，submitted to Algorithmica 2007）上述算法能够求得限制）上述算法能够求得限制性的最短路问题的最优解，其算法复杂性就性的最短路问题的最优解，其算法复杂性就是求最短路问题的算法复杂性。是求最短路问题的算法复杂性。 问题问题3.4（顶点加细限制性的最短路问题）（顶点加细限制性的最短路问题）给定赋权图给定赋权图G =（V，E；w，c; vs,vt），及常），及常数数B和和d，寻找图，寻找图G中从中从vs到到vt的一条路的一条路P(vs,vt)，满足（，满足（1）eP(vs,vt) w(e) B；（；（2）使得）使得路路P(vs,vt)的顶点加细图中每条边的权重不超的顶点加细图中每条边的权重不超过给定的常数过给定的常数d。其目标是使得（费用）。其目标是使得（费用） eP(vs,vt) insert(e)c(e)到达最小。到达最小。 定理定理 2.2（李建平等，（李建平等，submitted to Algorithmica，2007） 顶点加细限制性的最短路问题是顶点加细限制性的最短路问题是NP-完备完备的；的； 上述问题多项式等价于限制性的最短路问上述问题多项式等价于限制性的最短路问题（题（Mathematics of Operations Research, vol.17, no.1, 36-42, 1992）；）； 当当B表示图表示图G中从中从vs到到vt的最短路长度时，的最短路长度时，我们能够设计多项式时间算法解决该问题；我们能够设计多项式时间算法解决该问题； 当只计算顶点加细的数目时，我们能够设当只计算顶点加细的数目时，我们能够设计多项式时间算法解决该问题。计多项式时间算法解决该问题。四、匹配问题四、匹配问题4.1 背景背景 在生活中经常会遇到这样的问题，如某单在生活中经常会遇到这样的问题，如某单位需要指派位需要指派 n 个人去完成个人去完成 n 项任务，每个人只项任务，每个人只做一项工作，同时，每项工作只由一个人完成做一项工作，同时，每项工作只由一个人完成。由于各人的专长不同，每个人完成各项任务。由于各人的专长不同，每个人完成各项任务的效率也不同。于是产生了应指派哪一个人去的效率也不同。于是产生了应指派哪一个人去完成哪一项任务，使完成完成哪一项任务，使完成 n 项任务的总效率最项任务的总效率最高（如所用的时间为最少）。我们把这类问题高（如所用的时间为最少）。我们把这类问题称之为指派问题或分派问题称之为指派问题或分派问题(Assignment Problem)。 求解这样的问题时，需要引入变量求解这样的问题时，需要引入变量 xij , 其取其取值只能是值只能是 1 或或 0，并令，并令 ： 当问题是要求极小化时的数学模型是：当问题是要求极小化时的数学模型是：4.2 匹配问题匹配问题 定义定义4.1 给定图给定图G=（V，E），如果），如果M是是E的子集合，当的子集合，当M中任意两条边都不相邻，则中任意两条边都不相邻，则称称M是图是图G的一个匹配的一个匹配(matching)。 当图当图G的匹配的匹配M的元素个数恰好为顶点的元素个数恰好为顶点数的一半时，称数的一半时，称M是图是图G的完美匹配。的完美匹配。 问题问题4.1 （最大基数匹配问题）寻找图（最大基数匹配问题）寻找图G的匹配的匹配M，使得，使得M中含的元素个数最多。中含的元素个数最多。 问题问题4.2 （最优匹配问题）对于赋权图（最优匹配问题）对于赋权图G =（V，E; w），寻找图），寻找图G的匹配的匹配M，使得，使得M中含的元素的权重之和最大。中含的元素的权重之和最大。 问题问题4.3 （最小或最大完美匹配问题）对（最小或最大完美匹配问题）对于赋权图于赋权图G =（V，E; w），寻找图），寻找图G的完美的完美匹配匹配M，使得，使得M中含的边的权重之和达到最中含的边的权重之和达到最小（或最大）。小（或最大）。4.3 求解二部图匹配求解二部图匹配 设设G=（S，T；E）是）是二部图，二部图，能够用能够用反反圈算法来解决二部图最大匹配问题：设圈算法来解决二部图最大匹配问题：设M为为当前已有的匹配，当前已有的匹配，(1)初始初始k=0时，令时，令X(0)= | v是关于是关于M的非的非饱和顶点饱和顶点；(2)在在 中选边的原则为中选边的原则为 如果如果 ，则选以，则选以vi为顶点的非饱和边为顶点的非饱和边 如果如果 ，则选以，则选以vi为顶点的饱和边；为顶点的饱和边； (3)在某一步，当出现下面情形之一时停止：在某一步，当出现下面情形之一时停止： 情形情形1：X(k)中有非饱和的中有非饱和的T型点，此时型点，此时有关于有关于M的增广路，则可增广匹配的增广路，则可增广匹配M（重复（重复步骤步骤(2) ）；）； 情形情形2 情形情形1没有出现，但是由没有出现，但是由X(k) 确定确定的反圈中无边可选，此时没有关于的反圈中无边可选，此时没有关于M的增广的增广路，则路，则M是最大匹配。是最大匹配。 定理定理4.1 ：设：设G是一个图，是一个图，M是是G的一个的一个匹配，则匹配，则M是是G的最大匹配当且仅当的最大匹配当且仅当G中不存中不存在关于匹配在关于匹配M的增广路。的增广路。4.3 求解赋权二部图完美匹配：求解赋权二部图完美匹配：匈牙利算法匈牙利算法（或最小费用最大流问题的算法）（或最小费用最大流问题的算法） 4.4 求解一般图匹配：求解一般图匹配：Edmonds算法算法4.5 求解一般赋权图匹配：求解一般赋权图匹配：Edmonds算法算法五、欧拉问题五、欧拉问题5.1 背景背景 德国的哥尼斯堡城有一条普雷格尔河，德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图座桥相互连接，如图5.1所示。所示。 1736年瑞士科学家欧拉发表了关于图论年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。斯堡七座桥问题。AB图图5.15.1CD图图5.2ACDB5.2 欧拉问题欧拉问题 定义定义5.1 给定一个图给定一个图G=（V，E），如果），如果存在一条回路存在一条回路C经过每条边恰好一次，称这经过每条边恰好一次，称这样的图样的图G是欧拉图。回路是欧拉图。回路C被称为欧拉回路。被称为欧拉回路。 问题问题5.1（欧拉问题）对于给定的图（欧拉问题）对于给定的图G=（V，E），判断图），判断图G是否是欧拉图？是否是欧拉图？ 定理定理5.1（欧拉定理）图（欧拉定理）图G是欧拉图当且是欧拉图当且仅当仅当G是连通图，并且是连通图，并且G的每个顶点的度为偶的每个顶点的度为偶数。数。 1921年，年，Fleury提供了一个有效的算法提供了一个有效的算法来寻找图来寻找图G的欧拉回路。的欧拉回路。 以以Pk=v1v2vkvk+1表示第表示第k步得到的路，步得到的路，记记Gk=GE-E(Pk)，如下进行第，如下进行第k+1步：在步：在Gk中选一条边中选一条边ek+1=vk+1vk+2，使得，使得ek+1不是图不是图Gk的的割边（除非割边（除非dGk(vk+1)=1)。令。令Pk+1=v1v2vkvk+1 vk+2 ，及，及Gk+1=GE-E(Pk+1)，直到没有边可，直到没有边可选。选。5.3 一笔画问题一笔画问题 问题问题5.2（一笔画问题）对于给定的图（一笔画问题）对于给定的图G=（V，E），问），问G是否存在一条路是否存在一条路P经过每条经过每条边恰好一次？如果边恰好一次？如果G存在这样的一条路，称存在这样的一条路，称G是可一笔画的。这时，也称图是可一笔画的。这时，也称图G是是M图。图。 定理定理5.2 图图G是可一笔画的当且仅当是可一笔画的当且仅当G是是连通图，并且连通图，并且G中至多存在两个顶点的度为中至多存在两个顶点的度为奇数。奇数。六、中国邮递员问题六、中国邮递员问题6.1 中国邮递员问题中国邮递员问题 1960年，中国的数学家管梅谷教授提出年，中国的数学家管梅谷教授提出如下问题：一个邮递员，每次送信都要走遍如下问题：一个邮递员，每次送信都要走遍他负责的投递范围内的每条街道，完成投递他负责的投递范围内的每条街道，完成投递任务后回到邮局，问他应该按照何路线投递任务后回到邮局，问他应该按照何路线投递信件，使得所走的总路程之和达到最小？信件，使得所走的总路程之和达到最小？ 把这个问题抽象为图的问题，就是对于给把这个问题抽象为图的问题，就是对于给定的连通赋权图定的连通赋权图G =（V，E; w），要寻找），要寻找G的一个闭回路的一个闭回路C，要求，要求C经过每条边至少一次经过每条边至少一次，使得闭回路，使得闭回路C中的边权重之和达到最小。中的边权重之和达到最小。 管梅谷教授在管梅谷教授在1960年给出了一个判定闭年给出了一个判定闭回路回路C是否是最优的一个充分必要条件，但是否是最优的一个充分必要条件，但是没有设计出有效的算法；是没有设计出有效的算法；Edmonds和和Johnson于于1973年给出了一个有效的算法来完年给出了一个有效的算法来完整地解决了中国邮递员问题。整地解决了中国邮递员问题。Edmonds-Johnson算法：算法：(1)在赋权图中找到所有度为奇数的顶点（共在赋权图中找到所有度为奇数的顶点（共有偶数个），如有偶数个），如v1,v2,v2r-1v2r，并且计算这，并且计算这2r个奇数顶点之间的最短路及其长度；个奇数顶点之间的最短路及其长度；(2) 在以这在以这2r个顶点为新的顶点构造完全图个顶点为新的顶点构造完全图H2r，在完全图，在完全图H2r中，顶点中，顶点vi与与vj之间的边权重之间的边权重定义为图定义为图G中中vi与与vj之间的最短路长度。之间的最短路长度。 (3) 在完全图在完全图H2r上寻找权重最小的完美匹配上寻找权重最小的完美匹配M，每条匹配边对应于图，每条匹配边对应于图G中的一条最短路，中的一条最短路，把得到的把得到的r条最短路叠加到赋权图条最短路叠加到赋权图G上，就上，就得到新的赋权图得到新的赋权图G*（这是一个欧拉图）；（这是一个欧拉图）；(4) 对新的赋权图对新的赋权图G*，利用求欧拉回路的算法，利用求欧拉回路的算法(Fleury)能够找到一条欧拉回路能够找到一条欧拉回路C，这条回，这条回路路C 就是图就是图G上的中国邮递员问题的最优解上的中国邮递员问题的最优解（最优路线）。（最优路线）。七、七、NP-NP-完备的组合最优化问题完备的组合最优化问题7.1 哈密尔顿问题哈密尔顿问题(Hamiltonian Problem) 定义定义7.1 设给定一个图设给定一个图G=（V，E），），C是一个圈，如果是一个圈，如果C经过经过G的每个顶点恰好一次的每个顶点恰好一次，则称，则称C是图是图G的哈密尔顿圈，也称图的哈密尔顿圈，也称图G是哈是哈密尔顿图。密尔顿图。 问题问题7.1（哈密尔顿问题）对于给定图（哈密尔顿问题）对于给定图G，问，问G是否含有哈密尔顿圈？即是否含有哈密尔顿圈？即G是否是哈密是否是哈密尔顿图？尔顿图？7.2 货郎担问题货郎担问题(Travelling Salesman Problem) 设给定一个赋权的完全图设给定一个赋权的完全图G=（V，E；w），寻找），寻找G的一条闭回路的一条闭回路C经过所有的顶点经过所有的顶点（该回路（该回路C可以经过某些顶点多次），使得可以经过某些顶点多次），使得闭回路闭回路C上边的权重之和达到最小。上边的权重之和达到最小。 一般地，货郎担问题没有近似值为一般地，货郎担问题没有近似值为f(n)的的近似算法，对于满足三角不等式的完全图近似算法，对于满足三角不等式的完全图G，存在近似值为，存在近似值为2和和3/2的近似算法（树算法的近似算法（树算法与与Christofides算法）。算法）。 7.3 排序问题（排序问题（Scheduling Problem) 给定给定m台功能相同的机器，设有台功能相同的机器，设有n件需要件需要加工的任务，其加工时间分别为加工的任务，其加工时间分别为p1, p2, pn，每件任务要不间断地在某台机器上加工完，每件任务要不间断地在某台机器上加工完成，问：如何安排加工任务的顺序（称为方成，问：如何安排加工任务的顺序（称为方案），使得把全部任务加工完毕所需时间达案），使得把全部任务加工完毕所需时间达到最小。到最小。 存在近似值为存在近似值为2-1/m和和4/3-1/3m的近似算的近似算法。法。 7. 装箱问题（装箱问题（Bin-Packing Problem） 给定给定n个大小分别为个大小分别为a1, a2, an的物品，的物品，把它们放入容量为把它们放入容量为1的多个箱子之中，要求每的多个箱子之中，要求每个箱子中所放数之和不超过该箱子的容量个箱子中所放数之和不超过该箱子的容量1，问：如何安排装箱顺序，使得需要的箱子数问：如何安排装箱顺序，使得需要的箱子数目尽可能少。目尽可能少。该问题不存在近似值为该问题不存在近似值为3/2-k的近似算的近似算法，这里法，这里k是大于的任意正数。存在多个近是大于的任意正数。存在多个近似算法来解决该问题，其近似值为似算法来解决该问题，其近似值为2或或3/2。 7. 背包问题背包问题(Knapsack Problem) 给定一个背包，其容量为，设有给定一个背包，其容量为，设有n件物件物品，每件物品的容量分别为品，每件物品的容量分别为a1, a2, an ，当，当把这些物品放入背包之中，产生的效益分别把这些物品放入背包之中，产生的效益分别为为p1, p2, pn，问：如何安排装物体的顺序，问：如何安排装物体的顺序（称为方案），满足装入背包的物品容量之（称为方案），满足装入背包的物品容量之和不超过容量，使得产生的效益之和达到和不超过容量，使得产生的效益之和达到最大。最大。 存在全多项式近似方案存在全多项式近似方案PTAS(polynomial-time apprximation scheme)。 7. 最小点覆盖问题最小点覆盖问题设给定一个图设给定一个图G=（V，E），寻找的），寻找的一个子集合，使得中每条边的两个顶点一个子集合，使得中每条边的两个顶点至少有一个要属于，称是图的一个点至少有一个要属于，称是图的一个点覆盖。覆盖。最小点覆盖问题最小点覆盖问题: 就是要寻找点覆盖就是要寻找点覆盖，使得，使得|S|达到最小。达到最小。 存在近似值为存在近似值为2的近似算法来解决该问题的近似算法来解决该问题（匹配、（匹配、LP）。）。利用匹配算法，能够解决二部图的最小利用匹配算法，能够解决二部图的最小点覆盖问题。点覆盖问题。7.染色问题染色问题 给定图（，），所谓的一个给定图（，），所谓的一个k点染色是指把划分为点染色是指把划分为k个子集个子集V1,V2,Vk,使得集合使得集合Vi中的点染成颜色中的点染成颜色i，并且集合，并且集合Vi是是独立集。点染色问题就是求这样的最小正整独立集。点染色问题就是求这样的最小正整数数k。 给定图（，），所谓的一个给定图（，），所谓的一个k边染色是指把划分为边染色是指把划分为k个子集个子集1,E2,Ek,使使得集合得集合Ei中的边染成颜色中的边染成颜色i，并且集合，并且集合Ei是匹是匹配。边染色问题就是求这样的最小正整数配。边染色问题就是求这样的最小正整数k。7. 平面图的面染色问题平面图的面染色问题给定平面图（，），所谓的给定平面图（，），所谓的一个一个k面染色是指把的所有面划分为面染色是指把的所有面划分为k个子个子集集F1,F2,Fk,使得集合使得集合Fi中的面染成颜色中的面染成颜色i，任何有公共边的两个面具有不同的颜色。任何有公共边的两个面具有不同的颜色。面染色问题就是求这样的最小正整数面染色问题就是求这样的最小正整数k。 四色猜想四色猜想(定理定理)：任何平面图可以：任何平面图可以-面面染色。染色。(1979) 五色定理：任何平面图可以五色定理：任何平面图可以-面染色。面染色。 (1890)谢谢！谢谢！