Здравствуйте.
Представьте граф. Вы представили вершины и рёбра. Пусть у нас нет петель, нет кратности.
Если вы захватили одну вершину, то вы захватываете все вершины соединённые рёбрами с этой вершиной. Дальше захват не распространяется.
Вход: массив вершин f e:1,2,3,4,5,..,100;
массив связей f e: (1,2),(1,3),(4,92),(99,100)
Выход: минимальное число вершин для захвата графа и эти вершины

Предложите ваш вариант решения данной задачи, но не методом полного перебора.
Я приведу пример:

вход:
1..7
(1,2) (1,3) (1,4) (1,5) (2,3) (2,4) (3,7) (3,6)
выход:
2 вершины 1 и 3

Решение данной задачи не требуется мне для какой-нибудь работы или тп. Просто я кроме полого перебора не нашёл вариантов самостоятельно, не гуглил. Программные код не нужен.
Достаточно голого алгоритма

авторТочные решения "без полного перебора" пока науке не известны.

ссылаясь на что вы утверждаете это ?

Addx,
для собственного развития

MasterZiv, спасибо.
А разве мне не потребуется в этом случае перебрать все возможные комбинации вершин ? Или я неправильно вас понял. Покажите как это будет выглядеть на том примере что я написал, пожалуйста.

_мод,
Я сомневаюсь, что вас алгоритм верный.
Приведите пожалуйста обоснование.
Извините, если я ошибаюсь и критикую ваше решение

Что|кто такое|й"рюх" ?

Понимаю что нужно применять логику какую-то. Вот и спрашиваю какую

где обоснование что данный перебор не выродится в полный перебор с возвратом ? дайте пожалуйста обоснование метода. Мне кажется что это ближе к транспортной задаче. Может быть можно к ней привести или рассмотреть как частный случай