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 问题