1回答
DAG中的最小路径覆盖
、、、
我想知道是否存在一个有效的算法来计算有向无环图的最小路径覆盖。请不要将最小“路径覆盖”与“顶点不相交的路径覆盖”混淆。对于后者，我知道一个有效的算法，使用相应的二部图的最大匹配。但这只适用于顶点不相交的情况。当每个顶点可以被多次访问时，是否可以放松相同的算法以获得路径覆盖的答案？
浏览 4提问于2013-06-10得票数 3
回答已采纳
1回答
给定一个无向边的树，其中一个顶点的权重是它的度，则求最小权的顶点覆盖。以下是我的想法：
由于顶点覆盖需要包含足够多的顶点来覆盖所有边，这意味着无论覆盖中的顶点是什么，所有顶点的权重之和都是相同的(等于边的数目)。因此，我们不需要任何特殊的算法来寻找答案，我们只需要找到最小大小的顶点覆盖(覆盖最小</em
浏览 3提问于2011-08-15得票数 4
最小加权顶点覆盖问题的一个著名的2-近似是由Clarkson提出的：
放大图片创作者:J.“对用于顶点覆盖的贪心算法的修改。”资讯处理通讯16.1 (1983)：23-25。简单易读的算法伪代码可以在中找到，见32.1.2节。根据这篇论文，该算法的运行时复杂度为O(|E|*log|V|)，其中E是边的集合，V是顶点的集合。我不完全确定他们是如何得到这个结果的。设d(v)是图中顶点v的度，w(v)是某一权函数。排除<e
浏览 17提问于2016-07-30得票数 0
回答已采纳
1回答
通过查看图表，我知道最小顶点覆盖是{v1，v2，u3}和{v1，u2，u3}，但我不确定如何使用二部匹配/顶点覆盖算法来找出这一点。和但是在这种情况下，所有的顶点都是饱和的，所以我不知道如何继续。
浏览 1提问于2014-04-28得票数 0
2回答
我似乎找到了一种算法，但我在理解它时遇到了困难，我想知道你们中是否有人知道算法的一般轮廓。
这是我在第2页找到的算法的链接
浏览 1提问于2012-09-17得票数 2
树的顶点覆盖问题如下。输出：一组顶点W，使得对于每一个边uv，u∈W或v∈W，我们想要最小化W的大小。这个算法适用于我迄今尝试过的所有情况。我该如何证明它是正确的呢？通过矛盾，我想证明S不覆盖</em
浏览 8提问于2014-10-09得票数 0
回答已采纳
2回答
在座的任何人都知道是否有可能在O(n^2)中以最小化删除顶点的方式消除无向无权图(n顶点)中的所有圈？如果可能，我该怎么做呢？如果不是，为什么？
谢谢
浏览 0提问于2018-04-14得票数 0
3回答
一个crab是一个无向图，它有两种顶点:1个头和K个脚，以及恰好K条连接头和每条腿的边。(1 <= K <= T，其中T是给定的)例如。输入1 43 45 85 6
浏览 3提问于2013-06-05得票数 6
回答已采纳
1回答
我想我正在寻找一种算法，它可以在二分图中找到“最小”的“选择”。每个顶点有一个相关的(整数)成本来选择它。我只能找到将所选集合中的顶点数目最小化的算法，而不是代价。我以前以为我需要一个“匹配”，但实际上我只需要覆盖每个边的顶点子集.顶点1, 2 ,3在A中，有1。顶点4在B中，有2。解决方案是删除最昂贵的顶点，4.基于成本选择的贪婪解决方案将
浏览 0提问于2013-04-06得票数 1
回答已采纳
1回答
寻找最短周期
、、
基本上，我需要在一个图中有一个覆盖所有顶点并返回到源的最短路径。只要是最短路径，任何顶点的重复都是可以的。
我的算法从源开始。我运行dijkstra算法来找到最短路径。然后我选择最小的加权未达顶点，并再次运行dijkstra作为所选顶点作为源，并继续运行，直到所有顶点都完成。然后，从最后一个顶点再次使用dijkstra找到返回原始源的最短路径。
浏览 0提问于2012-10-30得票数 0
4回答
完全断开二部图的连接
、、、、
任务是最小化要删除的节点数量。图中的每个节点最多有4条边。
通过完全断开一个图，我的意思是不应该通过链接连接两个节点。基本上是一个空的边集。
浏览 1提问于2012-08-07得票数 4
回答已采纳
1回答
我有下面的算法来寻找树的最小顶点覆盖。这是一个极小的顶点集，使得对于G中的每一个边(v，u)，要么v在S，要么u在S中。我被告知算法具有线性时间复杂度，但是我不明白为什么是这样的，因为不是O(n)阶到u的边数，所以复杂度是O(n^2)吗？while V !
浏览 1提问于2022-04-02得票数 2
1回答
要找到无向图G的最小支配集，可以使用如下贪心算法:从一个空集D开始，直到D是一个支配集，添加一个具有最大未覆盖邻居数的顶点v。该算法一般不会找到最优解，它是一个ln(增量)-approximation。(如果增量是G中顶点的最大次数)有人知道一个小例子吗？
提前感谢
浏览 6提问于2012-06-04得票数 4
回答已采纳
1回答
我找到了一些算法来寻找最小顶点覆盖，比如使用二叉树，但我读到使用三叉树更好。但我找不到任何关于它的信息，也想不到它的算法。 有人知道怎么做吗？
浏览 11提问于2020-11-02得票数 2
回答已采纳
2回答
我正在为一次考试而学习，其中一个样题如下：
顶点覆盖:图中的顶点覆盖是一组顶点，使得每条边在该集合中至少有两个端点之一。最小顶点覆盖:图中的最小顶点覆盖是指在所有可能的顶点覆盖中具有最少顶点数量的顶点覆盖。最小顶点覆盖图中的最小顶点
浏览 0提问于2010-06-15得票数 12
1回答
最小顶点覆盖的验证算法？
、、、
我们知道，最小顶点覆盖是NP完全的，这意味着它在一组可以在多项式时间内验证的问题中。
我发现很难确定第二步可以在多项式时间内完成。有人能解释一下吗？
浏览 1提问于2013-04-18得票数 5
回答已采纳
1回答
所以，我有一个顶点图，它有一定的权重和边。我在试着找最小加权顶点覆盖。例如，如果我有一个大小为10的顶点覆盖，但每个节点的权重为10，则总覆盖的权重为100。但是如果我有一个大小为99的顶点覆盖，每个节点的权重为1，那么我会选择这个覆盖而不是前一个。我认为这是NP完全的，所以没有有效的算法，但我认为即使是详尽的搜索对我来说也是可行的，因为节点的数量将相对较少。我想要做到这一点的唯一方法是生成集合的幂
浏览 2提问于2012-08-21得票数 2
回答已采纳
下面提到的是一个算法.我想出了..。其中，X返回顶点cover.Is所需的最小顶点集，对吗？谢谢
浏览 3提问于2014-11-18得票数 2
回答已采纳
在图论中，我们使用匈牙利算法计算加权二部图的最小边覆盖(一组与每个顶点相关的边，即具有最小总权重的边)。
我发现在数学的新版本8中，有一个全新的图论函数包(从Graph[]开始)。我确实找到了一个名为FindEdgeCover[]的函数，它只能找到一个边缘覆盖，而不是最小的一个。
浏览 1提问于2011-09-11得票数 8
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
