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

Question

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

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

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

Answer 1

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

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

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

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

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

Answer 2

Это именно известная NP-труд Штайнер дерево проблема. Без более подробной информации о том, как выглядят ваши экземпляры, трудно дать совет по соответствующему алгоритму.

Answer 3

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

а) на основе MST: - изначально все узлы V находятся в V '- построить минимальное охваченное дерево графа G (V, E) - вызовите его T.
- Цикл: Для каждого листа V в T, который не в N, удалить V от V '.
- Повторите петлю, пока все листья в T не находятся в Н.

б) другое решение является следующим - на основе самых коротких путей дерево.
- Выберите любой узел в 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. Мы даем каждому узлу UA уникальный идентификатор идентификатора (U). Мы позволяем w (u) = 0, если u есть в n, в противном случае w (1). Мы создаем пару (w (u), id (u)) для каждого узла u.

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

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

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

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

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

Answer 4

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

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

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

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

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

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