График имеет два / три разных минимальных остовных дерева?

15

Я пытаюсь найти эффективный метод определения, имеет ли данный граф G два разных минимальных остовных дерева. Я также пытаюсь найти метод, чтобы проверить, есть ли у него 3 различных минимальных остовных дерева. Наивное решение, о котором я думаю, - запустить алгоритм Крускала один раз и найти общий вес минимального остовного дерева. Позже удаляем ребро из графа и снова запускаем алгоритм Крускала и проверяем, является ли вес нового дерева весом исходного минимального остовного дерева, и так для каждого ребра в графе. Время выполнения равно O (| V || E | log | V |), что совсем не хорошо, и я думаю, что есть лучший способ сделать это.

Любое предложение будет полезно, спасибо заранее

algorithms graph-theory graphs spanning-trees Итамар
источник

Было бы неплохо быть осведомленным о таком алгоритме, но он не решит эту текущую проблему

itamar

2

Граф будет иметь уникальное минимальное остовное дерево тогда и только тогда, когда (1) для любого разбиения на два подмножества, ребро минимального веса с одной конечной точкой в каждом подмножестве уникально, и (2) максимальный вес ребро в любом цикле группы уникально.

G

$G$

V (G)

$V(G)$

G

$G$

Юхо

Эти вопросы один и два уже отвечают на ваш вопрос?

Юхо

См. Проблему 23-1 в CLRS, чтобы узнать, как найти второй лучший MST в

.

O (n^{2})

$O(n^2)$

Каве

7

Kapoor & Ramesh ( правильная версия SIAM J. Comput. , Бесплатная (?) Версия личного веб-сайта ) предоставляют алгоритм для перечисления всех минимальных остовных деревьев как на взвешенных, так и на невзвешенных графиках.

Мое понимание основной идеи состоит в том, что вы начинаете с одного MST, а затем меняете ребра, которые лежат вдоль циклов на графике (поэтому, пока весовые коэффициенты в порядке, вы заменяете одно ребро другим, которое, как вы знаете, будет повторно соединять дерево) ,

Для взвешенного случая они дают время выполнения, чтобы перечислить все минимальные остовные деревья где - количество таких остовных деревьев. Он перечисляет их в порядке увеличения веса, и мое текущее (поверхностное) понимание предполагает, что вполне возможно завершить алгоритм после того, как он сгенерировал заданное количество деревьев (так как он только начинается с MST и производит их последовательно). $O(N\cdot|V|)$ $N$

Люк Мэтисон
источник

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

решений. Алгоритм учитывает это?

k

$k$

Рафаэль

1

@ Рафаэль, у меня не было времени, чтобы действительно разобраться с этим (маркировка присвоения), но из моего грубого понимания, это должно быть возможно - оно начинается с некоторого MST, а затем генерирует другие по одному из него.

Люк Мэтисон

1

@SaeedAmiri: «Количество таких охватывающих деревьев» означает «количество минимальных охватывающих деревьев», а не «количество охватывающих деревьев». Если все

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

n^{n - 2}

$n^{n-2}$

Джефф

1

В статье рассматриваются как взвешенные, так и невзвешенные графики, так что вы оба правы;). Я также думаю, что алгоритм допускает возможность остановки после того, как вы сгенерировали желаемое количество деревьев, поэтому для OP это сводится к

. Опять же, мне нужно немного свободного времени, чтобы лучше выглядеть.

O (| V |)

$O(|V|)$

Люк Мэтисон

1

После быстрого чтения взвешенный алгоритм генерирует деревья в порядке возрастания веса (очевидно, начиная с MST). Так и должно быть для целей ОП.

Люк Мэтисон

2

Можно показать, что алгоритм Крускала может найти каждое минимальное остовное дерево; см здесь .

Следовательно, вы можете выполнить Kruskal и, когда у вас есть несколько ребер на выбор, переходить. После того как вы разветвились раз, вы знаете, что существует как минимум различных минимальных остовных деревьев. $k$ $k$ К сожалению, несколько ветвей могут привести к одному и тому же дереву, если добавить ребра одинакового веса в разных порядках, так что это мало поможет без дальнейшей работы / понимания.

Рафаэль
источник

5

Нет. Если вам нужно выбрать между

ребрами за один шаг, возможно, эти

ребер есть во всех остовных деревьях. Возьмем, к примеру

звезду

со всеми ребрами веса 1. Первый шаг, нужно выбрать один из 5 ребер и т. Д. Но, очевидно, существует только одно остовное дерево. Возможно, помогает подсчет количества ребер с одинаковым весом для ребра, включенного в остовное дерево, которое не используется? Интересный вопрос ...

k

$k$

k

$k$

K_{1, 5}

$K_{1,5}$

vonbrand

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

Рафаэль

1

Чтобы увидеть, существует ли более одного MST, рассмотрим, например, алгоритм Крускала. Единственный способ построить разные MST - это исключить ребра, выбрав другой, когда есть несколько с одинаковым весом. Но эти края одинакового веса могли быть исключены, потому что они образовали цикл с более светлыми краями ...

Таким образом, вы должны запустить алгоритм Крускала, и, когда нужно рассмотреть несколько ребер с одинаковым весом, добавьте все из них, которые можно добавить, не создавая циклы. Если остался край этого веса, и он не закрывает цикл ни с одним из ребер с меньшим весом (которые были добавлены ранее), существует более одного MST. Проверка, есть ли ровно 2 или 3 и более, выглядит намного сложнее ...

vonbrand
источник

0

Модификация алгоритма Крускала: при упорядочении ребер кластеризуйте ребра с одинаковым весом. Теперь, в точке, где вы обрабатываете ребра по порядку, каждый раз, когда вы достигаете нового кластера, сначала проверяйте все ребра отдельно и удаляйте из кластера те, которые будут замыкать цикл, учитывая то, что было построено до кластера. Затем запустите все оставшиеся ребра в кластере, теперь пытаясь добавить их в MST. Если какой-либо из них закрывает цикл, то это было обязательно из-за того, что ранее были вставлены другие ребра того же кластера, что означает, что у вас более одного MST.

Это решение сохраняет сложность алгоритма Крускала, только увеличивает время обработки каждого ребра.

Карлос А. Проло
источник

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

Дэвид Ричерби

График имеет два / три разных минимальных остовных дерева?

Ответы: