Когда минимальное остовное дерево для графа не уникально

22

Для заданного взвешенного неориентированного графа G: Какие условия должны выполняться, чтобы для G было несколько минимальных остовных деревьев?

Я знаю, что MST уникален, когда все веса различны, но вы не можете полностью изменить это утверждение. Если на графике есть несколько ребер с одинаковым весом, может быть несколько MST, но также может быть только один:

введите описание изображения здесь

В этом примере график слева имеет уникальный MST, а правый - нет.

Самое близкое, что я мог найти, чтобы найти условия неединственности MST, было это:

Рассмотрим все хордовые циклы (циклы, которые не содержат других циклов) в графе G. Если в любом из этих циклов максимальное взвешенное ребро существует несколько раз, то граф не имеет единственного минимального остовного дерева.

Моя идея заключалась в том, что для такого цикла

введите описание изображения здесь

с n вершинами вы можете пропустить ровно одно из ребер и при этом все вершины быть связанными. Поэтому у вас есть несколько вариантов удаления ребра с наибольшим весом, чтобы получить MST, поэтому MST не уникален.

Тем не менее, я тогда придумал этот пример:

введите описание изображения здесь

Вы можете видеть, что у этого графа действительно есть цикл, который соответствует моему условию: (E, F, G, H), но, насколько я вижу, минимальное остовное дерево уникально:

введите описание изображения здесь

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

Keiwan
источник
1
Ваши самые маленькие циклы известны как циклы без аккордов (более или менее).
Юваль Фильмус

Ответы:

10

на первом рисунке: правый граф имеет уникальное MST, взяв ребра и ( F , G ) с общим весом 2.(F,H)(F,G)

Учитывая , граф и пусть М = ( V , Р ) быть как минимум связующего дерева (MST) в G .G=(V,E)M=(V,F)G

Если существует ребро с весом w ( e ) = m, такое, что добавление e к нашему MST дает цикл C , и пусть m также будет наименьшим весом ребра из F C , тогда мы можем создать второй MST, поменяв ребро из F C с весом ребра m на e . Таким образом, у нас нет уникальности.e={v,w}EFw(e)=meCmFCFCme

DTT
источник
Вы правы, я исправил этот график в вопросе сейчас. Знаете ли вы, является ли это наиболее общим условием, чтобы MST не был уникальным? Или это также может быть как-то определено без необходимости сначала найти MST?
Кейван
1
@Keiwan Я считаю, что если принять во внимание этот вопрос, то условие, изложенное в этом ответе, также является необходимым условием для наличия нескольких MST. Другими словами: граф имеет несколько MST тогда и только тогда, когда построение, описанное HueHang, может быть выполнено. G
Бакуриу
1
m не должен быть наименьшим весом ребра из F∩C. Фактически, это может быть только максимальный вес, в противном случае М не был бы минимальным во-первых. Предположим, что в F∩C есть ребро e 'с w (e') = m '> m = w (e). Тогда замена е на е 'оставит остовное дерево с общим весом меньше М, что противоречит минимальности М.
Чад
2

Предыдущий ответ указывает алгоритм для определения наличия нескольких MST, который для каждого ребра не входящего в G , находит цикл, созданный путем добавления e к предварительно вычисленному MST, и проверяет , не является ли e единственным тяжелым ребром в этом цикле. Этот алгоритм, скорее всего, будет запущен за O ( | E | | V | ) время.eGeeO(|E||V|)

Более простой алгоритм, чтобы определить, есть ли множественные MST из G в сложность во времениO(|E|log(|V|)) .

 1. Запустите алгоритм Крускала на чтобы найти MST m .Gm

 2. Попробуйте снова запустить алгоритм Крускала на В этом цикле, когда у нас есть выбор между ребрами равных весов, мы сначала попробуем ребра не в m , после чего попробуем ребра в m . Всякий раз, когда мы находим ребро, не входящее в m, соединяет два разных дерева, мы утверждаем, что существует несколько MST, завершающих алгоритм.Gmmm

 3. Если мы достигли здесь, то мы утверждаем, что имеет уникальный MST.G

Обычный прогон алгоритма Крускала занимает времени. Дополнительный выбор ребер не в m может быть сделан за O ( | E | ) время. Таким образом, алгоритм достигает O ( | E | log ( | V | ) ) сложности времени.O(|E|log(|V|))mO(|E|)O(|E|log(|V|))

Почему этот алгоритм может определять наличие нескольких MST?

Предположим, у нас есть MST который не совпадает с m . Достаточно показать, что алгоритм, работающий на G , не достигнет шага 3, поскольку ребро, найденное в конце шага 2, а не в m и соединяющее два разных дерева, было бы включено в итоговый MST, если бы мы запустили Крускала алгоритм до завершения. Пусть вес самой большой вес, что для любого ребра весом меньше вес , то в т тогда и только тогда , когда он находится в м ' . Поскольку м и м ' имеют одинаковое число ребер веса ш , существуют края весовmmGmwwmmmmw которые находятся в m ', но не в m . Если алгоритм завершил работу до обработки ребер этих ребер, мы закончили. В противном случае, предположим, что алгоритм будет обрабатывать первое ребро e среди этих ребер. Пусть S будет множеством всех ребер, которые до сих пор были сохранены для включения в результирующий MST. S м . Поскольку алгоритм не завершил обработку ребра веса w не в m, такого как e ' , он, должно быть, не начал обработку ребер веса w в m . Так что ребра в SwmmeSSmwmewmSвесят меньше чем . Это означает, что S m . Напомним, что e находится в m . Так как { e } S m , где m - дерево, e должно соединить два разных дерева в S, и алгоритм завершается в этой точке.wSm.em{e}SmmeS

Примечание о дальнейшей разработке
Шаг 1 и шаг 2 можно чередовать, чтобы мы могли завершить алгоритм как можно скорее без обработки ребер с большими весами.
Если вы хотите вычислить количество MST, вы можете проверить ответ о том, как вычислить количество MST .

Apass.Jack
источник
1

G

  • Ребро является самым тяжелым ребром в уникальном цикле, если оно является самым тяжелым ребром в некотором цикле.
  • Ребро не является самым тяжелым, если оно не является самым тяжелым в любом цикле.
  • Ребро является уникальным самым легким, если оно является самым легким, чтобы пересечь какой-либо разрез.
  • Ребро не является самым легким, если оно не является самым легким, чтобы пересечь любой разрез.
  • Два ST являются смежными, если каждый ST имеет ровно одно ребро, которого нет в другом ST.
  • MST является изолированным MST, если он не смежен с другим MST (когда оба MST рассматриваются как ST).

Когда существует более одного минимального связующего дерева?

G

  • Есть два смежных MST.
  • Там нет изолированных MST.
  • Существует ST, который является таким же легким или более легким, чем все смежные ST, и который является таким же легким, как один смежный ST.
  • Существует преимущество, которое не является ни самым тяжелым с уникальным циклом, ни самым тяжелым без цикла.
  • Существует край, который не является ни уникально-вырезанным-самым легким, ни не-разрезанным-самым легким

Новизна этого ответа состоит в основном из двух последних характеристик. Второй из последней характеристики можно рассматривать как самый следующий шаг в подходе ФП . Первые три характеристики вместе можно рассматривать как слегка улучшенную версию ответа dtt .

G

Когда минимальные остовные деревья уникальны?

G

  • Уникальность MST : существует уникальный MST.
  • Нет смежных MST : нет смежных MST.
  • Один изолированный MST : есть изолированный MST.
  • Один локальный минимум ST : есть ST, который легче, чем все соседние ST.
  • Экстремальное ребро цикла : каждое ребро является самым тяжелым с уникальным циклом или тяжелым без цикла.
  • Чрезвычайно острый край : каждый край является уникальным - самый легкий порез или не самый легкий

Вот мое доказательство.

"Уникальность MST" => "Нет смежного MST": очевидно.

«Нет смежных MST» => «Один изолированный MST»: очевидно.

«Один изолированный MST» => «Один локальный минимальный ST»: изолированный MST светлее всех соседних ST.

m

  • mlmllclmmm1m2m1m2lcm1m2lmm1m2lGmmmmlll
  • mhmhmchchmmhhmmmmhhhch

«Локальный минимум ST» => «Крайняя режущая кромка»: Доказательство оставлено в качестве упражнения.

meememm

"Extreme Cut Edge" => "Уникальность MST": Доказательство оставлено в качестве упражнения.

Вышеуказанные цепочки следствий доказывают теорему.

Еще раз, новизна этих ответов заключается в основном в свойстве «крайний край цикла» и в свойстве «крайний край отреза», в котором используются понятия «не самый тяжелый цикл» и «самый легкий разрез». Я не видел этих концепций в другом месте, хотя они вполне естественны.


Вот два связанных интересных наблюдения.

  • ee e e
  • ee e e

Два достаточных, но не обязательных условия для уникального MST

ab1,bc1,cd1,da2,ac2

1,1,2

Apass.Jack
источник