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
Najważniejsze pojęcia |
|
---|
Wybrane klasy grafów |
|
---|
Algorytmy grafowe |
|
---|
problemy grafowe |
|
---|
Inne zagadnienia |
|
---|