作业帮图论中生成子图问题!有一带权无向图,如何删边或选边,使其所有生成子图的所有边的权值加起来最小
来源：学生作业帮 编辑：作业帮 分类：语文作业 时间：2024/05/11 17:35:55
图论中生成子图问题!
有一带权无向图,如何删边或选边,使其所有生成子图的所有边的权值加起来最小
有一带权无向图,如何删边或选边,使其所有生成子图的所有边的权值加起来最小
你的问题描述很不清楚
（1）既然要删边,肯定有限制,不然干脆全删了不就得了.
（2）如果我理解没有错误,所谓所有的生成子图,是指删边后得到的图的所有生成子图,是这意思吗?
再问： 第二点正确， 就是有一个带权无向图，如何删边，使其得到的生成子图的所有边的权值加起来最小。 这里的所有的生成子图，是指删边后得到的图的所有生成子图。
再答： 你还是没说怎么删，是删一条还是怎么样，有限制吗？
再问： 随便删，但是必须保证每个点都有边相连
再答： 首先不管你怎么删，生成子图包含的节点都是一样的，即随便一个点集，其生成子图的权值和在删边之前和之后，不会有区别（除非要删的边包括在这个生成子图内）。 先考虑简单的情况（暂时不考虑每个点有边相连的限制），如果只允许删一条边，毫无疑问应该去删权值最大的边。 如果删k个边，显然是删权值前k大的边。 考虑每个点有边相连的限制，问题转化为：删除一些边，使得这些边的权值和尽量大，同时满足每个点有边相连。 该问题等价于：选择一些边留下，使得这些边的权值和尽量小，同时满足每个点有边相连。 问题转化为一个带权的最小集合覆盖问题（只要将每条边看做具有两个元素的集合，集合的权值设为边的权值），即找到一些集合，使得集合的权值和尽量小，同时满足集合的并集等于节点全集。 接着你去找带权的最小集合覆盖问题都有什么算法就行了
再问： 可以加我Q吗？想在日后多多指教！953963082
（1）既然要删边,肯定有限制,不然干脆全删了不就得了.
（2）如果我理解没有错误,所谓所有的生成子图,是指删边后得到的图的所有生成子图,是这意思吗?
再问： 第二点正确， 就是有一个带权无向图，如何删边，使其得到的生成子图的所有边的权值加起来最小。 这里的所有的生成子图，是指删边后得到的图的所有生成子图。
再答： 你还是没说怎么删，是删一条还是怎么样，有限制吗？
再问： 随便删，但是必须保证每个点都有边相连
再答： 首先不管你怎么删，生成子图包含的节点都是一样的，即随便一个点集，其生成子图的权值和在删边之前和之后，不会有区别（除非要删的边包括在这个生成子图内）。 先考虑简单的情况（暂时不考虑每个点有边相连的限制），如果只允许删一条边，毫无疑问应该去删权值最大的边。 如果删k个边，显然是删权值前k大的边。 考虑每个点有边相连的限制，问题转化为：删除一些边，使得这些边的权值和尽量大，同时满足每个点有边相连。 该问题等价于：选择一些边留下，使得这些边的权值和尽量小，同时满足每个点有边相连。 问题转化为一个带权的最小集合覆盖问题（只要将每条边看做具有两个元素的集合，集合的权值设为边的权值），即找到一些集合，使得集合的权值和尽量小，同时满足集合的并集等于节点全集。 接着你去找带权的最小集合覆盖问题都有什么算法就行了
再问： 可以加我Q吗？想在日后多多指教！953963082