Punkt artykulacji

Punkt artykulacji, wierzchołek rozcinający, wierzchołek rozdzielający, wierzchołek rozspajający (łac. articulatio staw, przegub) – wierzchołek grafu spójnego, którego usunięcie z grafu rozspójnia go (graf niespójny). Według innej definicji jest to taki wierzchołek, którego usunięcie zwiększa liczbę spójnych składowych grafu.

Warunki

Przed rozpoczęciem poszukiwania punktów artykulacji w grafie, wykonuje się w nim algorytm DFS i określa czasy odwiedzenia danych wierzchołków jako funkcję $d(w).$ Następnie wyznacza się wartości funkcji low.

Wierzchołek $w$ jest punktem artykulacji, gdy:

• jest korzeniem i ma więcej niż jednego syna,
• nie jest korzeniem, a dla przynajmniej jednego jego syna $s$ spełniony jest warunek,

$\text{low}(s)⩾d(w).$