Предположим, у вас есть график G = (V, E), представляющий план этажа одноэтажного торгового центра. Отдельные хранилища представлены вершинами, а ребра между вершинами представляют собой произвольное определение хранилищ, близких друг к другу.
В последнее время в этом торговом центре увеличилось количество краж в магазинах, поэтому руководство решает сделать так, чтобы каждый магазин:
В нем стоит охранник
Или находится рядом с магазином, в котором находится охранник.
При этом наймите как можно меньше охранников.
Как бы вы доказали, что эта задача оптимизации является NP-полной? Я чувствую, что это простое сокращение от задачи о независимом множестве, но я хочу убедиться.
