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

PHPz 转载: 2023-09-19 14:09:02 833浏览

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

让我们理解并检查节点是否具有 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)，但我们不知道哪种搜索技术对解决该问题更有用，这被称为非确定性算法。