найти минимальное количество вершин в невзвешенном графе

Question

У меня есть неориентированный взвешенный связный граф. Если я выбираю одну вершину, я автоматически выбираю все связанные с ней вершины. Каков будет алгоритм, чтобы я мог выбрать все вершины графа, используя минимальное количество попыток? В каждой попытке я выбираю одну вершину. Например, для матрицы смежности a [] [] = {1,1,0,0,0, 1,1,1,1,0, 0,1,1,0,0 0,1,0,1,1 0,0,0,1,1} Я должен выбрать вершины 2 и 4 или вершины 2 и 5.

Answer 1

Как уже указывалось красный тунец , это тип проблемы покрытие вершины . В частности, это проблема доминирующего множества , главное отличие в том, что доминирующий набор может быть намного меньше, чем правильное покрытие вершин.

Вы можете смоделировать это как установить проблему с обложкой . Каждая вершина представлена ​​как подмножество, содержащее себя и все смежные вершины. Если вам не нужно гарантировать точное оптимальное решение (только очень хорошее), вы можете применить эвристику , покрывающую жадный набор, для достижения аппроксимации оптимального набора в lg n время.

Answer 2

Это похоже на проблему покрытие вершины . Это NP Complete. Один из алгоритмов, который предлагает Википедия:

"Одна алгоритмическая техника, которая работает здесь называется ограниченное дерево поиска алгоритм, и его идея заключается в несколько раз выбрать какую-нибудь вершину и рекурсивная ветвь, с двумя случаями в каждый шаг: поместите либо текущий вершина или все ее соседи в вершинная оболочка. "

редактировать

вот доказательство того, что решение покрытия вершин решит вашу проблему, при условии, что нет вершины, у которой нет ребра:

(*) Решение покрытия вершин также решает вашу проблему

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

Обратите внимание, что обратное утверждение не выполняется:

(*) Решение вашей проблемы не обязательно решает покрытие вершины.

рассмотрите этот график:

[ ] ----- [X]
 ¦         ¦
 ¦         ¦
[ ] ----- [X]

Непосредственно выбранные узлы отмечены знаком «X». Этот график решает вашу проблему, как указано, но левый край не покрыт (так что это не решение для вершинного покрытия).