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])),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/555bcb64f41ccc1d78f91d75e0287ad2617e881e)
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.
![{\displaystyle d[v]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df1c445d32b96ab0fcd6b896587b81f0e8ae930d)
Brak komentarzy:
Prześlij komentarz