Существует ли алгоритм поиска остовного дерева неориентированного графа, который минимизирует число вершин, связанных более чем с одним ребром?
Например, с учетом сеточного графика 4 x 4, мы хотим найти такое связующее дерево, как слева (которое имеет 7 вершин, соединенных более чем с одним ребром), а не справа (которое имеет 12):
Изменить: Будет ли эта проблема проще, если мы рассмотрим только плоские графы (или даже только графы сетки)?
Как отмечает Евгений в комментариях, это называется максимальной проблемой остовного дерева листа. Я связался со статьей Википедии о очень тесно связанной связанной проблеме доминирующего множества, которая представляет собой задачу нахождения минимального множества вершин, которые (i) индуцируют связный подграф (ii), удовлетворяют предложению, что для всех других вершин v, некоторая вершина в множестве смежна с v. Две проблемы, которые, как говорят, эквивалентны решению, наблюдая, что, учитывая остовное дерево, мы можем построить связное доминирующее множество, отбрасывая листья (вершины с ровно одной связью) и учитывая связанное доминирующее множество, мы можем извлечь связующее дерево индуцированного подграфа и присоединить другие вершины в виде листьев.
К сожалению, обе проблемы NP-hard, и они остаются NP-жесткими при ограничении на плоские графики. Я не знаком с литературой по связанному доминирующему набору, в частности, но я предполагаю, что существует три угла.
# 1 может выглядеть как странная группировка, но то, что имеет тенденцию происходить в литературе планарного графа, состоит в том, что точные алгоритмы используются в качестве подпрограммы внутри алгоритмов аппроксимации, часто с помощью метода Бренды Бейкер, известного как сдвиг. Одним из свойств планарных графов является то, что параметр, называемый treewidth, ограничен O (sqrt (n)) вместо n, и существуют динамические программы, показатель времени выполнения которых является функцией гораздо меньшей ширины трещины. (Например, на сетках вы можете запускать строку DP за строкой. Механизм дробления деревьев обобщает это на произвольные планарные графики.)
Трудно посоветовать вам лучший курс, не зная, как выглядят экземпляры, и, возможно, даже не экспериментируя с ними. Я бы, наверное, пошел с дверью № 2, но я не уверен, какая будет хорошая формулировка. Хорошей новостью является то, что большая часть алгоритмической сложности абстрагируется в библиотеку solver, которую вы будете использовать. Здесь формулировка неизвестного качества.
Для всех вершин v пусть x_v будет 1, если v является нелистовым и 0, если v является листом. Доминирующая часть набора проста.
minimize sum_v x_v
subject to
for all v, sum_{w such that w = v or w ~ v} x_w >= 1
for all v, x_v in {0, 1}
Здесь я использую ~ для обозначения "рядом с". Принуждение к ограничению связи сложнее. Самый простой подход, который я могу придумать, состоит в том, чтобы решить целочисленную программу как есть, тогда найдите две вершины s и t, которые выбраны, но не связаны в решении, вычислите минимальный разделитель вершин U между s и t среди разделителей, не содержащих выбранную вершину, введите ограничение
(1 - x_s) + (1 - x_t) + sum_{v in U} x_v >= 1
а затем повторите попытку.
Я буду более надеяться на подход, который использует экспоненциально многие переменные, но его может быть значительно сложнее реализовать (генерация строк и столбцов). Выберите вершину r, которая будет принудительно использована как не-лист (предположим или попробуем все возможности). Существует одна переменная y_P для каждого простого пути P с r в качестве конечной точки.
minimize sum_v x_v
subject to
for all v, for all P having v as an interior vertex,
x_v >= y_P
for all v, sum_{P having v as an endpoint} y_P >= 1
for all v, x_v in {0, 1}
for all P, y_P in {0, 1}
Не то, чтобы я знал.
Вы можете использовать подход Breadth First Search, добавив все невидимые вершины в очередь и посетив следующую вершину в очереди. Между тем вы добавляете вершины и их края в очередь приоритетов, основываясь на числе возможных краев, отходящих от соединительной вершины. Затем переходите через PQ рекурсивно, каждый раз добавляя лучший край. Вам просто нужно отвлечь любые ребра, которые содержат уже используемые вершины. Затем проверьте, были ли какие-либо более высокие приоритетные грани в последней вершине и, если да, backtrack.
Это уродливая концепция и может быть хуже в реализации.
Для 4x4 мне понадобится только 7 вершин, соединенных более чем с 1 ребром, что даст мне 9 листовых узлов.
x-o-x x
| |
x-o-x o
| |
o-o-o-o
| | | |
x x x x
По мере увеличения размеров вам нужно расширить шаблон выше.
Для 10x10 у вас будет 59 листовых узлов
x-o-x x-o-x x-o-x x
| | | |
x-o-x x-o-x x-o-x o
| | | |
x-o-x x-o-x x-o-x o
| | | |
x-o-x x-o-x x-o-x o
| | | |
x-o-x x-o-x x-o-x o
| | | |
x-o-x x-o-x x-o-x o
| | | |
x-o-x x-o-x x-o-x o
| | | |
x-o-x x-o-x x-o-x o
| | | |
o-o-o-o-o-o-o-o-o-o
| | | | | | | | | |
x x x x x x x x x x
Для сеток, где Rows < > Cols вам нужно попробовать шаблон в обеих ориентациях, чтобы увидеть, что дает наилучшие результаты.