Доминирующие множества

Задача о наименьшем покрытии (ЗНП) является примером общей экстремальной задачи, к которой прямо или косвенно сводятся многие практические задачи. Эта задача является классической, хорошо изучена и часто используется в качестве теста для сравнения и оценки различных методов решения трудоёмких задач.

• Множество вершин S Ì V графа G(V,E) называется доминирующим множеством, если SÇG(S)=V.
• Доминирующее множество называется минимальным, если никакое его подмножество не является доминирующим. Доминирующее множество называется наименьшим, если число элементов в нём минимально.

Задача о пяти ферзях – расставить на доске 5 ферзей так, чтобы они не били друг друга – задача об отыскании наименьших доминирующих множеств.

Теорема. Независимое множество вершин является максимальным тогда и только тогда, когда оно является доминирующим.

Задача о выборе переводчика – есть несколько человек, владеющих разными языками. Требуется выбрать из них тех, которые смогут перевести с необходимых языков (покрыть) и при этом за минимальную плату – ЗНП.

Задача о развозке – составить маршрут так, чтобы посетить определённые пункты и затратить на это минимум средств – ЗНП.

Происхождение названия ЗНП – пусть имеется конечное множество V = {v₁, …, v_n} и семейство подмножеств этого множества E = {E₁, …, E_n}. Каждому подмножеству приписан вес. Найти покрытие E* Í E наименьшего веса. На языке графов v_i – это вершины, а E_i – множество смежности вершины, т.е. E_i = Г(v_i).