Funkcja low – dla danego grafu nieskierowanego, funkcja przyporządkowująca każdemu wierzchołkowi grafu najmniejszy numer PreOrder wierzchołka z którego można do niego dojść inną drogą, niż poprzez poprzednika w drzewie utworzonym przez procedurę DFS, tj.
gdzie minimum przebiega po wszystkich wierzchołkach które są potomkami wierzchołka i będącego wierzchołkiem z którego prowadzi krawędź wtórna do oznacza czas PreOrder odwiedzenia wierzchołka.
Przez krawędź wtórną rozumie się krawędź niedrzewową w grafie (tzn. taką krawędź, która nie odwiedzona przez algorytm DFS).
Uwagi Funkcja low określa przyporządkowanie w konkretnym drzewie utworzonym przez procedurę DFS. Trzeba pamiętać, iż takich drzew może być więcej. W każdym wartość funkcji dla danego wierzchołka będzie różna.
Zastosowania Dzięki funkcji low możemy odpowiedzieć na pytania: Czy dany wierzchołek jest punktem artykulacji Czy krawędzie między nim a jego poprzednikiem tworzą most. Do jakiej dwuspójnej składowej należy krawędź między wierzchołkiem a jego poprzednikiem
Bibliografia Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980. , s. 45.
Kategoria:Algorytmy grafowe