问题、模型与求解算法云南大学数学系李建平二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为回路；如果v0 vk，称该路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的最小支撑树T Begin 在图中寻找一个圈。若不存在圈，则已 经得到最小支撑树或说明该图不连通，后者 不存在支撑树（当然没有最小支撑树）； 若存在圈，去掉该圈中权数最大的边； 反复重复、两步，直到找到最小支 撑树或说明该图不连通（故没有最小支撑树 ）。 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 背景在生活中经常会遇到这样的问题，如