首页 > 代码库 > NP 问题

NP 问题

                                            NP问题

一、什么是NP问题?

      在搞清楚NP之前,必须弄清楚P问题,P问题就是在多项式时间内可解的问题。假设问题的输入规模为n,它的解运行需要的时间不会

超过它的关于n的多项式时间。那么NP就是,虽然在多项式时间内不能解决,但是能够在多项式时间内验证一个解。所以,很自然人们就想

NP和P到底相不相等,现在这个是个OPEN问题。

 

二.解决NP问题,用到的一些概念

   1.超图

技术分享

 

关于超图有个非常形象的解释,对于一个普通无向图来说,顶点代表文章,边代表作者,那么我们无法从这个图中知道一个作者到底写了哪些

文章,于是超图就解决了这个问题。这里的边是闭合的;从图中看到e1,e2,e3,e4;用点的集合表示边。Hypergraph表示方法H(X,E)

X = {v1,v2,v3,v4,v5,v6,v7}, E ={e1,e2,e3,e4}={{v1,v2,v3},{v2,v3},{v3,v5,v6},{v4}};

 

2.独立集

简单来说,就是在一个图中,任何两点不存在一条边。举个简单例子,一个简单无向图G,点表示一个个体,边表示两个人之间存在矛盾。如果你想找出

一堆人去参加一个party,那么肯定不能找两个死对头一起去,当然除非你想惹事。那么你找到的所有没有矛盾的人的集合就是独立集。

 

3.匹配

匹配,简单来说,就是一个图中没有一条边和另一条边公用一个顶点。如果你懂得了独立集你就会发现,其实匹配就是边独立集。另外,

匹配和独立集刚好构成完整的图。

 

4.弦

连接环中不相邻的两个顶点的边。

 

5.弦图

一个无向图称为弦图,当图中任意长度大于3的环都至少有一个弦。

 

6.诱导子图

所谓诱导子图,和普通子图的区别就是,点事原图的子集,同时,原图中子图的顶点构成的边也必须都有。相当于把原图一个部分全部挖出来。

普通的子图,可能在挖图的时候,漏掉一些边。还有生成子图,保留原图的所有顶点,但是没有保留所有边。

 

7.团(clique)

  也称为完全生成子图。就是一个无向图的子图,该子图中任意两个顶点之间存在一条边。那么极大团就是不能被更大的团包含,

简单来说就是再也找不到一条边和这个团的任意

顶点构成边。

 

8.支配集

  所谓支配集,就是指能够支配的范围,集合内的顶点是自己的,当然可以支配,邻居的顶点也可以支配。所以,它的定义

是:图顶点集的子集,设S是图G的支配集,对于图中的

任意一个顶点,要么属于集合S,要么与S中的顶点相邻。如果在S中去掉任何一个元素,S不再是支配集,那么S就是极小支配集。

 

9.反馈集

  所谓反馈集,就是破换团结的一些间谍。如果一个图有环,表示这些人是一个集体很团结。那么反馈集就是间谍。反馈集的定义

是:删除一个图的顶点Vi,使得其变成没有环的树,Vi构成的集合称为反馈集。

 

NP 问题