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.

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

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. ISBN 0-12-289260-7, s. 45.