《算法分析第二次作业答案.docx》由会员分享，可在线阅读，更多相关《算法分析第二次作业答案.docx（3页珍藏版）》请在三一办公上搜索。
1、算法分析第二次作业答案算法第二次作业答案 这里我们归约要做的主要步骤就是， 1.把NPC的input转化到NP-hard的input，即每一个NPC的input，实际上都是一个NP-hard的input。 2.把NP-hard的output转化到NPC的output上来，说明给我一个NP-hard的output，我就能给你一个NPC的output。 注意：以上的两个转化都要在polynomial的时间内完成。 第1题： 证明如下： 给定图G1和图G2中的一个子图G3，显然能在多项式时间内验证G1和G3是否同构，故subgraph-isomorphism问题是NP问题。 已知clique问题是N
2、P完全，现给出一个算法使clique问题变换成subgraph-isomorphism问题。算法如下： a) 令图H为团问题中K个顶点组成的完全图 b) 令图G1为图H的同构图 则由上述算法可知图G有一个规模为k的clique当且仅当在图G中存在与G1同构的子图H。因上述算法是多项式时间的，所以clique问题可以规约成subgraph-isomorphism问题。 综合知subgraph-isomorphism问题为NP完全问题。 第2题： 例 用3SAT证明ILP是NP-hard的。即 3SAT =1”，很显然了，ILP中的变量选0对应于3SAT中的变量选false，ILP中的变量选1对应
3、于3SAT中的变量选true，这样我们就映射好了。 很显然，这两个问题的input/output的转换trival的不行了。如果一个clause满足了，对应的那个ILP中的constraint肯定也满足了；反之依然。偷个懒O(_)O 证毕。 最后将所有约束条件写成矩阵形式AX=b,则将3SAT归约为了ILP 第3题： 给定set-partition问题S的一个解A，可以在多项式时间内验证xAx=y是否成立，所以set-partition问题为yBNP问题。 已知subset-sum问题为NP完全问题，现定义一个算法使subset-sum问题变换成set-partition问题。算法如下： 已知
4、整数集合S和整数t，给出r=2t-x xS定义整数集合S，使得S=SUr 返回S 上述变换后可知S中有一个子集和为t的子集当且仅当集合S能set-partition。又因上述转换算法是多项式时间的，因此subset-sum问题可以规约成set-partition问题。 综合可知set-partition问题为NP完全问题。 第4题： 第6题： 证明： 对于给定的n/2个顶点集V,对每一对顶点u,vV，通过检查边是否属于E，就可以在多项式时间O(n2)内完成对V是否是团的验证，则证明Half-Clique是NP问题。 已知Clique问题为NPC问题，对一个Clique问题，通过以下算法构造G： 1) 在G上添加n个顶点，并在这n个顶点中选取n-k个顶点，进行两两互联 2) 将这n-k个顶点同G中的每一个顶点连接起来。 3) 返回一个2n个顶点的图G 变换后显然有G中有一个K个顶点组成的团当且仅当G中有由n个顶点组成的团。显然转换算法可以在多项式时间内完成，故有 综上可知，Half-Clique问题为NPC问题。
