Найти все критические грани MST

Question

У меня есть этот вопрос из книги Роберта Седжуика об алгоритмах.

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

Пожалуйста, предложите алгоритм, который решает эту проблему.

Один подход, о котором я могу думать, делает работу вовремя E.V. Мой подход - запустить алгоритм kruskal.

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

Правильно ли этот алгоритм? Как я могу расширить этот алгоритм для выполнения задания во времени E log E.

Answer 1

Да, ваш алгоритм правильный. Мы можем доказать, что сравнивая выполнение алгоритма Крускаля с аналогичным исполнением, где стоимость некоторого края MST e изменяется на бесконечность. Пока первое исполнение не рассмотрит e, оба исполнения идентичны. После e первое исполнение имеет меньшее количество компонентов, чем второе. Это условие сохраняется до тех пор, пока не будет рассмотрено ребро e ', которое во втором исполнении объединяет компоненты, которые будут иметь e. Поскольку ребро e является единственной разницей между построенными до сих пор лесами, оно должно принадлежать циклу, созданному e '. После e ', казни принимают одинаковые решения, а разница в лесах заключается в том, что первое исполнение имеет e, а второе - e'.

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

• MakeVertex() - создает и возвращает новую вершину.
• Ссылка (u, c, v) - вершины u и v не должны быть связаны. Создает немаркированный край от вершины u до вершины v со стоимостью c.
• Mark (u, v) - вершины u и v должны быть концами ребра e. Знаки e.
• Подключено (u, v) - указывает, связаны ли вершины u и v.
• FindMax (u, v) - вершины u и v должны быть связаны. Возвращает конечные точки немаркированного края по уникальному пути от u до v с максимальной стоимостью вместе с этой стоимостью. Конечные точки этого ребра указаны в том порядке, в котором они отображаются на пути.

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

Answer 2

Условие, которое вы предлагаете, когда критическое значение является правильным, я думаю.Но нет необходимости фактически находить цикл и проверять каждый его край.

Алгоритм Kruskal добавляет ребра в порядке возрастания веса, поэтому последовательность кромочных добавок может быть разбита на блоки с равными весами. Внутри каждого блока с равным весом, если имеется более одного края, соединяющего одни и те же два компонента, тогда все эти ребра являются некритичными, поскольку вместо них можно выбрать любой из других ребер. (Я говорю, что они все некритично, потому что на самом деле мы не задали конкретный MST как часть ввода - если бы мы были тогда, это идентифицировало бы конкретный край для вызова некритического. Край, который на самом деле выбирает Крускал просто артефакт начального заказа на ребра или как была выполнена сортировка).

Но этого недостаточно: возможно, после добавления всех краев веса 4 или менее в MST мы обнаружим, что есть 3 весовых коэффициента, 5 ребер, соединяющих пары компонентов (1, 2), (2, 3) и (1, 3). Хотя ни одна из пар компонентов не соединена более чем с одним из этих трех ребер, нам нужно только (любое) из них 2 - использование всех 3 создаст цикл.

Для каждого блока с равным весом, имеющего вес, обозначаемый w, нам действительно нужно (концептуально) создать новый график, в котором каждый компонент MST до сих пор (т. Е. Используя ребра, имеющие вес < w), является вершина, и существует ребро между двумя вершинами, когда между этими компонентами имеется ребро веса-w. (Это может привести к многократным ребрам.) Затем мы запускаем DFS на каждом компоненте этого графика, чтобы найти любые циклы, и отмечаем каждое ребро, принадлежащее такому циклу, как некритическое. DFS принимает время O (nEdges), поэтому сумма времени DFS для каждого блока (сумма размеров которого равна E) будет O (E).

Обратите внимание, что алгоритм Крускала занимает время O (Elog E), а не O (E), как вы, кажется, подразумеваете, хотя такие люди, как Бернард Чазелль, приблизились к линейной конструкции MST, ТТБОМК пока еще нет ! :)