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,
![{\displaystyle {\mbox{low}}(s)\geqslant d(w).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/153caa1188bb4fd8e3387c74c23160e8d99a55ba)
Przypisy
Najważniejsze pojęcia |
|
---|
Wybrane klasy grafów |
|
---|
Algorytmy grafowe |
|
---|
problemy grafowe |
|
---|
Inne zagadnienia |
|
---|