第十二章NP完全问题ppt课件

.,1,第十二章NP完全问题,12.1P类和NP类问题12.2NP完全问题12.3co_NP类和NPI类问题,.,2,12.1P类和NP类问题,12.1.1P类问题12.1.2NP类问题,.,3,12.1.1P类问题,.,4,12.1.1P类问题,.,5,12.1.1P类问题,.,6,12.1.1P类问题,.,7,12.1.1P类问题,.,8,12.1.1P类问题,.,9,12.1.2NP类问题,.,10,12.1.2NP类问题,.,11,12.1.2NP类问题,.,12,12.1.2NP类问题,.,13,12.1.2NP类问题,.,14,12.1.2NP类问题,.,15,12.2NP完全问题,12.2.1NP完全问题的定义12.2.2几个典型的NP完全问题12.2.3其他的NP完全问题,.,16,12.2.1NP完全问题的定义,.,17,12.2.1NP完全问题的定义,.,18,.,19,.,20,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顶点覆盖问题（VERTEXCOVER）,.,21,12.2.2.1可满足性问题（SATISFIABILITY）,.,22,12.2.2.1可满足性问题（SATISFIABILITY）,.,23,12.2.2.1可满足性问题（SATISFIABILITY）,.,24,12.2.2.2三元可满足性问题（3_SATISFIABILITY）,.,25,12.2.2.2三元可满足性问题（3_SATISFIABILITY）,.,26,12.2.2.2三元可满足性问题（3_SATISFIABILITY）,.,27,12.2.2.2三元可满足性问题（3_SATISFIABILITY）,.,28,12.2.2.2三元可满足性问题（3_SATISFIABILITY）,.,29,12.2.2.3图的着色问题（COLORING）,.,30,12.2.2.3图的着色问题（COLORING）,.,31,12.2.2.3图的着色问题（COLORING）,.,32,12.2.2.3图的着色问题（COLORING）,.,33,12.2.2.3图的着色问题（COLORING）,.,34,12.2.2.3图的着色问题（COLORING）,.,35,12.2.2.4集团问题（CLIQUE）,.,36,12.2.2.4团问题（CLIQUE）,.,37,12.2.2.4集团问题（CLIQUE）,.,38,12.2.2.4集团问题（CLIQUE）,.,39,12.2.2.4集团问题（CLIQUE）,.,40,12.2.2.5顶点覆盖问题（VERTEXCOVER）,.,41,12.2.2.5顶点覆盖问题（VERTEXCOVER）,.,42,12.2.2.5顶点覆盖问题（VERTEXCOVER）,.,43,12.2.2.5顶点覆盖问题（VERTEXCOVER）,.,44,12.2.2.5顶点覆盖问题（VERTEXCOVER）,.,45,12.2.3其他的NP完全问题,.,46,12.2.3其他的NP完全问题,.,47,12.3co_NP类和NPI类问题,.,48,12.3co_NP类和NPI类问题,.,49,12.3co_NP类和NPI类问题,.,50,12.3co_NP类