说明问题 vertex cover problem 给定一个G(V,E)和整数k 是否存在一个G上点的子集合S,对G的每个edge至少会有一点属於S,使S的点数<=k? independent set problem 给定一个G(V,E)和整数k 是否存在一个G上点的子集合S,对G的每个edge至多会有一点属於S,使S的点数<=k? "vertex cover" can be reduced to "max independent set". 1.转换的演算法 给vertex cover的input为G(V,E)和整数k 则给independent set的input为G(V,E)和整数V-k 若independent set output是yes则vertex cover的 output为yes 反之亦然 2.转换的演算法在多项式时间之内 input转换演算法只需要O(1) output转换演算法只需要O(1) 3.转换的方法是对的 令S是任何的independent set 则对G的每个edge(u,v)而言,最多会有一点属於S, 所以对G的每个edge(u,v)而言,最少会有一点属於V-S 所以V-S是vertex cover "independent set" can be reduced to "vertex cover". 1.转换的演算法 给independent set的input为G(V,E)和整数k 则给vertex cover的input为G(V,E)和整数V-k 若vertex cover output是yes则independent set的 output为yes 反之亦然 2.转换的演算法在多项式时间之内 input转换演算法只需要O(1) output转换演算法只需要O(1) 3.转换的方法是对的 令S是任何的vertex cover 则对G的每个edge(u,v)而言,最少会有一点属於S 所以对G的每个edge(u,v)而言,最多会有一点属於V-S, 所以V-S是independent set --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.7.59 ※ 编辑: ajnightmare 来自: 140.112.7.59 (05/24 14:56) ※ 编辑: ajnightmare 来自: 58.114.208.7 (06/18 22:26)