Назначение связности графа

Question

Кто-нибудь знает алгоритм для следующей задачи:

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

Я думаю, что частью проблемы (для которой я знаю алгоритм) является вычисление количества способов, которыми 1 линия может быть обрезана, чтобы она стала отключенной. Затем вычисление того, как они могут быть сгруппированы с другими строками, получает значение (M-K)*K + K*(K-1)/2, M = нет. ребер, K = нет. из 1 порезов.

Часть, которую я не знаю, как сделать, это найти количество других способов вырезать 2 линии, например, на графике, который имеет только цикл 1 - 2 - 3 - 1 любая комбинация ребер является допустимым способом резки линии, чтобы отключить график.

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

Дополнительная информация об этой задаче: * Количество ребер <100 000 * Количество вершин <2000 * Программа должна работать максимум 2 секунды на любом графике с вышеуказанными ограничениями * Между двумя вершинами может быть несколько ребер. </p>

Я могу сделать первую часть в O (N + M). Я предполагаю, что сложность для второй части должна быть максимальной O (N * M).

Answer 1

Вы ищете все срезы ребер , содержащие два ребра. Такие срезы ребер существуют только в том случае, если график не более 2-реберно связан .

Статья Карзанова и Тимофеева " Эффективный алгоритм нахождения всех минимальных сечений ребер неориентированного графа *" содержит алгоритм вычисления всех минимальных сечений ребер графа. Вкратце, мне кажется, что алгоритм также можно использовать для поиска разрезов с указанным количеством ребер (например, 2 ребра). Сложность алгоритма O (лямбда n ^ 2), где лямбда - количество ребер в желаемых разрезах (в вашем случае, 2), а n - количество вершин.

Answer 2

Эта проблема является расширением проблемы 2-граничного соединения. Чтобы убедиться, что любое ребро (v, w) в графе не является мостом, мы находим задний край из вершин adjacent to w and including w, идущий к ancestor of v. Здесь предок означает вершины, которые были обнаружены до v. Теперь, если есть только один такой задний край, тогда that back-edge and (v, w) после удаления отключит график.

Answer 3

Тривиальное решение: для всех пар ребер удалите их из графика и посмотрите, все ли еще связано. Это O (n ^ 3), но должно работать.