课程期末作业：《算法概论》课后8.22题的证明

题目：

证明：
（a） FAS可从通过顶点覆盖的减少证明是NP完全。给出了一个顶点覆盖实例（G，b），其中G是一个无向图，我们想要一个小于等于b顶点覆盖，我们构建了一个实例（G，b）FAS如下：如果G =（V，E）有n个顶点v1，…，vn，然后使G0 =（v0，E0）是一个有向图，包含2n个顶点W1，W’ 1，…，WN，W’ N，和N + 2 | E |（有向）边，（WI，i）所有i = 1,2，…，n（w’i，wj）和（w’j，wj）每（vi，vj）∈E。由于FAS是可以在多项式时间内验证的，所以该问题属于NP问题。
（b）设G中一个大小为t的顶点覆盖为C，对于任意定点vi，vi属于C，设其在G’中相对应的顶点为wi和w’i，那么将边（wi，w’i）添加紧E’中，将C中的顶点进行处理，进行一遍遍历之后就得到了相应的E’，而E’就是要求解的FAC问题的结果，它的大小为t，这是因为对于顶点wi和wi’，当去掉(wi,wi’)之后所有与wi相邻的边都不可能位于任何一个环中，这是因为wi，不存在出的边，同理可得与wi’相邻的边都不可能位于任何一个环中，这是因为wi’，不存在入的边。
（c）对于G中的任意一条边(vi,vj)，设边中顶点在G中对应着wi，wi’，wj，wj’，相对应的就是边(wi,wi’)，(wj,wj’)，(wi’,wj)以及(wj’,wi)，如果E’是G’的一个大小为t的FAS，那么这四条变中至少有一个是属于E’的否则就会形成环，那么边e一定有一个端点是属于{wi,wj}，如果wi是e的端点，那么将vi，加入到C中，否则将vj加入到C中，那么C就是G的与一个 大小最大为t的顶点覆盖。