Шарнір (теорія графів)

Вершина ${\displaystyle v}$ графу ${\displaystyle G}$ називається шарніром, якщо підграф (граф, що містить якесь підмножина вершин даного графу) ${\displaystyle G_{1}}$, отриманий з графу ${\displaystyle G}$ видаленням вершини ${\displaystyle v}$ і всіх інцидентних їй ребер, складається з більшої кількості компонент зв'язності, ніж вихідний граф ${\displaystyle G}$.

Граф, що містить два шарніра (вершини 2 і 5) і три блоки (12, 2345, 56).

Ребровим аналогом шарніра є міст. Мостом називається таке ребро графу, в результаті видалення якого кількість компонент зв'язності в графі зростає.

Ефективне вирішення завдання пошуку всіх шарнірів графу засноване на алгоритмі пошуку у глибину.

Нехай задано граф ${\displaystyle G}$. Через ${\displaystyle Adj(v)}$ позначимо множину всіх вершин графу, суміжних з ${\displaystyle v}$. Припустимо, що ми переглянули граф в глибину, почавши з деякою довільній вершини. Занумеруємо всі вершини графу в тому порядку, в якому ми в них увійшли, і кожній вершині ${\displaystyle v}$ підпорядкуємо відповідний номер ${\displaystyle n(v)}$. Якщо в вершину ${\displaystyle u}$ ми вперше потрапили з вершини ${\displaystyle v}$, то вершину ${\displaystyle u}$ будемо називати нащадком ${\displaystyle v}$, а ${\displaystyle v}$ — предком ${\displaystyle u}$. Безліч всіх нащадків вершини ${\displaystyle v}$ позначимо через ${\displaystyle Ch(v)}$. Через ${\displaystyle Low(v)}$ позначимо мінімальний номер серед всіх вершин, суміжних з ${\displaystyle v}$ і з тими вершинами, в які ми прийшли по шляху, що проходить через ${\displaystyle v}$.

Зрозуміло, що величину ${\displaystyle Low(v)}$ можна обчислити рекурсивно, безпосередньо в процесі обходу в глибину: якщо зараз розглядається вершина ${\displaystyle v}$, і з неї не можна перейти в ще не відвіданих вершину (тобто потрібно повернутися до предку ${\displaystyle v}$, або припинити обхід, якщо ${\displaystyle v}$ — стартова вершина), то для всіх її нащадків ${\displaystyle Low}$ вже пораховано, а значить, і для неї можна можна провести відповідні обчислення за формулою

${\displaystyle Low(v)=\min \left\{\min _{x\in Ch(v)}Low(x),\min _{y\in Adj(v)/Ch(v)}n(y)\right\}.}$

Знаючи величину ${\displaystyle Low(v)}$ для всіх вершин графу, можна визначити всі його шарніри згідно з такими правилами:

1. Стартова вершина (тобто та, з якою ми почали обхід) є шарніром тоді і тільки тоді, коли у неї більше одного нащадка.
2. Вершина ${\displaystyle v}$, відмінна від стартової, є шарніром тоді і тільки тоді, коли у неї є нащадок u такий, що ${\displaystyle Low(u)=n(v)}$.

Як приклад розглянемо застосування описаного алгоритму до графу, зображеному на малюнку справа. Числа, якими позначені вершини, відповідають одному з можливих варіантів обходу в глибину. При такому порядку у кожної з вершин рівно один нащадок, за винятком вершини 6, у якій нащадків немає. Стартова вершина 1 має єдиного нащадка, отже, шарніром вона не є. Для інших вершин обчислимо значення, що цікавить нас функції:

${\displaystyle Low(6)=5,Low(5)=2,Low(4)=2,Low(3)=2,Low(2)=1}$.

У вершини 2 є нащадок 3, а у 5 нащадок 6 — в обох випадках виконано шукане співвідношення ${\displaystyle Low(u)=n(v)}$. Отже, 2 і 5 є шарнірами. Інших шарнірів в цьому графі немає.

GetArticulationPoints(i, d)
    visited[i] = true
    depth[i] = d
    low[i] = d
    childCount = 0
    isArticulation = false
    for each ni in adj[i]
        if not visited[ni]
            parent[ni] = i
            GetArticulationPoints(ni, d + 1)
            childCount = childCount + 1
            if low[ni] >= depth[i]
                isArticulation = true
            low[i] = Min(low[i], low[ni])
        else if ni <> parent[i]
            low[i] = Min(low[i], depth[ni])
    if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
        Output i as articulation point

• Міст (теорія графів)

• Код на С++, Python та Java для пошуку шарнірів