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.

$\text{low}(v)=\min (d[v],\underset{k\in K}{\min }(\text{low}[k]),\underset{w\in W}{\min }(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. Szablon:ISBN, s. 45.