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

[FunFox]

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

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

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

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

[WildKOT]

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

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

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

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

1. Из графа удаляем рёбра соединиющие вершина саму с собой, они будут мешать алгоритму.
2. Для каждой вершины считаем число незаблокированных рёбер
Логично предположить, что следует выбирать вершины, которые имеют минимальное число рёбер, чтобы сумма степеней выбранных вершин была минимальна.
3. Для вершин степени 0 очевидно, что их надо выбрать в первую очередь.
4. Выбор вершины А степени 1 помешает выбору другой вершины Б, но если выбрать Б, то в лучшем случае только А будет заблокирована. Поэтому всегда можно выбирать вершину степени 1.
(при выборе вершины все заблокированные вершины вместе с рёбрами исходящими из них выключаются из рассмотрения)
5. Каждый следующий шаг вытаскиваем вершину с минимальной степенью.

[0]

1. Из графа удаляем рёбра соединиющие вершина саму с собой, они будут мешать алгоритму.
2. Для каждой вершины считаем число незаблокированных рёбер
Логично предположить, что следует выбирать вершины, которые имеют минимальное число рёбер, чтобы сумма степеней выбранных вершин была минимальна.
3. Для вершин степени 0 очевидно, что их надо выбрать в первую очередь.
4. Выбор вершины А степени 1 помешает выбору другой вершины Б, но если выбрать Б, то в лучшем случае только А будет заблокирована. Поэтому всегда можно выбирать вершину степени 1.
(при выборе вершины все заблокированные вершины вместе с рёбрами исходящими из них выключаются из рассмотрения)
5. Каждый следующий шаг вытаскиваем вершину с минимальной степенью.

Это неверно.
Для контрпримера можно взять граф из 7 вершин A,B1,B2,B3,C1,C2,C3.
Ребра: (A,Bi) для всех i, (Bi,Cj) для все i и j, (Ci,Cj) для всех i!=j.
Вершина A имеет степень 3, вершины Bi имеют степень 4, вершины Сi имеют степень 5.
Но взяв вершину с минимальной степенью A мы исключим вершины Bi и останется полный граф из которого можно взять только 1 вершину. Итого сможем набрать только 2 вершины.
А взяв сначала вершину B1 мы сможем взять B2 а затем и B3 набрав в итоге 3 вершины.