近似算法讲义.ppt

连通的无向图G有欧拉路径的充要条件是：G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2， 奇数点是起点和终点。 连通的无向图G是欧拉环（存在欧拉回路）的充要条件是：G中每个顶点的度都是偶数 Claim:若G无HC，则因为H是完全图，存在HC。H的最小HC至少有一条边不是E的，其长为kn =上有三角 NPC原来主要是应用到语言或判定问题问题上，但将最优解的值和输入实例一起作为输入，则可将其转换为判定问题： NPC原来主要是应用到语言或判定问题问题上，但将最优解的值和输入实例一起作为输入，则可将其转换为判定问题： K也是算法A的绝对误差。 平面图是可以画在平面上并且使得不同的边可以互不交叠的图。 二部图（二分图）就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集 该问题来源于地图着色，19世纪50年代英国提出了4色猜想：任何地图都可以4着色，100多年以后美国学者在计算机上予以证明。 注意：对于有的图，4色不一定是最优的，若图不是偶图，至少应该是3色的。 正则图是每个顶点都有相同数目的邻居的图，即每个顶点的度相同。若每个顶点的度均为 ，称为 -正则图。 如何证明一个问题的绝对近似算法是不存在的？否定结果可避免做无用功！ 注意：我们均默认近似算法是多项式时间的 如何证明一个问题的绝对近似算法是不存在的？ 注意：f(σ)和OPT(I)等均为表示利润的整数, f(σ)= OPT(I) 意味着近似算法A找到了最优解，也就是背包问题多项式时间可解。 这里的例子说明在纯组合问题上，依然可用扩放性质 顶点集C被称为无向图 G=(V,E) 的团，如果C是顶点集V的子集(C?V)，而且任意两个C中的顶点都有边连接。另一种等价的说法是，由C诱导的子图是完全图 （有时也用“团”来指这样的子图）。 极大团是指增加任一顶点都不再符合团定义的团，也就是说，极大团不能被任何一个更大的团所包含。 最大团是一个图中顶点数最多的团。图G的团数（clique number）ω(G) 是指G中最大团的顶点数。图G的边团覆盖数（edge clique cover number）是指覆盖G中所有的边所需要的最少的团的数目。图G的二分维数（bipartite dimension）是指覆盖G中所有边所需要的最少的二分团的数目，其中二分团（biclique）就是完全二分子图 。而分团覆盖问题 （Clique cover problem）所关心的是用最少的团去覆盖G中所有的顶点。 独立集（independent set）是刚好和团相反的概念，因为图G中的团和图G的补图中的独立集是一一对应的。 Claim直接给出了最优解之间的scaling性质：OPT(GK+1)=(k+1)OPT(G) A(GK+1)= β， A(G)= β/(k+1)=|C|, A(GK+1)= β=(k+1)|C| 若RA(I) ≤（1+?），则称A是(1+?)－近似算法，1-近似算法产生最优解 注意：绝对性能比与具体实例I无关，故表达比时无须用I RA=inf{r≥1:对于所有的实例I，RA(I) ≤r} RLPT是绝对性能比。即A(I)/OPT(I) ≤4/3-1/3m 证明留为作业 渐近性能比=inf{r≥1：存在n?Z+，对所有满足OPT(I) ≥n的实例I，RA(I) ≤r} 亦可定义为：渐近性能比=inf{r≥1：存在n?Z+，对所有满足I≥n的实例I，RA(I) ≤r} RFFD为3/2：1/2,1/3,/1/3,1/3,1/4,1/4 连通的无向图G有欧拉路径的充要条件是：G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2， 奇数点是起点和终点。 连通的无向图G是欧拉环（存在欧拉回路）的充要条件是：G中每个顶点的度都是偶数 因为某顶点可能通过多次，故欧拉环的顶点序列长度n。而哈密尔顿圈的顶点序列长度为n，因此，可以通过去掉重复顶点的方式得到哈密尔顿圈。因为去掉的边长度=0,所以HC的长度小于其ET的长度，这点由三角不等式保证。 连通的无向图G有欧拉路径的充要条件是：G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2， 奇数点是起点和终点。 连通的无向图G是欧拉环（存在欧拉回路）的充要条件是：G中每个顶点的度都是偶数 连通的无向图G有欧拉路径的充要条件是：G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2， 奇数点是起点和终点。 连通的无向图G是欧拉环（存在欧拉回路）的充要条件是：G中每个顶点的度都是偶数 * § 1.3.3 旅行商问题（TSP） ∵图T∪M中所有顶点度为偶数，∴可从其构造欧拉环ET d(ET) = d(T∪M) ≤ 1.5OPT(G) 用短路法从ET构造HC