《第十二章 np完全问题》由会员分享,可在线阅读,更多相关《第十二章 np完全问题(53页珍藏版)》请在金锄头文库上搜索。
1、第十二章 NP完全问题,12.1 P类和NP类问题 12.2 NP完全问题 12.3 co_NP类和NPI类问题,12.1 P类和NP类问题,12.1.1 P类问题 12.1.2 NP类问题,12.1.1 P类问题,12.1.1 P类问题,12.1.1 P类问题,12.1.1 P类问题,12.1.1 P类问题,12.1.1 P类问题,12.1.2 NP类问题,12.1.2 NP类问题,12.1.2 NP类问题,12.1.2 NP类问题,12.1.2 NP类问题,12.1.2 NP类问题,12.2 NP完全问题,12.2.1 NP完全问题的定义 12.2.2 几个典型的NP完全问题 12.2.3
2、 其他的NP完全问题,12.2.1 NP完全问题的定义,12.2.1 NP完全问题的定义,12.2.2 几个典型的NP完全问题,12.2.2.1 可满足性问题(SATISFIABILITY) 12.2.2.2 三元可满足性问题(3_SATISFIABILITY) 12.2.2.3 图的着色问题(COLORING) 12.2.2.4 集团问题(CLIQUE) 12.2.2.5 顶点覆盖问题(VERTEX COVER),12.2.2.1 可满足性问题(SATISFIABILITY),12.2.2.1 可满足性问题(SATISFIABILITY),12.2.2.1 可满足性问题(SATISFIABI
3、LITY),12.2.2.2 三元可满足性问题(3_SATISFIABILITY),12.2.2.2 三元可满足性问题(3_SATISFIABILITY),12.2.2.2 三元可满足性问题(3_SATISFIABILITY),12.2.2.2 三元可满足性问题(3_SATISFIABILITY),12.2.2.2 三元可满足性问题(3_SATISFIABILITY),12.2.2.3 图的着色问题(COLORING),12.2.2.3 图的着色问题(COLORING),12.2.2.3 图的着色问题(COLORING),12.2.2.3 图的着色问题(COLORING),12.2.2.3 图
4、的着色问题(COLORING),12.2.2.3 图的着色问题(COLORING),12.2.2.4 集团问题(CLIQUE),12.2.2.4 团问题(CLIQUE),12.2.2.4 集团问题(CLIQUE),12.2.2.4 集团问题(CLIQUE),12.2.2.4 集团问题(CLIQUE),12.2.2.5 顶点覆盖问题(VERTEX COVER),12.2.2.5 顶点覆盖问题(VERTEX COVER),12.2.2.5 顶点覆盖问题(VERTEX COVER),12.2.2.5 顶点覆盖问题(VERTEX COVER),12.2.2.5 顶点覆盖问题(VERTEX COVER),12.2.3 其他的NP完全问题,12.2.3 其他的NP完全问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,12.3 co_NP类和NPI类问题,