有重酬!求大佬解答最大流、顶点覆盖的算法分析题
一.顶点覆盖问题:给定无向图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 必有重谢!