使得F’是T的一个覆盖:F'F,∪S=∪S=T并且 F=最小;其中符号表示基数。M 定理33最优覆盖问题(MCV)是NP难题。 设T={12…,7},F={S1,…,S6} S={1,4,5,7),S2={34},S3={2,57S4={1,2,6}2S5={1,3,7 S6={3,5,6} Point# s1 s2 s3 $4 S5 S6 Point# F1 F2 F3 F4 F5 F6 2② 4567 23456 000 000 7 7使得F’是T的一个覆盖：F’ F, 并且 |F|=最小；其中符号| |表示基数。 定理3.3 最优覆盖问题(MCV)是NP难题。 设 T={1, …,7} , F={S1 , …,S6} S1={1,4,5,7}, S2={3,4}, S3={2,5,7},S4={1,2,6}, S5={1,3,7}, S6={3,5,6} S S T S F' S F = =     Point# S1 S2 S3 S4 S5 S6 1 ① ① 1 2 2 ② 3 ③ 3 3 4 ④ ④ 5 ⑤ 5 5 6 ⑥ 6 7 ⑦ 7 7 Point# F1 F2 F3 F4 F5 F6 1 1 0 0 1 1 0 2 0 0 1 1 0 0 3 0 1 0 0 1 1 4 1 1 0 0 0 0 5 1 0 1 0 0 1 6 0 0 0 1 0 1 7 1 0 1 0 1 0 