3回答
关于支配集是NP完全集的证明
np-complete、reduction
以下是问题所在。我想知道是否有明确而有效的证据：支配集:输入无向G，整数k> 0。是否存在控制所有顶点的顶点子集S，|S|<= k？假设VC是NPC，证明DS是NPC。
浏览 11提问于2011-03-15得票数 6
1回答
从最大独立集到支配集的约化证明支配集是NP-完全的
np-complete、proof
我知道从顶点覆盖到支配集的简化。有没有人知道这是不是已经完成了？我在网上找不到任何东西。我希望能找到一些类似这样的证据：和
如果存在大
浏览 6提问于2013-04-14得票数 1
1回答
哪一个是NP-完全问题的两个问题的组合是什么类？
complexity-theory、reduction、np-complete、np-hard
我有一个带有最小化成本函数和两个约束条件的优化问题。在不考虑任何约束的情况下，我可以将优化问题简化为NP完全问题。但在这两个约束下，我没有任何想法将问题简化为已知的NP完全或NP难问题。假设在图中，我想选择满足两种不同条件的最小节点数。这些条件是独立的。例如，其中一个是解决最小支配集问题，另一个是确保选择具有某些结构特征
浏览 27提问于2020-08-26得票数 0
回答已采纳
1回答
证明加权反馈顶点集是NP-完全的
set、vertex、feedback、np-complete、weighted
我需要证明加权反馈顶点集(WFVS)是NP-完全的。我怎么做，我搞糊涂了。我不知道该怎么做。
谢谢！:)
浏览 5提问于2015-01-12得票数 0
1回答
用贪婪算法求最小指数型支配集
python、algorithm、graph-theory、networkx、independent-set
我开发了一个基于距离约束的图的最小独立支配集的算法。(我使用Python和NetworkX生成图形并获取对)
比较发现的独立支配集并找出最小支配集对于少量的节点来说，这并没有什么区别，但是对于大量的</em
浏览 6提问于2016-11-07得票数 1
1回答
最少仓库数
algorithm、graph
给定V个顶点(城镇)和E边(城镇之间的路线)。一家公司决定建造仓库，以确保任何X镇都会有一个仓库，要么位于X，要么位于邻近的X镇。1 22 58 610 7我首先计算每个城市的程度，然后在城市中放置一个最大程度的仓库。然后，我标记所有邻近城市的访问，然后转移到下一
浏览 2提问于2014-06-22得票数 1
回答已采纳
2回答
包含从1到N的所有数的最小多集集
algorithm
接下来，我们将它们分成K-element多集。你如何找到这样的集合，其中包含最小的多集，但这个多集的和包含从1到N的所有数字？在不明确的情况下，答案将是任何符合标准的集合(第一次发现)。例如，我们有N = 9，K = 3包含从1到9的所有数字的最小多集数等于4，可以是(1,2,3)(4,5,6)(7,8,8有什么
浏览 5提问于2015-06-11得票数 1
回答已采纳
1回答
给定一个未加权图，如何找到1的生成树。最大叶数2最小叶数
algorithm、graph、spanning-tree
编写了一种算法来查找具有最大叶子数的生成树。编写了一种算法来找到具有最小节点数的生成树。
我还未能就以下问题提出解决办法。对于第一部分，我想的是找到最高度的顶点，然后把它放在第二层，最后一层得到最大的叶子数。
浏览 3提问于2020-03-20得票数 0
2回答
关于独立集问题的NP-完备性问题
complexity-theory、time-complexity、np-complete
我认为，当证明一个问题P是NP-完全时，我们应该将一个已知的NP问题简化为P。但是，看看独立集问题的解决方案，似乎不是这样的。为了证明独立集是NP-完全的，你可以取一个图G，找到它的逆G'，然后计算团(G‘)。但是，这是另一种方式:它取一个问题，我不知道它是不是NPC，然后把它简化成一个已知的
浏览 2提问于2010-01-25得票数 0
回答已采纳
1回答
使用numpy的Pareto前沿指数
python、numpy
例如，非支配向量集(v0)将被标记为Pareto前沿指数0，非支配向量集(v1 =M-v0)将被标记为索引1，下一组/非支配向量集(v2 =M-v0- v1) 2等等，直到矩阵M的所有向量都被标记为止。[1, 2, 3, 4, 5, 6],])
如果a在x中，b在y中，则向量x支配这是我的尝试：
def cal
浏览 1提问于2017-01-19得票数 4
1回答
寻找所需“中心点”的最小数目
algorithm、graph、cluster-analysis
函数返回两个节点之间的某种距离，这样dist(a，c)可能不是dist(a，b)+dist(b，c)。基于阈值，我通过边缘连接某些节点。我希望选择最小的节点数，这样这些节点的集合及其相邻的边缘连接就构成了整个n个节点的集合。最优的解决方案可能吗？在纸上涂鸦使我认为中心感可以帮助我(程度，亲密？)集群发生在我身上，但是这个图中的节点没有属性。如何选择节点的最小数目？提前感谢
浏览 4提问于2016-04-18得票数 2
回答已采纳
4回答
如何证明一个问题是np完全的并且是np中的？
algorithm、np-complete、np
如果一个部门需要一个委员会来挑选部门的负责人。委员会不能包括有利益冲突的人。这些投入包括：
如何证明这个问题是NP -完全的，并且是NP中的？
浏览 2提问于2015-06-16得票数 0
2回答
NP-完备团+独立集图的证明
algorithm、computer-science、np-complete、clique-problem
“证明它是NP-完全的，以确定给定的输入G和k是否同时有一个大小为k的团和一个独立的大小集。注意，这是一个问题，而不是2；答案是是当且仅当G有这两个子集。”我的算法课上给了我们这个问题，一大群学生找不到答案。到目前为止..。
我们知道，集团问题和独立集问题本身都是NP-完全的.我们也知道，这个问题的验证，给予一些“证书”
浏览 2提问于2010-11-12得票数 12
1回答
零知识证明与零知识证明有什么区别？
zero-knowledge-proofs
在零知识证明中，证明器交互地向验证者证明NP语句是正确的。如果该语言是NP完全语言，如果证明器在多时间内运行，则证明程序可以这样做的唯一方法是当它有一个证人时。因此，当证明者为NP完全陈述提供ZK证明时，证明者证明他知道一个令人满意的证人。
浏览 0提问于2019-04-15得票数 6
回答已采纳
2回答
这是证明某种东西是NP完全的正确理解吗？
algorithm、np-complete、reduction、np
据我所知，要证明一个问题是NP完全的，有两个步骤：
证明问题是NP难-例如，假设你有一个神谕，可以计算另一个已知的NP完全</e
浏览 1提问于2013-12-12得票数 2
回答已采纳
1回答
为什么形式程序证明NP-完备？
algorithm、proof、np-complete
我知道如何证明问题X是NP-完全的。
然而，为什么这个过程证明X是NP-完全的呢？有人能用一种相对简单的方式解释这件事吗？
浏览 0提问于2014-04-05得票数 0
回答已采纳
1回答
检查它是否是一个主要的图集
python、graph-theory
根据定义，图G= (V，E)的支配集是V的子集D，使得不位于D中的每个顶点至少与D的一个成员相邻。我想知道如何检查其中一个可能的组合是否是一
浏览 2提问于2022-10-15得票数 0
2回答
竞赛图的控制集
graph-theory、minimum-spanning-tree、tournament
我正在写一个寻找锦标赛图的支配集的算法。有向图的最小生成树是否等同于图的支配集？换句话说，如果我找到了锦标赛图的最小MST (通过迭代所有的顶点)，那么我能说这等同于图的支配集吗？
浏览 2提问于2008-11-17得票数 0
回答已采纳
云服务器
ICP备案
对象存储
实时音视频
云点播
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号