Алгоритм, чтобы увидеть, есть ли ровно два MST в графике?

Ответ 1

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

Kruskal строит MST для каждой перестановки одинаковых весов ребер

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

Kruskal может найти каждый MST

Кроме того, каждый MST может быть получен путем выбора определенного способа упорядочения каждого множества равных весов, а затем выполнения алгоритма Крускаля. Чтобы увидеть это, предположим, что существует какой-то MST, который не может быть создан таким образом. Теперь вычитаем небольшое количество epsilon (меньше, чем разница между любой парой неравных весов ребер) от веса каждого ребра в этом MST: этот MST теперь является уникальным MST, поэтому Kruskal должен производить этот MST при запуске с новыми весами ребер, Но поскольку мы только скорректировали края не более чем на epsilon, когда края отсортированы по весу, набор всех ребер, имеющих вес w_i - epsilon, должен появиться (в некотором порядке) непосредственно перед множеством ребер, имеющих вес w_i (в некотором порядке), без каких-либо других ребер между этими двумя группами. Но это допустимый возможный порядок для исходных немодифицированных ребер, и алгоритм Крускаля заботится только о упорядочении ребер, а не их конкретных весах, поэтому алгоритм Крускаля должен был создать MST и из этого упорядочения. Это противоречит нашему предположению, поэтому должно быть, что алгоритм Крускаля может производить каждый MST.

Графы компонентов

Вызовите лес, построенный алгоритмом Крускаля, после я >= 0 шагов добавления края F (i) и оставшихся ребер, которые не будут создавать цикл R (i). (Когда к шагу я добавляется ребро, мы формируем R (i), начиная с копии R (i-1) и удаляя только что добавленный край и все другие ребра, которые соединяли одну и ту же пару компонентов. Хотя Kruskal алгоритм фактически исключает эти другие ребра "лениво", определяя R (i) таким образом, упрощает доказательство свойств алгоритма.) Мы разложим алгоритм Крускаля на ряд блоков, каждый из которых состоит из последовательности добавлений кромки, в которой ребра добавляется тот же вес. Call я block-define, если либо я = 0, либо край минимального веса в R (i) больше любого края, добавленного в шагах 1.. i.

Предположим, что после того, как было выполнено какое-то блок-определяющее число я >= 0 шагов добавления края алгоритма Крускаля, наименьшее ребро в R (i) (т.е. следующее наименьшее ребро, которое не создало бы цикл) имеет вес w. Алгоритм Kruskal продолжит соединять все деревья, имеющие какое-то отношение между ними между ними, прежде чем делать что-либо еще, и даже если выбрать другой порядок ребер для этих равных весов может повлиять на то, что деревья производятся, это не может повлиять на множество вершин в каждом дереве. Это более точно:

Определите новый, невзвешенный мультиграф (то есть граф, который может иметь несколько ребер между одной парой вершин) C (i), состоящий из вершины для каждого компонента (дерева) в лесу F (i). Для любой вершины v из C (i) назовем t (v) деревом в F (i), которое соответствует v. Создайте ребро в C между двумя вершинами u и v всякий раз, когда в R (i) существует ребро веса w, между некоторой вершиной в t (u) и некоторой вершиной из t (v). Вызов C (i) графа компонента после шагов i.

Лемма: Предположим, что для некоторого блочно-определяющего числа я C (i) имеет k компонент, содержащих по крайней мере 1 ребро (т.е. компоненты, которые не являются единичными вершинами), а среди этих компонентов есть m >= 2k вершин. Вызовите этот набор вершин M. Тогда, независимо от того, как упорядочены ребра равного веса, после mk дополнительных шагов добавления к краю алгоритма Крускаля m деревьев, соответствующих вершинам в M, будут объединены в k деревьев, а j-го дерева, состоящего из объединения деревьев, соответствующих вершинам j-й компоненты C (i), плюс один или несколько ребер веса w, для каждого 1 <= j <= k. В частности, множество вершин в каждом из k результирующих деревьев не зависит от конкретного упорядочения ребер веса w, порождающих ребра в C (i).

Доказательство:Каждое ребро (u, v) в C (i) соответствует краю веса-w в R (i), который может появиться первым среди всех ребер w-w в некоторой перестановке одинаковых весов и поэтому может быть выбран следующим образом алгоритм Крускаля. Эффект его добавления будет состоять в объединении двух деревьев в F (i) в один из F (i + 1) и отбросить одно или несколько ребер из R (i + 1). Эффект на графе компонентов будет состоять в том, чтобы объединить u и v в C (i) в одну вершину x в C (i + 1), удалить все остальные параллельные ребра между u и v в C (i + 1) и изменить все ребра между третьей вершиной y и u или v в C (i) в ребро между y и новой вершиной x в C (i + 1). Если ребро в одном компоненте C (i) выбирается рядом с Крускалом, ребра в других компонентах не затрагиваются, поэтому, как ребра для разных компонентов чередуются в перестановке, не имеет никакого эффекта. Поэтому мы можем предположить, что все ребра для одного компонента видны первыми, затем все ребра для другого компонента и т.д. До k-го компонента. Предположим, что первая компонента имеет s вершин. Каждый край, добавленный алгоритмом Крускаля, уменьшает количество вершин этого компонента на 1 без отключения компонента. Наличие ребра в компоненте в C (i + j) указывает на наличие края веса-w в R (i + j), которое соединяет два разных дерева в F (i + j), поэтому алгоритм Крускаля будет продолжаться для выбора ребер, которые сжимают этот компонент до тех пор, пока он не станет единственной вершиной в C (i + s-1). Независимо от того, какие ребра выбраны на каждом шаге, вершины в соответствующем дереве в F (i + s-1) будут состоять из объединения всех вершин из деревьев s в F (i). Это можно повторить для остальных компонентов. Если во всех х существует m вершин по k компонентам, то требуется выполнить шаги m-k, чтобы сжать каждый компонент в одну вершину.

Подсчет MST

Теорема:. Число MST является произведением числа охватывающих лесов в мультиграфе C (i) для каждого блока, определяющего i.

Доказательство.. Как установлено в лемме, каждый лес, который может быть создан путем запуска Крускала на некоторой перестановке ребер в C (i), идентичен множеству вершин в каждом результирующем дерево в F (i + mk). Каждое остовное дерево s-вершинного компонента C (i) представляет собой отдельный набор ребер s-1, которые могут быть выбраны алгоритмом Крускала для создания отдельного базового MST, который содержит соответствующий набор деревьев s в F (i), Пролетный лес представляет собой комбинацию связующих деревьев, по одному для каждого компонента, поэтому количество охватывающих лесов является продуктом количества остовных деревьев для каждого содержащегося дерева. Вызовите количество охватывающих лесов в C (i) q (i). Поскольку шаги добавления краев в последующих блоках Крускала не заботятся о структуре краев каждого компонента, а только о том, какие вершины находятся в каждом компоненте, любой выбор q (i) охватывающих лесов для блока, начиная с этапа i, не влияет на количество охватывающих лесов для следующего блока, начинающегося с шага j > i, и все q (i) * q (j) леса различны.

Существуют несколько сложные алгоритмы для вычисления числа связующих деревьев графа, например, на основе теорема Кирхгофа, от imslavko. Я не уверен, что этот будет работать для мультиграфов. Но в любом случае, поскольку мы заботимся только о частных случаях 1, 2 и более 2, мы можем воспользоваться ярлыками.

• Если мы хотим только выяснить, имеет ли граф ровно 1 MST или больше 1, мы можем использовать тот факт, что единственный способ для произведения целых чисел быть равен 1, - если каждый коэффициент равен 1: то есть, если какой-либо блок имеет более одного связующего дерева для C (i), немедленно остановите и сообщите "Больше 1". Если мы закончим без этого, сообщите "1".

• Если мы хотим определить, имеет ли граф ровно 2 MST, мы можем использовать тот факт, что для произведения целых чисел, равных 2, ровно 1 из факторов должен быть равен 2, а все остальные должен быть 1. Для того, чтобы мультиграф имел ровно 2 связующих дерева, он должен состоять из леса плюс ровно один дополнительный (параллельный) край между двумя вершинами, которые уже имеют ребро между ними. (Любой мультиграф, содержащий k-цикл для k >= 3, должен иметь по крайней мере k покрывающих деревьев, образованных путем удаления любого 1 из k ребер.)

Обзор алгоритма

Выполняйте Kruskal, как обычно, но всякий раз, когда начинается новый блок (обозначается добавлением края, который имеет больший вес, чем любой ранее добавленный край), перед добавлением края выполните следующие шаги:

• Создайте пустой мультиграфик C, используя представление списка смежности.
• Сканирование вперед по всем оставшимся краям, имеющим этот вес, и для каждого ребра (u, v) добавить (c (u), c (v)) в C, где c (v) - представитель node v, найденный структурой union/find, используемой для проверки возможности подключения.
• Выполните DFS через каждый компонент этого мультиграфа, используя массив флагов для записи того, какие вершины уже были посещены. Целью этой DFS является проверка циклов и параллельных ребер:
  • Если есть какие-либо циклы длины 3 или выше, компонент имеет не менее 3 остовных деревьев, то есть алгоритм может заканчиваться в этой точке.
  • Если какой-либо параллельный ребро появляется с кратким 3 или более, алгоритм также может немедленно прекратиться.
  • Каждый раз, когда двойной ребро просматривается между двумя вершинами, увеличивайте глобальный счетчик: если этот счетчик превышает 1, то существуют не менее 2 * 2 = 4 MST, поэтому алгоритм может снова прекратиться. Если мы дойдем до конца алгоритма Крускаля, а счетчик будет равен 1, то существуют ровно 2 MST; в противном случае оно должно быть в 0, и в этом случае существует ровно 1 MST.

Все эти дополнительные операции берут линейное время на непересекающихся блоках ребер, поэтому они не будут увеличивать временную сложность лежащего в основе алгоритма Крускала мимо O (E log V).

Ответ 2

Я знаю алгоритм, который определяет число разных Spanning Trees: этот algo использует теорему Кирхгофа. Я помню решение проблемы о количестве минимальных деревьев, но это было экспоненциально, если я правильно помню. Основная идея заключалась в тестировании бит-масок ребер, используемых в дереве, и в том числе-исключая метод.

Кстати, если все веса ребер различны, то существует только один MST. Надеюсь, что это поможет.