Funkcja low

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Funkcją 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[edytuj]

  • 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[edytuj]

Dzięki funkcji low możemy odpowiedzieć na pytania:

Bibliografia[edytuj]

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