Несколько минимальных остовных деревьев на одном графике

Question

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

Рассмотрим этот неориентированный граф, в котором все узлы являются узел связан с каждым другим узлом в графе. (Слишком лениво рисовать, но представьте себе, что 9 вершин выходят из каждого узла / входят в него)

Минимальное остовное дерево для этого графа может выглядеть следующим образом:

Я ищу алгоритм, который можно задавать такими параметрами, как: Максимальное число вершин pr. Узел и максимальный диапазон дерева.

Итак, я скажу Алгоритму: ни один узел не может быть напрямую связан с более чем 2 другими узлами, и ни одно дерево в графе не может состоять из более чем 3 вершин (4 узлы) результат, как это решение.

В конечном итоге это будет написано в Python 3.0, но сейчас я просто ищу какой-то вклад в то, как я к этому подхожу.

Answer 1

Во-первых, обратите внимание, что это не тривиальная проблема. Существует множество алгоритмов для поиска всех минимальных остовных деревьев, но включение непересекающихся графов превращает это в еще большую проблему разбиения.

• Это потребует динамического программирования c, чтобы уменьшить ваши путь взрыва.
• Начните с разбиения. Для каждого раздела соберите возможные связующие деревья.
• Результатом этих списков является ваш набор решений для этого раздела.
• Напишите функцию, которая будет возвращать все связующие деревья для данного набора узлов - - запомните результат, чтобы вам не приходилось обновлять список деревьев каждый раз, когда вы меняете номер узла.

Теперь для разделов. Здесь вы получаете числа Гранди: все возможные способы express целевого значения как суммы возможных целых чисел. Это хорошо документированный алгоритм DP, который легко найти в переполнении стека с помощью «алгоритма Python ...». Для иллюстрации я буду работать только с 4 узлами: QWER. Возможные разделы из 4 элементов, по крайней мере, с 2 узлами в каждом разделе:

4
2 2

Критический вопрос здесь заключается в том, являются ли ваши узлы взаимозаменяемыми - например,

QW  ER
QE  WR
QR  WE

... отличные решения для вас? Если это так, теперь у вас есть четыре раздела для обработки; если нет, у вас есть только два.

Для каждого раздела создайте все допустимые связующие деревья. Двухузловые решения тривиальны; Решение с 4 узлами включает в себя конфигурации (с использованием узлов параметров abcd):

ab- c -d (линейный) ab + c -ad (звездочка с символом в центре)

Опять же, если ваши узлы взаимозаменяемы, у вас есть только два решения.

[(ab, b c, cd), (ab, a c, ad)] * ​​1028 *

Наконец, используйте itertools.product, чтобы сформировать все комбинации ваших решений для разделов.

Это заставляет вас двигаться?

---

Обновление для комментария ОП

Узлы и ребра не являются взаимозаменяемыми. Давайте рассмотрим 5-узловую систему QWERT. У этого есть 10 различных разделов - каждый должен быть 3-2 разделения.

QW ERT МЫ QRT QE WRT WR QET QR WET WT QER QT WER ER QWT RT QWE ET QWR

Каждый из они будут следовать той же конфигурации решений. Для иллюстрации рассмотрим первое: QW | ERT. У QW только один гаечный ключ: список ребер (один) [(Q,W)]. ERT имеет три: [(E,R), (R,T)], [(E,R), (E,T)], [(E,T), (R,T)]. Ваша коллекция связующих деревьев - это itertools.product из этих двух списков.