минимально связанный подграф, содержащий заданный набор узлов

Question

У меня есть невзвешенный связный график. Я хочу найти связанный подграф, который определенно включает в себя определенный набор узлов и как можно меньше дополнений. Как это могло быть достигнуто?

На всякий случай я переформулирую вопрос, используя более точный язык. Пусть G (V, E) - невзвешенный неориентированный связный граф. Пусть N - некоторое подмножество V. Как лучше всего найти наименьший связный подграф G '(V', E ') в G (V, E) такой, что N - это подмножество V'?

Приближения в порядке.

Answer 1

Это точно известная проблема NP-hard Steiner Tree .Без более подробной информации о том, как выглядят ваши экземпляры, сложно дать совет относительно подходящего алгоритма.

Answer 2

Я не могу придумать эффективный алгоритм, чтобы найти оптимальное решение, но, предполагая, что ваш входной граф плотный, следующее может работать достаточно хорошо:

1. Преобразовать ваш входной графG(V, E) к взвешенному графу G'(N, D), где N - это подмножество вершин, которые вы хотите охватить, а D - это расстояния (длины пути) между соответствующими вершинами в исходном графе.Это «свернет» все ненужные вершины в ребра.

2. Вычислить минимальное остовное дерево для G'.

3. "Разверните "минимальное остовное дерево с помощью следующей процедуры: для каждого ребра d в минимальном остовном дереве возьмите соответствующий путь на графике G и добавьте все вершины (включая конечные точки) на пути к результирующему набору V'и все ребра на пути к результирующему набору E'.

Этот алгоритм легко отключить, чтобы дать неоптимальные решения.Пример случая: равносторонний треугольник, в котором есть вершины по углам, в серединах сторон и в середине треугольника, а также ребра по сторонам и от углов до середины треугольника.Чтобы покрыть углы, достаточно выбрать одну среднюю точку треугольника, но этот алгоритм может выбрать стороны.Тем не менее, если график плотный, он должен работать нормально.

Answer 3

Самыми простыми решениями будут следующие:

a) на основе mst: - изначально все узлы V находятся в V '- построить минимальное остовное дерево графа G (V, E) -назовите его T.
- цикл: для каждого листа v в T, который не находится в N, удалите v из V '.
- повторяйте цикл, пока все листья в T не окажутся в N.

b) другое решение заключается в следующем - на основе дерева кратчайших путей.
- выберите любой узел в N, назовите его v, пусть v будет корнем дерева T = {v}.- удалить v из цикла N.

• : 1) выбрать кратчайший путь из любого узла в T, а из любого узла в N. кратчайший путь p: {v, ..., u}, где vнаходится в T и u находится в N. 2) каждый узел в p добавляется к V '.3) каждый узел в p и в N удаляется из N. --- повторять цикл до тех пор, пока N не станет пустым.

В начале алгоритма: вычислить все кратчайшие пути в G, используя любой известный эффективный алгоритм.

Лично я использовал этот алгоритм в одной из своих работ, но он больше подходит для распределенной среды.Пусть N будет набором узлов, которые нам нужно соединить.Мы хотим построить минимальный связный доминирующий набор графа G, и мы хотим дать приоритет для узлов в N. Мы присваиваем каждому узлу уникальный идентификатор id (u).Пусть w (u) = 0, если u находится в N, в противном случае w (1).Мы создаем пару (w (u), id (u)) для каждого узла u.

• каждый узел u создает многосетевой ретрансляционный узел.То есть набор M (u) соседей с 1 переходом, так что каждый сосед 2 переходов является соседом по меньшей мере с одним узлом в M (u).[чем меньше M (u), тем лучше решение].

• u находится в V 'тогда и только тогда, когда: u имеет наименьшую пару (w (u), id (у)) среди всех своих соседей.или u выбран в M (v), где v является соседом 1-го шага u с наименьшим (w (u), id (u)).

- хитрость при централизованном выполнении этого алгоритма заключается в эффективности вычисления соседей с 2 ​​скачками.Лучшее, что я мог получить от O (n ^ 3) - это O (n ^ 2.37) путем умножения матриц.

- Я действительно хотел бы знать, каково соотношение аппроксимации этого последнего решения.

Мне нравится этот справочник по эвристике дерева Штейнера: проблема дерева Штейнера, Хван Франк;Ричардс Дана 1955 - Зимний Павел 1952

Answer 4

Вы можете попытаться сделать следующее:

1. Создание минимального покрытия вершин для нужных узлов N.

2. Сверните эти, возможно, несвязанные, подграфы в «большие» узлы.То есть для каждого подграфа удалите его из графа и замените его новым узлом.Назовите этот набор узлов N'.

3. Сделайте минимальное покрытие вершин узлов в N'.

4. "Распаковать"узлы в N'.

Не уверен, дает ли он вам приближение в пределах определенной границы или около того.Вы могли бы даже обмануть алгоритм, чтобы принять действительно глупые решения.