Funkcja low


Funkcja low w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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.

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

Uwagi | edytuj kod

  • 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 kod

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

Bibliografia | edytuj kod

  • Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980. ​ISBN 0-12-289260-7​, s. 45.
Na podstawie artykułu: "Funkcja low" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy