| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3419 人关注过本帖
标题:有重酬!求大佬解答最大流、顶点覆盖的算法分析题
只看楼主 加入收藏
faintdong
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2021-3-14
收藏
 问题点数:0 回复次数:0 
有重酬!求大佬解答最大流、顶点覆盖的算法分析题
一.顶点覆盖问题:给定无向图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 必有重谢!
搜索更多相关主题的帖子: 分析 最大 最小 集合 算法 
2021-03-15 00:16
快速回复:有重酬!求大佬解答最大流、顶点覆盖的算法分析题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015162 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved