algorytm.org

Funkcja low

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Funkcja low
Ocena użytkowników:***** / 17
SłabyŚwietny 
Wpisany przez Emil Hotkowski, 02 października 2012 12:05

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.
Jak działa LOW?

Funkcja low jest to tablica którą wypełniamy w następujący sposób:
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:
Przykładowy graf

Nasz dfs sprowadzi nam go (łącznie z numeracją) do takiej postaci:
Przykładowy graf - po DFS

Jednak my wiemy iż posiadamy jeszcze jedną krawędź:
Przykładowy graf - dodatkowa 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.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Emil HotkowskiC/C++
.cpp
.cpp
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 02 października 2012 12:23
Dodaj komentarz