Funkcja low

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.