一．顶点覆盖问题：给定无向图G=(V，E)，G的顶点覆盖为顶点集合V 的一个子集U，满足E 中每一条边至少与U中的一个顶点相连。最小顶点覆盖是具有
最少顶点数量的一个覆盖。（20分）
1. 解释P 问题，NP 完全问题，算法近似度。（6 分）
2. 判定图G 是否存在规模为k 的顶点覆盖集合， 属于P 问题还是NP 完全问题？（2 分）
3. 考虑解决顶点覆盖问题的贪心策略：每次从未被覆盖的顶点中选择一个顶点，使得它所覆盖的未被覆盖的顶点数目最多。这种法总能产生一个最优
解吗？如果能，请证明；如果不能，请举出反例。（6分）
4. 用伪代码给出一个顶点覆盖集合的近似算法，并分析其近似度。（6分）
给定有向图G如下所示，起点为s，终点为t。（10分）
1. 计算(s,t)间的最大流，最小割（4分）
2. 将满足(s,t)间最大流的路径以及路径上流的权重一一列出（3分）
3. 写出s，t之间的一个最小割（3分）
如果有人能解答，请+V faintDong 必有重谢！