Проверьте, включен ли край в НЕКОТОРЫХ MST в линейном времени (неявные значения)

Я работаю над алгоритмом, чтобы проверить, включено ли данное ребро в один из возможных mst.

В этом вопросе мы рассматриваем нечеткие значения, а наше ребро e связывает вершины A и B.

До сих пор у меня есть: Если путь может быть сделан из A в B, состоящий из ребер с весами, меньшими или равными весу нашего ребра e, мы можем сказать, что ребро e не является частью любого MST.

Я ничего не вижу здесь/идеи по лучшему алгоритму?

EDIT:

Каковы мысли о решении, включающем свойство цикла. Итак, рассмотрим все ребра с весом меньше рассматриваемого ребра. Если мы сможем сделать путь из A- > B с этими ребрами, можно сказать, что он не является частью какого-либо MST?

Ответ 1

Мы разрешим это с помощью свойства цикла MST, в котором говорится, что "для любого цикла C на графике, если вес ребра e C больше чем веса всех других ребер C, то это ребро не может принадлежать MST."

Теперь запустите следующий алгоритм O(E+V), чтобы проверить, будет ли ребро E, соединяющее вершины u и v, частью MST или нет.

Шаг 1

Запустите dfs из одной из конечных точек (или u или v) ребра E, учитывая только те ребра, которые имеют вес меньше, чем у E.

Шаг 2

Случай 1 Если в конце этого dfs вершины u и v связаны, то ребро E не может быть частью некоторого MST. Это связано с тем, что в этом случае определен определенный цикл в графе с краем E, имеющим максимальный вес, и он не может быть частью MST (из свойства цикла).

Случай 2 Но если в конце dfs u и v остаются отсоединенными, то край E должен быть частью некоторого MST, так как в этом случае E не всегда является максимальным весом всех циклов, из которых он является частью.

Ответ 2

Предположим, что A-B - ваш график, а e - единственный ребро. Тогда e является частью MST, но существует путь A-B, достаточный для вашего условия.

Даже если вы требуете, чтобы e не являлся частью такого пути, это неправильно. Просто возьмите граф с двумя ребрами e1 и e2 между A и B, которые имеют одинаковый вес.

Вы также должны рассмотреть график A-B-C с дополнительным ребром из A-C, где все ребра имеют вес один. Независимо от того, какой край вы удаляете, вы можете получить минимальное связующее дерево. Таким образом, любое ребро может быть частью MST.

Ответ 3

Если вы начнете с проверки веса ребер, было бы слишком сложно достичь вашего ограничения O (n).

Чтобы проверить, должно ли одно ребро быть в MST, вместо этого вы должны начать с проверки того, создает ли этот край граф, цикл, мы все знаем, что MST не может иметь никаких циклов.

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

Таким образом, вы можете выполнить проверку времени O (n), если край находится в MST.

Ответ 4

Я запишу эти мысли об этой проблеме.
Свойство цикла очень важно здесь: наибольшее ребро в любом цикле не может быть в минимальном остовном дереве.
Чтобы доказать свойство цикла, предположим, что существует минимальное остовное дерево T, содержащее ребро e, которое является наибольшим ценовым ребром в цикле. Тогда мы можем удалить ребро e в дереве T и получить два множества S и T. Тогда цикл должен содержать некоторое ребро, отличное от e, которое связывает множества S и T. Тогда из свойства разреза ребро e не может быть в минимальном остовном дереве.

Как только у нас есть свойство цикла, мы продолжаем утверждать, что какое-либо ребро e находится в минимальном остовном дереве:
Ребро e (v, w) не принадлежит ни одному минимальному остовному дереву тогда и только тогда, когда существует путь от v и w, где каждое ребро на этом пути меньше e.

Используя вышеуказанное утверждение, алгоритм выглядит следующим образом:
Удалим все ребра, большие, чем e, теперь мы имеем граф G '. Запустите DFS, чтобы проверить, связаны ли v и w в G '. Если v и w все еще связаны, то ребро e не принадлежит ни одному минимальному остовному дереву. Если v и w не связаны, то ребро e находится в некотором минимальном остовном дереве.