Пусть имеем некоторое множество и систему его подмножеств. Требуется найти минимальное количество подмножеств, покрывающих исходное множество. Задачу можно представить с помощью двудольного графа: к первой доле относятся элементы первого множества, ко второму - подмножества (одно подмножество - одна вершина). Вершины первой и второй долей соединяются ребром, если множество вершины второй доли содержит элемент вершины первого множества. Требуется удалить как можно больше вершин из второй доли с инцидентными ей ребрами, но чтобы каждой вершине первой доли осталось хотя бы одно инцидентное ребро.
Пусть, например, исходное множество содержит 12 элементов {1,2,...12}, а система подмножеств следующая: {2, 3}, {4, 8, 10}, {1, 6}, {6, 9}, {2, 11}, {5, 7}, {4, 5, 12}, {8, 11}, {3, 9}, {11}. Тогда в алгебраической форме (на NP-языке) эта задача выглядит следующим образом
Project Cover2
Module Main2
Var x1 As Boolean
Var x2 As Boolean
Var x3 As Boolean
Var x4 As Boolean
Var x5 As Boolean
Var x6 As Boolean
Var x7 As Boolean
Var x8 As Boolean
Var x9 As Boolean
Var x10 As Boolean
Var x11 As Boolean
Var x12 As Boolean
Con c1 As x2+x3>=1
Con c2 As x4+x8+x10>=1
Con c3 As x1+x6>=1
Con c4 As x6+x9>=1
Con c5 As x2+x11>=1
Con c6 As x5+x7>=1
Con c7 As x4+x5+x12>=1
Con c8 As x8+x11>=1
Con c9 As x3+x9>=1
Con c10 As x11>=1
Con e1 As
Minimize(x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12)
или
12*12= 144 варианта...