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[1].

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ę Następnie wyznacza się wartości funkcji low.

Wierzchołek jest punktem artykulacji, gdy:

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

Przypisy

  1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 10. ISBN 0-387-95014-1.