Mosty i punkty artykulacji

02.10.2010 - Michał Karpiński
TrudnośćTrudność

Przykład

Sprawdźmy nasz nowo poznany algorytm w praktyce. W grafie przedstawionym na poniższej animacji znajdują się dwa punkty artykulacji. Korzystając z przedstawionych na poprzedniej stronie kroków postaramy się je znaleźć. Warto zauważyć, że graf składa się z trzech spójnych składowych, czyli po wykonaniu procedury DFS będziemy rozważali trzy różne drzewa.

Łatwo też zauważyć, że w grafie znajdują się dwa mosty – każdy z nich połączony końcem z tym samym punktem artykulacji. W ramach ćwiczeń zastanów się, czy prawdą jest, że każdy most posiada na swoich końcach przynajmniej jeden punkt artykulacji. Narysuj kilka prostych przykładów.

Złożoność czasowa

W ostatnim rozdziale niniejszego artykułu odpowiemy na pytanie: ile czasu zajmie wykonanie algorytmu wyszukiwania mostów i punktów artykulacji w grafie nieskierowanym? Mówimy o ‘czasie‘ jako o pewnej ilości zasobu, który jest niezbędny do wykonania algorytmu, czyli ile operacji elementarnych należy wykonać na danych wejściowych, aby algorytm mógł się zakończyć.

Złożoność czasowa zależna jest od rozmiaru danych wejściowych (choć nie zawsze). W naszym przypadku rozważać będziemy ilość wierzchołków ($ V $) oraz ilość krawędzi ($ E $) podanego grafu. Operacjami, którymi będziemy się posługiwali są przejścia z wierzchołka do jego sąsiada, przeglądnięcie listy sąsiedztwa itp. Będziemy korzystali z notacji dużego O.

1. Na początek załóżmy, że graf wejściowy jest spójny. Wiemy, że procedura DFS działa w czasie $ O(V + E) $, ale gdy graf jest spójny, to $ |E| > |V| - 1 $ i wtedy złożoność czasowa wynosi $ O(E) $.

2. Sprawdźmy jak długo zajmie wyliczenie funkcji $ low $. Dla każdego wierzchołka $ v $ patrzymy na $ d[v] $ i na wszystkie krawędzie wychodzące z $ v $: albo są to synowie w drzewie DFS albo krawędzie wtórne. Więc całkowity czas jest liniowy w stosunku do liczby krawędzi w grafie, czyli $ O(E) $.

3a. Przy szukaniu mostów trzeba ponownie przejrzeć każdy wierzchołek $ v $ w poszukiwaniu takich, które mają własność $ low[v] = d[v] $. Czyli trzeba wykonać $ O(V) $ operacji. Wciąż trzeba mieć na uwadze, że $ |E| > |V| - 1 $, co oznacza, że $ O(V)=O(E) $. Całkowity czas znalezienia mostów w grafie wynosi $ O(E) $.

3b. Przy szukaniu punktów artykulacji również trzeba przejrzeć z powrotem wszystkie wierzchołki. Znalezienie punktów artykulacji - z tego samego powodu co powyżej - zajmie $ O(E) $.

4.636365
Twoja ocena: Brak Ocena: 4.6 (11 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com