Для заданного взвешенного неориентированного графа G: Какие условия должны выполняться, чтобы для G было несколько минимальных остовных деревьев?
Я знаю, что MST уникален, когда все веса различны, но вы не можете полностью изменить это утверждение. Если на графике есть несколько ребер с одинаковым весом, может быть несколько MST, но также может быть только один:
В этом примере график слева имеет уникальный MST, а правый - нет.
Самое близкое, что я мог найти, чтобы найти условия неединственности MST, было это:
Рассмотрим все хордовые циклы (циклы, которые не содержат других циклов) в графе G. Если в любом из этих циклов максимальное взвешенное ребро существует несколько раз, то граф не имеет единственного минимального остовного дерева.
Моя идея заключалась в том, что для такого цикла
с n вершинами вы можете пропустить ровно одно из ребер и при этом все вершины быть связанными. Поэтому у вас есть несколько вариантов удаления ребра с наибольшим весом, чтобы получить MST, поэтому MST не уникален.
Тем не менее, я тогда придумал этот пример:
Вы можете видеть, что у этого графа действительно есть цикл, который соответствует моему условию: (E, F, G, H), но, насколько я вижу, минимальное остовное дерево уникально:
Таким образом, кажется, что мое состояние не является правильным (или, возможно, просто не совсем правильно). Я был бы очень признателен за любую помощь в поиске необходимых и достаточных условий неединственности минимального остовного дерева.
Ответы:
на первом рисунке: правый граф имеет уникальное MST, взяв ребра и ( F , G ) с общим весом 2.(F,H) (F,G) Учитывая , граф и пусть М = ( V , Р ) быть как минимум связующего дерева (MST) в G .G=(V,E) M=(V,F) грамм
Если существует ребро с весом w ( e ) = m, такое, что добавление e к нашему MST дает цикл C , и пусть m также будет наименьшим весом ребра из F ∩ C , тогда мы можем создать второй MST, поменяв ребро из F ∩ C с весом ребра m на e . Таким образом, у нас нет уникальности.e = { v , w } ∈ E∖ F W ( E ) = м е С м F∩ C F∩ C м е
источник
Предыдущий ответ указывает алгоритм для определения наличия нескольких MST, который для каждого ребра не входящего в G , находит цикл, созданный путем добавления e к предварительно вычисленному MST, и проверяет , не является ли e единственным тяжелым ребром в этом цикле. Этот алгоритм, скорее всего, будет запущен за O ( | E | | V | ) время.е грамм е е O(|E||V|)
Более простой алгоритм, чтобы определить, есть ли множественные MST из G в сложность во времениO(|E|log(|V|)) .
Обычный прогон алгоритма Крускала занимает времени. Дополнительный выбор ребер не в m может быть сделан за O ( | E | ) время. Таким образом, алгоритм достигает O ( | E | log ( | V | ) ) сложности времени.O(|E|log(|V|)) m O(|E|) O(|E|log(|V|))
Почему этот алгоритм может определять наличие нескольких MST?
Предположим, у нас есть MST который не совпадает с m . Достаточно показать, что алгоритм, работающий на G , не достигнет шага 3, поскольку ребро, найденное в конце шага 2, а не в m и соединяющее два разных дерева, было бы включено в итоговый MST, если бы мы запустили Крускала алгоритм до завершения. Пусть вес самой большой вес, что для любого ребра весом меньше вес , то в т тогда и только тогда , когда он находится в м ' . Поскольку м и м ' имеют одинаковое число ребер веса ш , существуют края весовm′ m G m w w m m′ m m′ w которые находятся в m ', но не в m . Если алгоритм завершил работу до обработки ребер этих ребер, мы закончили. В противном случае, предположим, что алгоритм будет обрабатывать первое ребро e ′ среди этих ребер. Пусть S будет множеством всех ребер, которые до сих пор были сохранены для включения в результирующий MST. S ⊂ м . Поскольку алгоритм не завершил обработку ребра веса w не в m, такого как e ' , он, должно быть, не начал обработку ребер веса w в m . Так что ребра в Sw m′ m e′ S S⊂m w m e′ w m S весят меньше чем . Это означает, что S ⊂ m ′ . Напомним, что e ′ находится в m ′ . Так как { e ′ } ∪ S ⊂ m ′ , где m ′ - дерево, e ′ должно соединить два разных дерева в S, и алгоритм завершается в этой точке.w S⊂m′. e′ m′ {e′}∪S⊂m′ m′ e′ S
Примечание о дальнейшей разработке
Шаг 1 и шаг 2 можно чередовать, чтобы мы могли завершить алгоритм как можно скорее без обработки ребер с большими весами.
Если вы хотите вычислить количество MST, вы можете проверить ответ о том, как вычислить количество MST .
источник
Когда существует более одного минимального связующего дерева?
Новизна этого ответа состоит в основном из двух последних характеристик. Второй из последней характеристики можно рассматривать как самый следующий шаг в подходе ФП . Первые три характеристики вместе можно рассматривать как слегка улучшенную версию ответа dtt .
Когда минимальные остовные деревья уникальны?
Вот мое доказательство.
"Уникальность MST" => "Нет смежного MST": очевидно.
«Нет смежных MST» => «Один изолированный MST»: очевидно.
«Один изолированный MST» => «Один локальный минимальный ST»: изолированный MST светлее всех соседних ST.
«Локальный минимум ST» => «Крайняя режущая кромка»: Доказательство оставлено в качестве упражнения.
"Extreme Cut Edge" => "Уникальность MST": Доказательство оставлено в качестве упражнения.
Вышеуказанные цепочки следствий доказывают теорему.
Еще раз, новизна этих ответов заключается в основном в свойстве «крайний край цикла» и в свойстве «крайний край отреза», в котором используются понятия «не самый тяжелый цикл» и «самый легкий разрез». Я не видел этих концепций в другом месте, хотя они вполне естественны.
Вот два связанных интересных наблюдения.
Два достаточных, но не обязательных условия для уникального MST
источник