Я верю, что это правда, но не смог получить формальное доказательство ни того, ни другого. Но правда ли, что любое минимальное остовное дерево достижимо с помощью алгоритма Крускала? Точно так же это верно для алгоритма Прима?
РЕДАКТИРОВАТЬ: Чтобы быть более точным, я хочу знать, если дан MST для подключенного, неориентированного, взвешенного графа, гарантируется ли, что есть последовательность шагов, использующая Kruskal или Prim, которая генерирует это MST. Например, у Крускала есть разные варианты, когда есть несколько ребер с одинаковым весом. Аналогично для прим.
algorithms
graphs
minimum-spanning-tree
domoremath
источник
источник
Ответы:
Как показали комментарий Рафаэля и комментарий j_random_hacker в ответ положительный. Фактически, любое MST достижимо любым алгоритмом MST с некоторыми небольшими исключениями.
Для графа две весовые функции на всех ребрах (до вещественных чисел) определяются как (слабо)G совместимые по сравнению (друг с другом), если мы можем распространить строгий слабый порядок на ребрах, индуцированный любой весовой функцией, на одну и ту же строгую общий заказ. То есть мы можем разработать согласованные правила разрыва связи с каждой весовой функцией, чтобы результат сравнения любых двух ребер одной весовой функцией и ее правил разрыва связи был таким же, как результат другой весовой функции и ее связи. нарушая правила.
Доказательство леммы 1 оставлено в качестве простого упражнения.
(Подсказка к) Доказательство. Один из подходов состоит в проверке условия 5 леммы 1. Другой подход заключается в проверке условия 2 леммы 1, показывая, что в любом наборе ребер самый легкий ребро по также является самым легким ребром по ш 1w2 w1 ,
Алгоритм сравнения на графе определяется какG совместимый с сравнением, если для любых двух (слабо) сравниваемых весовых функций на всех ребрах, совместимых со сравнением, мы можем запустить алгоритм с одной весовой функцией таким образом, чтобы его можно было повторить без каких-либо изменений. с другой весовой функцией. В частности, эти два запуска алгоритма будут иметь одинаковые выходные данные.
Обратите внимание, что большинство, если не все алгоритмы MST, могут быть указаны в двух вариантах. Первый вариант предполагает, что разные ребра имеют разные веса, что используется, когда основной задачей является поиск одного MST (который на самом деле также является уникальным MST). Второй вариант позволяет различным краям группы G иметь одинаковые веса. Конечно, в этом ответе, где основной задачей является поиск всех MST, мы будем заботиться только об алгоритмах MST во втором варианте.G G
Совместимый со сравнением алгоритм MST может найти все MST.
Чтобы доказать вышеприведенное утверждение, нам просто нужно немного адаптировать раздел «Kruskal может найти каждое MST» при вычислении количества MST . Для любого MST от G с весовой функцией ш 1 , выбирает положительный вес , который легче , чем абсолютная разница между любой парой неравных весов ребер. Если мы вычтем этот вес из веса каждого ребра в m, не меняя веса других ребер, мы получим новую весовую функцию, скажем, w 2 . Если ребро e 1 легче, чем e 2 на w 1 , то e 1 должно быть легче, чемm G w1 m w2 e1 e2 w1 e1 сe2 также на . По лемме 2 w 1 и w 2 совместимы по сравнению. Обратите внимание, что m является уникальным MST с w 2 . (Один из способов показать эту уникальность состоит в том, чтобы доказать, что всякий раз, когда вес одного ребра MST уменьшается, любое MST с новой весовой функцией должно содержать это ребро.) Таким образом, любой прогон алгоритма на w 2 найдет m . Поскольку алгоритм совместим для сравнения, мы можем запустить алгоритм таким же образом с w 1 или с w 2 . Поскольку этот прогон найдет уникальный MST, mw2 w1 w2 m w2 w2 m w1 w2 m , он также найдет m с w 1 .w2 m w1
Каждый алгоритм MST совместим для сравнения
Вышеупомянутое предложение звучит слишком широко. Ну, под каждым алгоритмом MST я подразумеваю любой общий алгоритм MST, основанный на сравнении, который я видел, исключая те явно патологические, как неправильные или имеющие ненужные шаги. Поскольку алгоритм MST, совместимый со сравнением, может найти все MST, каждый алгоритм MST может найти все MST. В частности, каждый из четырех классических алгоритмов MST , а именно алгоритмы Боровки, Прима, Крускала и обратного удаления, может найти все MST.
Вот еще три сравнительно-совместимых алгоритма MST.
Следующий алгоритм MST несовместим.
Обратите внимание, что все восемь упомянутых выше алгоритмов MST основаны на сравнении.
Как показать алгоритм совместим сравнения?
Я буду использовать алгоритм Крускала в качестве примера. Ниже приведено описание алгоритма Крускал (во втором аромате) на взвешенный неориентированный связной графе .G
Алгоритм является совместимым для сравнения, если в общих чертах он может быть описан в трех видах шагов.
Это достаточное условие охватывает алгоритмы Боровки, Прима, Крускала, обратное удаление, удаление тяжелого края и добавление не тяжелого края. Обратите внимание, что для соответствия этому достаточному условию нам, возможно, придется изменить некоторые описания алгоритма, не влияя на набор достижимых MST. Из-за того, что алгоритм Крускала, смещенный по степени, совместим со сравнением, позвольте мне подчеркнуть, что это достаточное условие описано в нечетких терминах.
источник