Какие алгоритмы применяются для определения связности графа после удаления ребер?

Для определения связности графа после удаления рёбер могут применяться, например, следующие алгоритмы:

• Алгоритм на основе поиска максимального потока. e-maxx.ru neerc.ifmo.ru Основан на теореме Форда-Фалкерсона. e-maxx.ru Нужно перебрать все пары вершин и найти между каждой парой наибольшее число непересекающихся по рёбрам путей. e-maxx.ru Для этого используют, например, алгоритм Эдмондса-Карпа. neerc.ifmo.ru
• Алгоритм обратного удаления. ru.wikipedia.org Начинает с максимального по весу ребра и удаляет его, если удаление не приводит к несвязному графу. ru.wikipedia.org Затем проверяет следующее самое тяжёлое ребро и так далее, пока не просмотрит все рёбра и не найдёт пригодные для удаления. ru.wikipedia.org
• Матричный алгоритм установления связности. habr.com Использует матрицу смежности графа. habr.com Если матрицу последовательно возводить в степень, то элементы получаемых матриц будут описывать для соответствующих пар вершин число связывающих их цепей, которые измеряются числом рёбер. habr.com
• Алгоритм поиска точек сочленения. ejudge.babichev.org Точка сочленения — вершина графа, удаление которой вместе с исходящими из неё рёбрами приводит к увеличению числа компонент связности графа. ejudge.babichev.org Для поиска точек сочленения используют, например, наивный поиск: удаляют вершину с рёбрами и проверяют связность. ejudge.babichev.org