NPC

（1） 背包问题：问题可以描述为，给定一组物品，每种物品都有自己的重量和价格，在

限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

（2） 哈密顿圈问题(Hamilton circuit problem)：图论中著名的难题之一设有一个图，若其

上存在一个圈，这个圈包含该图上的每一节点，则称该圈为哈密顿圈，这个图称为哈密顿图.哈密顿圈问题可叙述为:什么样的图为哈密顿图，或者说判断一个图是哈密顿图的行之有效的充分必要条件是什么.

（3） 旅行商问题，即TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、

货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

（4） 图着色问题：给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着

色问题即为将V分为K个颜色组，每个组形成一个集，即其中没有相邻的顶点。其优化版本是希望获得最小的K值。

（5） 分团问题(clique problem)：一个大小为3的clique，clique是一个图中两两相邻的

一个点集，或是一个完全子图(complete subgraph)，clique problem是问一个图中是否有大小是k以上的clique。任意挑出k个点，我们可以简单的判断出这k个点是不是一个clique。

（6） 顶点覆盖问题：给定一个N个点M条边的无向图G（点的编号从1至N），问是否

存在一个不超过K个点的集合S，使得G中的每条边都至少有一个点在集合S中。

2. 解：