500руб. за решение задачи., Вроде бы задача не сложная, но у меня от нее цейтнот. Опции

[FunFox]

Кину на мобилу 500 руб. Если кто-то решит задачу.

Дано.
Произвольный граф(НЕориентированый).
Из графа вытаскивают вершину и кладут ее в ящик.
После этого соседние с этой вершиной вершины блокируются(их вытаскивать больше нельзя).
Далее снова вытаскивается вершина, и соседние с ней тоже блокируются.
Так пока не останется доступных вершин.
Для произвольного графа нужно разработать алгоритм(порядок) вытаскивания вершин, такой, чтобы количество вершин в ящике оказалось максимальной.

Очень нужно эту задачу решить, а 500руб. как небольшая мотивация.

P.S. Перебор не предлагать.
P.P.S. Если не до конца понятно условие, спрашивайте.

[John777]

У меня две новости: хорошая и плохая
Хорошая в том, что тот, кто решит эту задачу или хотя бы найдет приближенное решение за полиномиальное время, получит не только 500 рублей на мобильник, но и Филдсовскую премию впридачу за доказательство P=NP.

Короче, это называется Задача о независимом множестве (maximum independent set), и она NP-трудная. Соответственно, любое ее решение для графа общего вида будет перебором с некоторыми эвристиками. Правда, если у вас граф какого-то определенного вида (например, дерево или двудольный граф), то задача решается за полиномиальное время.

А вообще по теме Википедия в помощь - там все достаточно разумно написано.