W artykule tym chciałbym zaprezentować Wam pewien algorytm zwany low. Choć po głębszym zastanowieniu można by to nazwać funkcją, gdyż jest to tablica wartości, z której możemy odczytać pewne własności grafu.

W tym artykule będę wymagał podstawowej wiedzy z teorii grafów tzn. dfs i numeracja preorder.

Do czego służy LOW?

Funkcja low pozwala nam na jednoznaczne określenie czy krawędź jest mostem albo czy wierzchołek jest punktem artykulacji, wartość funkcji LOW jest to najwcześniejszy wierzchołek w numeracji PreOrder do jakiego możemy dotrzeć pod pewnymi warunkami.

• Most - jest to taka krawędź po której usunięciu graf, SSS lub spójna składowa ulega rozspójnieniu.
  
  
• Punkt artykulacji – analogicznie jest to wierzchołek który rozspójnia nam wyżej wymienione rzeczy.
  
  

Jak działa LOW?

Funkcja low jest to tablica którą wypełniamy w następujący sposób:

• W ramach dfs dla wierzchołka przypisujmy low[v] = PreOrder[v], gdzie PreOrder[v] jest równy numerowi preorder w dfsie.
• Dla każdego już odwiedzonego syna (oprócz ojca) low[v] = min(low[v], PreOrder[u]) gdzie u to ten odwiedzony już wierzchołek z którym mamy jakieś połączenie.
• Dla każdego nieodwiedzonego puszczamy DFS’a i low[v] = min(low[v], low[u]).

Mini dowód + zasada działania

No dobrze, ale część z was może się zapytać „czemu to działa” i w ogóle jak to działa?!
Wiec zacznijmy od początku, funkcja dfs sprowadzi nam graf do postaci drzewa.
Zakładając że mamy drzewo każda krawędź to most i każdy wierzchołek (poza korzeniem i liścmi) jest to punkt artykulacji. Jednak my mamy jeszcze dodatkowe ścieżki i na potrzeby przykładu oznaczymy je na niebiesko.
Rozpatrzmy następujący graf:

Nasz dfs sprowadzi nam go (łącznie z numeracją) do takiej postaci:
Jednak my wiemy iż posiadamy jeszcze jedną krawędź:
Możemy poruszać się po drzewie w następujący sposób, czarnymi krawędziami możemy cały czas schodzić jednak one prowadzą nas w dół, co zwiększa nam potencjalnie LOW a my chcemy je zminimalizować, niebieska krawędź jest to taka krawędź która prowadzi do wierzchołka o wcześniejszym numerze PreOrder.

A więc kiedy opłaca nam się schodzić w dół czarną krawędzią? A no kiedy któryś z synów wierzchołka posiada krawędź do wierzchołka wcześniejszego niż v.

I my dowiadujemy się tego w ramach dfs’a , ponieważ liczenie low odbywa się po powrocie z konkretnego poddrzewa.

Mosty i punkty artykulacji

Most – występuje wtedy jeżeli w danym wierzchołku występuje następująca równość low[v] = PreOrder[v], co jest równoznaczne z tym, iż z całego naszego poddrzewa nie da się dotrzeć nigdzie wyżej czyli krawędź, którą dotarliśmy do tego wierzchołka jest jedyną która prowadzi do danego poddrzewa.
Punkt artykulacji – występuje wtedy kiedy zachodzi równość low[v] ≥ PreOrder[w], gdzie v to syn naszego w. Jest tak ponieważ przez wierzchołek v wierzchołek w łączy się z resztą poddrzewa a wiemy to właśnie stąd że low[v] jest takie a nie inne, czyli nie ma takiej opcji by wejść do poddrzewa wierzchołka w i wyjść z niego inną ścieżką niż v.