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.

${\displaystyle {\mbox{low}}(v)=\min(d[v],\min _{k\in K}({\mbox{low}}[k]),\min _{w\in W}(d[w])),}$

gdzie minimum przebiega po wszystkich wierzchołkach ${\displaystyle K,}$ które są potomkami wierzchołka ${\displaystyle v}$ i ${\displaystyle W,}$ będącego wierzchołkiem z którego prowadzi krawędź wtórna do ${\displaystyle v.}$ ${\displaystyle d[v]}$ 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).

• 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.

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

• Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980. ISBN 0-12-289260-7, s. 45.