精选优质文档-倾情为你奉上算法设计练习题一. 计算复杂性1 P184 10.3 设计一个多项式时间的算法判断一个无向图G是否是2可着色的算法：2-COLORING输入：无向图G(V, E)输出：该图是2可着色的，则输出yes；否则，输出no.1. 取任一节点，标记为白色2. 所有与它邻接的节点标记为黑色3. 对任意已标记的节点v，将所有与v邻接且未标记的节点标记为与v相反的颜色4. 重复步骤3，直到不存在与已标记节点邻接且还未标记的节点5. 如果图中还有未标记的节点，那么这些节点一定在一个新的连通分量中，再选 择其中一个节点标记为白色，转到步骤36. 如果得到的图中，所有邻接的节点都标记为不同的颜色，则输出yes；否则，输出no.End 2-COLORING 时间复杂度分析：在n个顶点和m条边的图上进行分析，算法的运行时间是2 P185-186 10.16 团集问题的NP完全性是由可满足性问题归约到它证明的，给出一个从顶点覆盖到团集的较简单的归约法1：规约方法：设G=（V，E）是连通无向图，S
