Задача на графы

[charming_girl]

Народ, никто из вас раньше не сталкивался с подобной задачей на графы?

Размещение "центров", покрывающих заданную область.
Примеры задач данного типа:
размещение телевизионных или радиопередающих станций на некоторой территории;
размещение военных баз, контролирующих данную территорию;
размещение центров торговли, обслуживающих некоторый район.
Задача: требуется разместить радиопередающие станции на территории, представленной квадратом и разделенной на 16 районов так, чтобы станция, расположенная в любом из районов, могла вещать на этот район и на соседние (по горизонтали и вертикали). Число станций должно быть минимально.
Решение: построим граф, вершины которого соответствуют районам, и две вершины связаны тогда и только тогда, когда соответствующие им районы являются соседними. После построения такого графа задача сводится к нахождению наименьшего доминирующего множества вершин в графе

[charming_girl]

Ребят, помогите, пожалуйста, очень нужно