证明图的主导集是NP-完全的

图的一个主导集是NP完全问题，它是顶点的子集，使得子集中的每个顶点或相邻的顶点都在子集中。NP的完整形式是“非确定性多项式”，它将在多项式时间内检查问题，这意味着我们可以在多项式时间内检查解决方案是否正确。多项式时间对于像线性搜索的时间复杂度 – n， 二分搜索 – logn， 归并排序- n(log)n 等代码具有最好的复杂性。NP完全图在合理的时间内提供了一个很好的解决方案。这个应用程序在网络控制、计算机实验室中的拓扑创建、社交网络和分布式计算等领域中使用。

让我们理解并检查节点是否具有 NP 完全图的主导集。

据说一个顶点支配它自己和它的每个邻居。

我们看到有两个图显示了图中节点的灰色在自然界中占主导地位。

G = V, E

参数

G 被视为图，V 被视为顶点，E 被视为边。

给定一个图G(V, E)和一个整数k，确定图是否有一个大小为k的支配集。被指定为问题的输入被认为是问题的一个实例。图G(V, E)和整数k作为支配集问题的示例，该问题询问图G是否可以有一个在G中的支配集。由于NP-完全问题的定义是同时属于NP和NP-难的问题，所以证明一个问题是NP-完全的有两个组成部分−

支配集在NP完全问题中

如果存在一个 NP 问题 Y 在多项式时间内可简化为 X，则 X 是 NP 完全问题。 NP 完全问题与 NP 问题一样困难。如果一个问题同时是 NP 问题和 NP-Hard 问题的一部分，那么它就是 NP-Complete。在多项式时间内，非确定性图灵机可以解决 NP 完全问题。当一个问题是 np 完全问题时，它同时具有 np 和 np 硬组合。

这意味着具有np解的问题可以在多项式时间内进行验证。

NP完全的真实例子具有支配集，例如 -

• 决策问题。

• 图形一致。

非确定性搜索算法

NP_search( key ) {
   arraylist[100];
   i = array_check(key);
   if(list[i]==key) {
      searching found at index i.
   } else {
      searching found at index i.
   }
}

因此，该算法的总时间复杂度为 O(1)，但我们不知道哪种搜索技术对解决该问题更有用，这被称为非确定性算法。

支配集在NP难问题中

如果存在一个可在多项式时间内归约到问题X的NP-完全问题Y，那么问题X是NP-困难的。NP-困难问题与NP-完全问题一样难。一个NP-困难问题不一定属于NP类。

如果每个 NP 问题都可以在多项式时间内解决，则称其为 NP-Hard。很多时候，一个特定的问题是用来解决和减少其他问题的。

NP-hard 的真实例子具有支配集，例如 -

• 哈密顿回路

• 优化问题

• 最短路线

结论

我们学习了图的主导集是 NP 完全的概念。我们看到离散数学如何成为连接这些问题的重要方面，例如哈密尔顿循环、最短路径等。在编程方面，NP 完全问题是一类很难找到但可以直接验证解决方案的问题多项式时间。

以上是证明图的主导集是NP-完全的的详细内容。更多信息请关注PHP中文网其他相关文章！