Найти все пары узлов, удаление которых отключает граф

Question

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

Проблема выглядит аналогично нахождению точек сочленения (или мостов) связного, неориентированного графа - но с поворотом, что мы должны удалить пару вершин, связанных ребром (и все другие ребра, связанные сэта пара).

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

Хотя верно то, что при нахождении точки сочленения (в большинстве случаев) также будет найдена такая пара, существует множество пар, которые не являются точками сочленения - рассмотрим граф с 4 вершинами, 5 ребрами (квадрат с одной диагональю): у него есть одна такая пара, но нет точек сочленения (ни мостов).

Я потерян.Помоги мне, переполнение стека, ты моя единственная надежда.

Answer 1

Довольно просто, может быть, не самый эффективный:

Пусть граф будет G = (V, E) с V: = {v_1, ..., v_n}.Для каждого подмножества V 'из V пусть G_V' будет подграфом, индуцированным узлами, содержащим узлы V \ V '.Пусть далее N> _v_i: = {v_j в V: {v_i, v_j} в E и j> i} будет множеством всех соседей v_i в G с индексом больше, чем i.Наконец, пусть c (G) будет набором связанных компонентов графа.

Вычислите пары следующим образом:

pairs = {}
for each v in V:
    compute G_{v}
    if G_{v} is unconnected:
        for each v' in N>_v:
            # Ensures that removal of v' does not render subgraph connected
            # (Note comment by MkjG)
            if |c(G_{v})| > 2 or {v'} not in c(G_{v}):
                add {v,v'} to pairs
    else:
        for each v' in N>_v:
            compute G_{v,v'}
            if G_{v,v'} unconnected:
                add {v,v'} to pairs

Связь можно проверить через DFS или BFS в O (м+ N).Следовательно, время выполнения должно быть O (n * k * (m + n)), где k - максимальная степень G.

Answer 2

Обновление до моего предыдущего ответа, основанное на предложении @MkjG использовать DFS для вычисления точек сочленения.

Пусть граф будет G = (V, E) с V: = {v_1, ..., v_n} _.Для каждого подмножества V 'из V пусть G_V' будет подграфом, индуцированным узлами, содержащим узлы V \ V '.Для связного G мы называем v в V точкой сочленения, если G_ {v} не является связным.Пусть N_v будет множеством соседей v в G.

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

1. вычисляет дерево DFS T для некоторого корневого узла r в V
2. r - это точка сочленения, если в T

Пусть результатом DFS на графе G будет функция c на узлах v в V. c (v) является подмножеством N_v, оно содержит v 'в c (v), если обавыполняются следующие условия:

1. v 'является потомком v в T
2. ни один узел в поддереве T' корня T в корне v не имеет заднего края по отношению к предкуиз v

Обратите внимание, что для корневого узла r в T c (r) - это множество всех дочерних элементов r.Функция c может быть вычислена за время O (n + m).

Вычислить пары разделителей следующим образом:

# performs DFS on G for some root node r
c = DFS(G,r)
# computes articulation points of G and corresponding number of components
aps = {}
compCounts = {}
for each v in V:
    numComps = |c(v)|
    if v != r:
        ++numComps
    if numComps > 1:
        add v to aps
        compCounts[v] = numComps
# computes the set of all separator pairs containing at least on ap
S = {}
for each v in aps:
    numComps = compCounts[v]
    for each v' in N_v:
        if numComps > 2:
            # G_{v,v'} has at least two connected components
            add {v,v'} to S
        else:
            # if v' is an isolated node in G_{v}, then G_{v,v'} is connected
            if N_v' != {v}:
                add {v,v'} to S
# computes remaining separator pairs
for each v in V \ aps:
    compute G_{v}
    # performs DFS on G_{v} for some root r_v != v
    c_v = DFS(G_{v},r_v)
    # adds separator pairs for articulation points of G_{v} in N_v
    for each v' in N_v:
        numComps = |c(v')|
        if v' != r_v:
            ++numComps
        if numComps > 1:
            add{v,v'} to S

Время выполнения в O (n * (n + m))

Answer 3

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

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