Znajdowanie mostów w grafie


Tematy pokrewne   Podrozdziały
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
  Rozwiązanie nr 1
Rozwiązanie nr 2

Problem

Dla danego grafu nieskierowanego wyznaczyć wszystkie mosty.


 

Mostem (ang. bridge) nazywamy krawędź grafu, której usunięcie zwiększa liczbę spójnych składowych. Na powyższym rysunku mostem jest krawędź 0 – 1.

 

Rozwiązanie nr 1

 

Naiwny sposób rozwiązania tego problemu jest następujący:

 

Obliczamy wstępnie liczbę spójnych składowych w grafie (możemy tutaj wykorzystać algorytm opisany w rozdziale o spójnych składowych) i zapamiętujemy ją. Następnie wybieramy kolejne krawędzie grafu. Wybraną krawędź usuwamy z grafu i ponownie wyznaczamy liczbę spójnych składowych. Jeśli będzie większa od zapamiętanej, to usunięta krawędź jest mostem. W takim przypadku krawędź tę zapamiętujemy, wstawiamy z powrotem do grafu i przechodzimy do następnej krawędzi. Gdy algorytm zakończy swoje działanie, otrzymamy listę krawędzi, które są mostami.

 

Algorytm naiwny wyszukiwania mostów w grafie nieskierowanym

Wejście
n  –  liczba wierzchołków w grafie, n C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
L  –  lista par wierzchołków, które tworzą krawędzie-mosty.
Elementy pomocnicze:
ccn(n,graf)  –  funkcja zwracająca liczbę spójnych składowych w grafie
nc  –  liczba spójnych składowych grafu,  nc C
v,u  –  numery wierzchołków grafu,  v,u C
Lista kroków:
K01: Utwórz pustą listę L  
K02: nc ← ccn(n,graf) ; zapamiętujemy liczbę spójnych składowych
K03: Dla v = 0,1,...,n-1, wykonuj K04...K08 ; przechodzimy przez kolejne wierzchołki grafu
K04:     Dla każdego sąsiada u wierzchołka v wykonuj K05...K08 ; przechodzimy przez wszystkich sąsiadów wierzchołka v
K05:         Jeśli uv, to następny obieg pętli K04 ; każdą krawędź wybieramy jeden raz
K06:         Usuń krawędź v-u z grafu ; wybraną krawędź usuwamy
K07:         Jeśli ccn(n,graf) > nc, to dodaj v-u do L ; jeśli krawędź jest mostem, to zapamiętujemy ją w L
K08:         Dodaj krawędź v-u do grafu ; odtwarzamy krawędź
K09: Zakończ ; mosty w L

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję grafu nieskierowanego, wyszukuje w nim wszystkie mosty i wyświetla je w oknie konsoli. Ponieważ usuwanie krawędzi może być nieco kłopotliwe, zastosowaliśmy tu nieco inną metodę. Otóż wykorzystujemy dodatkową tablicę logiczną VU, której elementy odzwierciedlają wierzchołki. Jeśli dla danej krawędzi v-u oba elementy VU[v] i VU[u] mają wartość false, to krawędź v-u jest usunięta z grafu. Tablica VU jest dodatkowym parametrem funkcji ccn().

 

Przykładowe dane (spójne składowe zostały pokolorowane w celach testowych):

       17 17
0 1 0 2 0 3
1 2 1 14
4 11 4 12
5 6 5 9
6 7 6 8
10 15
11 15
12 15
13 14 13 16
14 16

 

Lazarus
// Wyszukiwanie mostów w grafie nieskierowanym
// Data: 27.12.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------

program bridges;

// Typy dla dynamicznej tablicy list sąsiedztwa, stosu i listy mostów
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

// Definicja typu obiektowego stack
//---------------------------------
stack = object
  private
    S : PslistEl;  // lista przechowująca stos

  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push(v : integer);
    procedure  pop;
end;

// Konstruktor
//------------
constructor stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------

destructor stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function stack.empty : boolean;
begin
  if S = nil then empty := true else empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//----------------------------------
function stack.top : integer;
begin
  top := S^.v;
end;

// Umieszcza dane na stosie
//-------------------------
procedure stack.push(v : integer);
var
  e : PslistEl;
begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure stack.pop;
var
  e :PslistEl;
begin
  if S <> NIL then
  begin
    e := S;
    S := S^.next;
    dispose(e);
  end;
end;

// Funkcja oblicza liczbę spójnych składowych w grafie
// n    - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// VU   - tablica dostępności krawędzi grafu
//----------------------------------------------------
function ccn(n : integer; var graf : TList; VU : array of boolean) : integer;
var
  C        : array of integer;
  S        : stack;
  cc,i,v,u : integer;
  p        : PslistEl;

begin
  S.init;                    // Tworzymy pusty stos
  SetLength(C,n);            // Tworzymy tablicę spójnych składowych
  for i := 0 to n - 1 do
    C[i] := 0;               // Zerujemy tablicę spójnych składowych

  cc := 0;                   // Zerujemy licznik spójnych składowych

  for i := 0 to n-1 do
    if C[i] = 0 then         // Szukamy nieodwiedzonego jeszcze wierzchołka
    begin
      inc(cc);               // Zwiększamy licznik składowych
      S.push(i);             // Na stosie umieszczamy numer bieżącego wierzchołka
      C[i] := cc;            // Wierzchołek numerujemy i oznaczamy jako odwiedzony
      while not S.empty do   // Przechodzimy graf algorytmem DFS
      begin
        v := S.top;          // Pobieramy wierzchołek
        S.pop;               // Usuwamy go ze stosu
        p := graf[v];        // Przeglądamy sąsiadów wierzchołka v
        while p <> nil do
        begin
          u := p^.v;         // Numer sąsiada do u
          if (VU[v] or VU[u]) and (C[u] = 0) then
          begin
            S.push(u);       // Na stos idą sąsiedzi nieodwiedzeni
            C[u] := cc;      // i ponumerowani
          end;
          p := p^.next;
        end;
      end;
    end;
  SetLength(C,0);           // Usuwamy tablicę C
  S.destroy;                // Usuwamy stos
  ccn := cc;                // Zwracamy wynik
end;

// **********************
// *** Program główny ***
// **********************

var
  n,m      : integer;       // Liczba wierzchołków i krawędzi
  A        : TList;         // Tablica list sąsiedztwa
  nc,i,v,u : integer;
  L,p,r    : PslistEl;
  VU       : array of boolean;

begin
  read(n,m);                 // Odczytujemy liczbę wierzchołków i krawędzi

  SetLength(A,n);            // Tworzymy tablice dynamiczne
  SetLength(VU,n);

  for i := 0 to n - 1 do
  begin
    A[i]  := nil;
    VU[i] := true;
  end;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read(v,u);               // Wierzchołki tworzące krawędź
    new(p);                  // Tworzymy nowy element
    p^.v := u;               // Numerujemy go jako w
    p^.next := A[v];         // Dodajemy go na początek listy A[v]
    A[v] := p;
    new(p);                  // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := A[u];
    A[u] := p;
  end;

  // Algorytm znajdowania mostów

  L := nil;                  // Pusta lista mostów

  nc := ccn(n,A,VU);         // Zapamiętujemy liczbę spójnych składowych

  for v := 0 to n - 1 do     // Przechodzimy przez kolejne wierzchołki grafu
  begin
    p := A[v];               // Przeglądamy listę sąsiedztwa wierzchołka v
    while p <> nil do
    begin
      u := p^.v;             // u - numer wierzchołka sąsiedniego w grafie
      if u > v then          // Interesują nas tylko krawędzie w jedną stronę
      begin
        VU[v] := false;      // Zaznaczamy krawędź v-u jako usuniętą
        VU[u] := false;
        if ccn(n,A,VU) > nc then
        begin
          new(r);            // Znaleziony most dodajemy do listy L
          r^.v := u;
          r^.next := L;
          L := r;
          new(r);
          r^.v := v;
          r^.next := L;
          L := r;
        end;
        VU[v] := true;      // Kasujemy zaznaczenie krawędzi jako usuniętej
        VU[u] := true;
      end;
      p := p^.next;
    end;
  end;

  writeln;

  // Wypisujemy znalezione mosty, jednocześnie usuwając listę L

  v := 0;

  while L <> nil do
  begin
    write(L^.v,' ');
    v := (v + 1) mod 2;
    if v = 0 then writeln;
    p := L;
    L := L^.next;
    dispose(p);
  end;

  // Usuwamy pozostałe struktury dynamiczne

  for i := 0 to n - 1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(A,0);
  SetLength(VU,0);
end.
Code::Blocks
// Wyszukiwanie mostów w grafie nieskierowanym
// Data: 27.12.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa, stosu i listy mostów

struct slistEl
{
  slistEl * next;
  int v;
};

class stack
{
  private:
    slistEl * S;   // lista przechowująca stos

  public:
    stack();       // konstruktor
    ~stack();      // destruktor
    bool empty(void);
    int  top(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu stack
//---------------------

// Konstruktor
//------------
stack::stack()
{
  S = NULL;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
stack::~stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool stack::empty(void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int stack::top(void)
{
  return S->v;
}

// Zapisuje na stos
//-----------------
void stack::push(int v)
{
  slistEl * e = new slistEl;
  e->v    = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void stack::pop(void)
{
  if(S)
  {
    slistEl * e = S;
    S = S->next;
    delete e;
  }
}

// Funkcja oblicza liczbę spójnych składowych w grafie
// n    - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// VU   - tablica dostępności krawędzi grafu
//----------------------------------------------------
int ccn(int n, slistEl ** graf, bool * VU)
{
  int * C,cc,i,v,u;
  stack S;
  slistEl * p;

  C = new int[n];            // Tworzymy tablicę spójnych składowych

  for(i = 0; i < n; i++) C[i] = 0; // Zerujemy tablicę spójnych składowych

  cc = 0;                    // Zerujemy licznik spójnych składowych

  for(i = 0; i < n; i++)
    if(!C[i])                // Szukamy nieodwiedzonego jeszcze wierzchołka
    {
      cc++;                  // Zwiększamy licznik składowych
      S.push(i);             // Na stosie umieszczamy numer bieżącego węzła
      C[i] = cc;             // Wierzchołek numerujemy i oznaczamy jako odwiedzony
      while(!S.empty())      // Przechodzimy graf algorytmem DFS
      {
        v = S.top();         // Pobieramy wierzchołek
        S.pop();             // Usuwamy go ze stosu
        for(p = graf[v]; p; p = p->next) // Przeglądamy sąsiadów wierzchołka v
        {
          u = p->v;
          if((VU[v] || VU[u]) && !C[u])
          {
            S.push(p->v);   // Na stos idą sąsiedzi nieodwiedzeni
            C[u] = cc;      // i ponumerowani
          }
        }
      }
    }

  delete [] C;               // Usuwamy tablicę C
  return cc;                 // Zwracamy wynik
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n,m;                   // Liczba wierzchołków i krawędzi
  slistEl ** A;              // Tablica list sąsiedztwa
  int nc,i,v,u;
  slistEl * L,* p,* r;
  bool * VU;

  cin >> n >> m;             // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy zmienne dynamiczne

  VU = new bool[n];          // Krawędzie aktywne
  A  = new slistEl * [n];    // Tablica list sąsiedztwa

  // Tablicę wypełniamy pustymi listami

  for(i = 0; i < n; i++)
  {
    A[i] = NULL;
    VU[i] = true;
  }

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;
    p = new slistEl;
    p->v = u;
    p->next = A[v];
    A[v] = p;
    p = new slistEl;
    p->v = v;
    p->next = A[u];
    A[u] = p;
  }

  // Algorytm znajdowania mostów

  L = NULL;                  // Pusta lista mostów

  nc = ccn(n,A,VU);          // Zapamiętujemy liczbę spójnych składowych

  for(v = 0; v < n; v++)     // Przechodzimy przez kolejne wierzchołki grafu
  {
    p = A[v];                // Przeglądamy listę sąsiedztwa wierzchołka v
    while(p)
    {
      u = p->v;              // u - numer wierzchołka sąsiedniego w grafie
      if(u > v)              // Interesują nas tylko krawędzie w jedną stronę
      {
        VU[v] = VU[u] = false; // Zaznaczamy krawędź v-u jako usuniętą
        if(ccn(n,A,VU) > nc)
        {
          r = new slistEl;   // Znaleziony most dodajemy do listy L
          r->v = u;
          r->next = L;
          L = r;
          r = new slistEl;
          r->v = v;
          r->next = L;
          L = r;
        }
        VU[v] = VU[u] = true; // Kasujemy zaznaczenie krawędzi jako usuniętej
      }
      p = p->next;
    }
  }

  cout << endl;

  // Wypisujemy znalezione mosty, jednocześnie usuwając listę L

  v = 0;

  while(L)
  {
    cout << L->v << " ";
    v ^= 1;
    if(!v) cout << endl;
    p = L;
    L = L->next;
    delete [] p;
  }

  // Usuwamy dynamiczne struktury danych

  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] A;
  delete [] VU;

  return 0;
}
Free Basic
' Wyszukiwanie mostów w grafie nieskierowanym
' Data: 27.12.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa, stosu i listy mostów

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

Type stack
  Private:
    S As slistEl Ptr  ' lista zawierająca stos
  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function top As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu stack
'---------------------

' Konstruktor
'------------
Constructor stack()
  S = 0
End Constructor

' Destruktor
'-----------
Destructor stack()
  While S
    pop()
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function stack.empty() As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------
Function stack.top() As Integer
  top = S->v
End Function

' Zapisuje na stos
'-----------------
Sub stack.push(ByVal v As Integer)
  Dim e As slistEl Ptr
  e = New slistEl
  e->v    = v
  e->Next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub stack.pop()
  Dim e As slistEl Ptr
  If S Then
    e = S
    S = S->Next
    Delete e
  End If
End Sub

' Funkcja oblicza liczbę spójnych składowych w grafie
' n    - liczba wierzchołków w grafie
' graf - tablica list sąsiedztwa
' VU   - tablica dostępności krawędzi grafu
'----------------------------------------------------
Function ccn(ByVal n As Integer, ByVal graf As slistEl Ptr ptr, ByVal VU As Byte Ptr) As Integer

  Dim As Integer Ptr C
  Dim As Integer cc,i,v,u
  Dim As stack S
  Dim As slistEl Ptr p

  C = New Integer [n]        ' Tworzymy tablicę spójnych składowych

  For i = 0 To n - 1
    C[i] = 0                 ' Zerujemy tablicę spójnych składowych
  Next

  cc = 0                     ' Zerujemy licznik spójnych składowych

  For i = 0 To n - 1
    If C[i] = 0 Then         ' Szukamy nieodwiedzonego jeszcze wierzchołka
      cc += 1                ' Zwiększamy licznik składowych
      S.push(i)              ' Na stosie umieszczamy numer bieżącego węzła
      C[i] = cc              ' Wierzchołek numerujemy i oznaczamy jako odwiedzony      
      While S.empty() = 0    ' Przechodzimy graf algorytmem DFS
        v = S.top()          ' Pobieramy wierzchołek
        S.pop()              ' Usuwamy go ze stosu
        p = graf[v]          ' Przeglądamy sąsiadów wierzchołka v
        While p
          u = p->v
          If ((VU[v] = 1) OrElse (VU[u] = 1)) AndAlso (C[u] = 0) Then
            S.push(p->v)     ' Na stos idą sąsiedzi nieodwiedzeni
            C[u] = cc        ' i ponumerowani
          End If 
          p = p->Next
        Wend
      Wend
    End If
  Next
  
  Delete [] C                ' Usuwamy tablicę C

  Return cc                  ' Zwracamy wynik

End Function

' **********************
' *** Program główny ***
' **********************

Dim As Integer n,m,nc,i,v,u
Dim As slistEl Ptr Ptr A
Dim As slistEl Ptr L,p,r
Dim As Byte Ptr VU

Open Cons For Input As #1

Input #1,n,m                 ' Odczytujemy liczbę wierzchołków i krawędzi

A = New slistEl Ptr [n]      ' Tworzymy tablice dynamiczne
VU = New Byte [n]            ' Krawędzie aktywne

' Tablicę A wypełniamy pustymi listami, a tablicę C wypełniamy zerami

For i = 0 To n - 1
  A[i] = 0
  VU[i] = 1
Next

' Odczytujemy kolejne definicje krawędzi.

For i = 0 To m - 1
  Input #1,v,u               ' Wierzchołki tworzące krawędź
  p = new slistEl            ' Tworzymy nowy element
  p->v = u                   ' Numerujemy go jako u
  p->next = A[v]             ' Dodajemy go na początek listy A[v]
  A[v] = p
  p = new slistEl            ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = A[u]
  A[u] = p
Next

' Algorytm znajdowania mostów

L = 0                        ' Pusta lista mostów

nc = ccn(n,A,VU)             ' Zapamiętujemy liczbę spójnych składowych

For v = 0 To n - 1           ' Przechodzimy przez kolejne wierzchołki grafu
  p = A[v]                   ' Przeglądamy listę sąsiedztwa wierzchołka v
  While p
    u = p->v                 ' u - numer wierzchołka sąsiedniego w grafie
    If u > v Then            ' Interesują nas tylko krawędzie w jedną stronę
      VU[v] = 0              ' Zaznaczamy krawędź v-u jako usuniętą
      VU[u] = 0
      If ccn(n,A,VU) > nc Then
        r = new slistEl      ' Znaleziony most dodajemy do listy L
        r->v = u
        r->next = L
        L = r
        r = new slistEl
        r->v = v
        r->next = L
        L = r
      End If
      VU[v] = 1              ' Kasujemy zaznaczenie krawędzi jako usuniętej
      VU[u] = 1
    End If
    p = p->Next
  Wend
Next

Print

' Wypisujemy znalezione mosty, jednocześnie usuwając listę L

v = 0

While L
  Print L->v;
  v = (v + 1) Mod 2
  If v = 0 Then Print
  p = L
  L = L->Next
  Delete [] p
Wend

' Usuwamy dynamiczne struktury danych

For i = 0 To n - 1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] A
Delete [] VU

End
Wynik
17 17
0 1 0 2 0 3
1 2 1 14
4 11 4 12
5 6 5 9
6 7 6 8
10 15
11 15
12 15
13 14 13 16
14 16

10 15
6 7
6 8
5 6
5 9
1 14
0 3

 

Rozwiązanie nr 2

Teraz zaprezentujemy lepszy algorytm wyszukiwania mostów w grafie nieskierowanym (w literaturze nosi on nazwę algorytmu R. Tarjana). Algorytm bazuje na idei drzewa rozpinającego oraz wykorzystuje w specyficzny sposób przejście DFS. Na początek kilka spostrzeżeń, które ten algorytm wykorzystuje.

 

Most nie może być częścią cyklu. Uzasadnienie jest proste i wynika bezpośrednio z definicji mostu. Most jest krawędzią, której usunięcie dzieli składową grafu na dwie oddzielne składowe, czyli takie, dla których nie istnieje droga prowadząca od jednej składowej do drugiej. Lecz cykl w grafie nieskierowanym zawsze można przebyć w obu kierunkach, czyli pomiędzy każdymi dwoma wierzchołkami cyklu zawsze istnieją co najmniej dwie różne drogi dojścia.

Na rysunku obok widzimy fragment grafu. Krawędź łącząca wierzchołki A i B należy do cyklu A–B–C–D–E–A. Gdyby była mostem, to jej usunięcie spowodowałoby, iż od wierzchołka A do B przestałaby istnieć w grafie droga (wierzchołki te znalazłyby się w oddzielnych składowych). Tymczasem od A do B możemy dojść idąc wzdłuż krawędzi cyklu w drugą stronę. To samo dotyczy dowolnej innej krawędzi należącej do tego cyklu.

Most musi należeć do drzewa rozpinającego. To spostrzeżenie wynika z poprzedniego oraz z własności drzew rozpinających. Drzewo rozpinające jest grafem acyklicznym. Krawędzie grafu, które nie znalazły się w drzewie rozpinającym, są krawędziami tworzącymi cykl, ponieważ prowadzą zawsze do wierzchołków, które wcześniej odwiedziła procedura przejścia grafu DFS lub BFS. Są to tzw. krawędzie wtórne (ang. back edges). Skoro tak, to krawędzie te nie mogą być mostami, ponieważ należą do cykli. Pozostaje zatem rozważenie tylko tych krawędzi, które są zawarte w drzewie rozpinającym grafu.

Przykładowy graf

    

Drzewo rozpinające grafu

 

Zwróć uwagę, że każda z szarych krawędzi (czyli takich, które nie należą do drzewa rozpinającego) tworzy cykl z krawędziami czarnymi.

 

W algorytmie Tarjana wykorzystuje się przejście wsteczne drzewa rozpinającego grafu (ang. post-order traversal). Przejście to wykorzystuje algorytm DFS w sposób następujący:

  1. Oznaczamy bieżący wierzchołek jako odwiedzony.
  2. Przetwarzamy wszystkich nieodwiedzonych jeszcze sąsiadów bieżącego wierzchołka.
  3. Przetwarzamy wierzchołek bieżący.

Przejście DFS wykorzystywane jest do numerowania odwiedzanych wierzchołków oraz do wyznaczania dla każdego z nich dodatkowego parametru Low(v). Parametr Low(v) dla danego wierzchołka v jest najmniejszą liczbą z numeru wierzchołka v nadanego mu przez DFS, parametrów Low wszystkich jego synów na drzewie rozpinającym oraz numerów DFS wierzchołków połączonych z v za pomocą krawędzi wtórnych (czyli tych, które nie zostały umieszczone na drzewie rozpinającym). Jeśli napotkamy wierzchołek v, którego numer nadany przez DFS jest równy parametrowi Low(v) i wierzchołek ten posiada na drzewie rozpinającym ojca, to krawędź od tego ojca do wierzchołka v jest mostem.

Prześledźmy na prostym przykładzie kolejne kroki algorytmu Tarjana.

 

      Oto nasz przykładowy graf, w którym mamy znaleźć wszystkie mosty. Graf przejdziemy algorytmem DFS, tworząc po drodze drzewo rozpinające w głąb oraz numerując wierzchołki grafu (numeracja DFS nie ma nic wspólnego z numerami wierzchołków w definicji grafu – określa ona kolejność odwiedzin poszczególnych wierzchołków). Numery te posłużą później do wyznaczenia dla każdego wierzchołka parametru Low, gdy zostaną już przetworzeni wszyscy sąsiedzi.
  Przejście DFS rozpoczynamy od wierzchołka nr 0 (może to być dowolny inny wierzchołek grafu). Wierzchołek ten otrzymuje numer 1 (numery wierzchołków nadane przez DFS będziemy oznaczać kolorem czerwonym), zostaje oznaczony jako odwiedzony, po czym rekurencyjnie algorytm DFS odwiedza wszystkich nieodwiedzonych jeszcze sąsiadów. Przejście do sąsiada tworzy gałąź w drzewie rozpinającym, którą należy zapamiętać w osobnej strukturze danych.
  Zatem z wierzchołka nr 0 przechodzimy do wierzchołka nr 2. Oznaczamy go jako odwiedzonego i numerujemy liczbą 2. Krawędź 0 – 1 staje się krawędzią drzewa rozpinającego.

Odwiedzamy rekurencyjnie wszystkich sąsiadów wierzchołka nr 1.

  Przechodzimy do wierzchołka nr 2. Oznaczamy go jako odwiedzonego i numerujemy liczbą 3. Krawędź 1 – 2 jest dołączana do drzewa rozpinającego.

Ponieważ wszyscy sąsiedzi wierzchołka nr 2 zostali już odwiedzeni, to przechodzimy do przetwarzania samego wierzchołka nr 2. Polega ono na wyznaczeniu parametru Low dla tego wierzchołka. Będzie to najmniejsza wartość z 3 i 1, czyli 1 (3 – numer wierzchołka nadany przez DFS, 1 – numer wierzchołka połączonego krawędzią wtórną 2 – 0). Ponieważ Low(2) = 1 jest różne od numeru 3, który wierzchołkowi nadało DFS, zatem krawędź 1 – 2 (ojciec – syn na drzewie rozpinającym) nie jest mostem..

Wracamy z powrotem do wierzchołka nr 1, z którego tutaj przyszliśmy.

  Z wierzchołka nr 1 przechodzimy do kolejnego nieodwiedzonego sąsiada, czyli do wierzchołka nr 4.

Wierzchołek nr 4 oznaczamy jako odwiedzony, nadajemy mu numer 4. Krawędź 1 – 4 zostaje dodana do drzewa rozpinającego.

Wierzchołek nr 4 posiada dwóch nieodwiedzonych sąsiadów: 3 i 5.

  Z wierzchołka nr 4 przechodzimy do wierzchołka nr 3. Oznaczamy go jako odwiedzony i nadajemy mu numer 5. Krawędź 4 – 5 trafia do drzewa rozpinającego.

Wierzchołek nr 3 posiada nieodwiedzonego jeszcze sąsiada nr 5.

  Z wierzchołka nr 3 przechodzimy do wierzchołka nr 5. Oznaczamy go jako odwiedzony i nadajemy mu numer 6. Krawędź 3 – 5 dołączamy do drzewa rozpinającego.

Wierzchołek nr 5 nie posiada więcej nieodwiedzonych sąsiadów. Zatem wyliczamy dla niego parametr Low jako mniejszą liczbę z 6 (numer nadany wierzchołkowi 5 przez DFS) i 4 (numer DFS wierzchołka 4, do którego prowadzi krawędź wtórna).

Low(5) = min(6,4) = 4

Ponieważ parametr Low ma dla tego wierzchołka wartość różną od numeru nadanego przez DFS, krawędź 3 – 5 nie jest mostem.

Przetwarzanie wierzchołka nr 5 jest zakończone, wracamy do wierzchołka nr 3, z którego przyszliśmy.

  Jesteśmy w wierzchołku nr 3. Wszyscy sąsiedzi zostali odwiedzeni. Wyliczamy parametr Low(3) jako najmniejszą liczbę z 5 (numer DFS wierzchołka 3) i 4 (parametr Low wierzchołka nr 6, który jest synem).

Low(3) = min (5,4) = 4

Ponieważ Low(3) = 4 jest różne od numeru DFS równego 5 dla wierzchołka nr 3, krawędź 4 – 3 nie jest mostem.

Wracamy do wierzchołka nr 4.

  Jesteśmy w wierzchołku nr 4. Wszyscy sąsiedzi wierzchołka nr 4 są odwiedzeni. Obliczamy Low(4) jako najmniejszą liczbę z 4 (numer DFS wierzchołka nr 4), 4 (parametr Low(3) = 4, ponieważ wierzchołek nr 3 jest synem wierzchołka nr 4 na drzewie rozpinającym) oraz 6 (numer DFS wierzchołka nr 5, który łączy się z nim krawędzią wtórną).

Low(4) = min (4,4,6) = 4

Ponieważ parametr Low jest równy numerowi DFS, to krawędź 1 – 4 jest mostem.

Wracamy do wierzchołka nr 1.

  Jesteśmy w wierzchołku nr 1. Wszyscy jego sąsiedzi są odwiedzeni. Obliczamy Low(1) jako najmniejszą liczbę z 2 (numer DFS wierzchołka 1) i 1 (parametr Low(2) = 1, ponieważ wierzchołek nr 2 jest synem na drzewie rozpinającym).

Low(1) = min (2,1) = 1

Parametr Low różni się od numeru DFS, zatem krawędź 0 – 1 nie jest mostem.

  Jesteśmy w wierzchołku startowym nr 0. Wszyscy sąsiedzi zostali już odwiedzeni. Obliczamy Low(0) jako najmniejszą liczbę z 1 (numer DFS wierzchołka 0), 1 (parametr Low(1), ponieważ wierzchołek nr 1 jest synem na drzewie rozpinającym) i 3 (numer DFS wierzchołka 2, który łączy się krawędzią wtórną).

Low(0) = min (1,1,3) = 1

Mamy równość parametru Low(0) z numerem DFS. Jednakże wierzchołek nr 0 nie posiada ojca na drzewie rozpinającym, zatem nie istnieje łącząca go z nim krawędź-most.

Cały graf został przetworzony. Algorytm Tarjana kończy się.

 

Zwróć uwagę, że wszystkie mosty w danej spójnej składowej grafu zostaną znalezione w jednym przejściu DFS. Zatem otrzymujemy algorytm działający w czasie liniowym.

 

Algorytm Tarjana wyszukiwania mostów w grafie nieskierowanym

Funkcja rekurencyjna DFSb(v,vf,graf,D,cv,L)
Wejście
v  –  wierzchołek startowy, v C
vf  –  ojciec wierzchołka v na drzewie rozpinającym w głąb, vf C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
D    tablica numerów DFS dla poszczególnych wierzchołków
cv    referencja do zmiennej zewnętrznej przechowującej numery wierzchołków. Przy pierwszym wywołaniu zmienna powinna zawierać 1. cv C
L    lista mostów. Przechowuje numery wierzchołka startowego i końcowego krawędzi-mostu.
Wyjście:
Wartość parametru Low dla wierzchołka v. Jeśli zostanie znaleziony most, to będzie on dopisany do listy L.
Elementy pomocnicze:
Low    wartość parametru Low dla bieżącego wierzchołka, Low C
temp    chwilowo przechowuje wynik wywołania rekurencyjnego, t C
Lista kroków:
K01: D[v] ← cv ; numerujemy wierzchołek
K02 Low ← cv ; wstępna wartość parametru
K03: cv ← cv + 1 ; kolejny wierzchołek będzie miał numer o 1 większy
K04: Dla każdego sąsiada u wierzchołka v, wykonuj K05...K10 ; przeglądamy wszystkich sąsiadów wierzchołka bieżącego
K05:     Jeśli u = vf, to następny obieg pętli K04 ; pomijamy ojca na drzewie rozpinającym
K06:     Jeśli D[u] = 0, to idź do K09 ; sąsiad nieodwiedzony?
K07:     Jeśli D[u] < Low, to LowD[u] ; odwiedzony, krawędź wtórna. Modyfikujemy parametr Low
K08:     Następny obieg pętli K04  
K09:     temp ← DFSb(u,v,graf,T,D,cv,L) ; rekurencyjne wywołanie funkcji
K10:     Jeśli temp < Low, to Lowtemp ; modyfikujemy parametr Low
K11: Jeśli (vf > -1) (Low = D[v]), to dodaj krawędź vf,v do listy L ; sąsiedzi odwiedzeni. Sprawdzamy warunek mostu
K12: Zakończ z wynikiem Low  

 

Algorytm główny
Wejście
n  –  liczba wierzchołków w grafie, n C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
Lista L zawiera krawędzie będące mostami
Elementy pomocnicze:
cv    przechowuje numery wierzchołków dla DFS, cv C
D    dynamiczna tablica dla numerów wierzchołków nadawanych przez DFS. Elementy są liczbami całkowitymi.
L    lista par wierzchołków, które są połączone mostem
i    numery wierzchołków w grafie, i C
Lista kroków:
K01 Twórz n elementową tablicę D  
K02: Zeruj tablicę D  
K03: Twórz pustą listę L  
K04: Dla i = 0,1,...,n-1 wykonuj K05...K07  
K05:     Jeśli D[i] > 0, to następny obieg pętli K04 ; szukamy nieodwiedzonych jeszcze wierzchołków
K06:     cv ← 1 ; numer DFS pierwszego wierzchołka
K07:     DFSb(i,-1,graf,D,cv,L) ; szukamy mostów
K08: Zakończ z wynikiem L  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję grafu nieskierowanego, wyszukuje w nim wszystkie mosty i wyświetla je w oknie konsoli. Aby uprościć funkcję rekurencyjną DFSb(), większość jej parametrów została zrealizowana jako zmienne globalne.

 

Przykładowe dane (spójne składowe zostały pokolorowane w celach testowych):

       17 17
0 1 0 2 0 3
1 2 1 14
4 11 4 12
5 6 5 9
6 7 6 8
10 15
11 15
12 15
13 14 13 16
14 16

 

Lazarus
// Wyszukiwanie mostów w grafie nieskierowanym
// Data: 28.12.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------

program bridges;

// Typy dla dynamicznej tablicy list sąsiedztwa i listy mostów
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

// Zmienne globalne

var
  n,m,cv : integer;           // Liczba wierzchołków, krawędzi, numeracja
  graf   : TList;             // Tablica list sąsiedztwa
  D      : array of integer;  // Numery DFS
  L      : PslistEl;          // Lista mostów

// Funkcja rekurencyjna wyszukująca mosty
// v  - numer bieżącego wierzchołka
// vf - ojciec bieżącego wierzchołka na drzewie rozpinającym
// Reszta parametrów to zmienne globalne
//----------------------------------------------------------
function DFSb(v,vf : integer) : integer;
var
  Low,temp,u : integer;
  p          : PslistEl;
begin
  D[v] := cv;                 // Numerujemy wierzchołek
  Low  := cv;                 // Wstępna wartość parametru Low
  inc(cv);                    // Następny numer wierzchołka

  p := graf[v];               // Przeglądamy listę sąsiadów
  while p <> nil do
  begin
    u := p^.v;                // u - numer wierzchołka sąsiada
    if u <> vf then           // u nie może być ojcem v
    begin
      if D[u] = 0 then        // Jeśli sąsiad u nie był odwiedzany, to
      begin
        temp := DFSb(u,v);    // rekurencyjnie odwiedzamy go
        if temp < Low then Low := temp;
      end
      else if D[u] < Low then Low := D[u];
    end;
    p := p^.next;             // Następny wierzchołek na liście
  end;

  // Wszyscy sąsiedzi zostali odwiedzeni. Teraz robimy test na most

  if (vf > -1) and (Low = D[v]) then
  begin
    new(p);                   // Mamy most. Dodajemy go do listy L
    p^.v := v;
    p^.next := L;
    L := p;
    new(p);
    p^.v := vf;
    p^.next := L;
    L := p;
  end;

  DFSb := Low;                // Wynik
end;

// **********************
// *** Program główny ***
// **********************

var
  i,u,v : integer;           // Numery wierzchołków
  p,r   : PslistEl;
begin
  read(n,m);                 // Odczytujemy liczbę wierzchołków i krawędzi

  SetLength(graf,n);        // Tworzymy zmienne dynamiczne
  SetLength(D,n);
  L := nil;

  for i := 0 to n - 1 do
  begin
    graf[i] := nil;
    D[i]    := 0;
  end;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read(v,u);               // Wierzchołki tworzące krawędź
    new(p);                  // Tworzymy nowy element
    p^.v := u;               // Numerujemy go jako w
    p^.next := graf[v];      // Dodajemy go na początek listy graf[v]
    graf[v] := p;
    new(p);                  // To samo dla krawędzi w drugą stronę
    p^.v := v;
    p^.next := graf[u];
    graf[u] := p;
  end;

  // Szukamy mostów

  for i := 0 to n - 1 do
    if D[i] = 0 then         // Szukamy nieodwiedzonego wierzchołka
    begin
      cv   := 1;             // Początek numeracji DFS
      DFSb(i,-1);            // Szukamy mostów
    end;

  writeln;

  // Wypisujemy znalezione mosty

  v := 0;

  while L <> nil do
  begin
    write(L^.v,' ');
    v := (v + 1) mod 2;
    if v = 0 then writeln;
    p := L;
    L := L^.next;
    dispose(p);
  end;

  // Usuwamy struktury dynamiczne

  SetLength(D,0);

  for i := 0 to n - 1 do
  begin
    p := graf[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(graf,0);
end.
Code::Blocks
// Wyszukiwanie mostów w grafie nieskierowanym
// Data: 28.12.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i listy mostów

struct slistEl
{
  slistEl * next;
  int v;
};

// Zmienne globalne

int n,m,cv;                   // Liczba wierzchołków, krawędzi, numeracja
slistEl ** graf;              // Tablica list sąsiedztwa
int *D;                       // Numery DFS
slistEl * L;                  // Lista mostów

// Funkcja rekurencyjna wyszukująca mosty
// v  - numer bieżącego wierzchołka
// vf - ojciec bieżącego wierzchołka na drzewie rozpinającym
// Reszta parametrów to zmienne globalne
//----------------------------------------------------------
int DFSb(int v, int vf)
{
  int Low,temp,u;
  slistEl * p;

  // Numerujemy wierzchołek, ustalamy wstępną wartość Low oraz zwiększamy numerację

  D[v] = Low = cv++;

  for(p = graf[v]; p; p = p->next) // Przeglądamy listę sąsiadów
  {
    u = p->v;                 // u - numer wierzchołka sąsiada
    if(u != vf)               // u nie może być ojcem v
    {
      if(!D[u])               // Jeśli sąsiad u nie był odwiedzany, to
      {
        temp = DFSb(u,v);     // rekurencyjnie odwiedzamy go
        if(temp < Low) Low = temp;
      }
      else if(D[u] < Low) Low = D[u];
    }
  }

  // Wszyscy sąsiedzi zostali odwiedzeni. Teraz robimy test na most

  if((vf > -1) && (Low == D[v]))
  {
    p = new slistEl;         // Mamy most. Dodajemy go do listy L
    p->v = v;
    p->next = L;
    L = p;
    p = new slistEl;
    p->v = vf;
    p->next = L;
    L = p;
  }

  return Low;                // Wynik
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  int i,u,v;                 // Numery wierzchołków
  slistEl *p,*r;

  cin >> n >> m;             // Odczytujemy liczbę wierzchołków i krawędzi

  graf = new slistEl * [n]; // Tworzymy zmienne dynamiczne
  D = new int[n];
  L = NULL;

  for(i = 0; i < n; i++)
  {
    graf[i] = NULL;
    D[i]    = 0;
  }

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;           // Wierzchołki tworzące krawędź
    p = new slistEl;         // Tworzymy nowy element
    p->v = u;                // Numerujemy go jako w
    p->next = graf[v];       // Dodajemy go na początek listy graf[v]
    graf[v] = p;
    p = new slistEl;         // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = graf[u];
    graf[u] = p;
  }

  // Szukamy mostów

  for(i = 0; i < n; i++)
    if(!D[i])               // Szukamy nieodwiedzonego wierzchołka
    {
      cv   = 1;             // Początek numeracji DFS
      DFSb(i,-1);           // Szukamy mostów
    }

  cout << endl;

  // Wypisujemy znalezione mosty

  v = 0;

  while(L)
  {
    cout << L->v << " ";
    v ^= 1;
    if(!v) cout << endl;
    p = L;
    L = L->next;
    delete p;
  }

  // Usuwamy struktury dynamiczne

  delete [] D;

  for(i = 0; i < n; i++)
  {
    p = graf[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete graf;

  return 0;
}
Free Basic
' Wyszukiwanie mostów w grafie nieskierowanym
' Data: 28.12.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i listy mostów

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As Integer n,m,cv        ' Liczba wierzchołków, krawędzi, numeracja
Dim Shared As slistEl Ptr Ptr graf  ' Tablica list sąsiedztwa
Dim Shared As Integer Ptr D         ' Numery DFS
Dim Shared As slistEl Ptr L         ' Lista mostów

' Funkcja rekurencyjna wyszukująca mosty
' v  - numer bieżącego wierzchołka
' vf - ojciec bieżącego wierzchołka na drzewie rozpinającym
' Reszta parametrów to zmienne globalne
'---------------------------------------
Function DFSb(ByVal v As Integer, ByVal vf As Integer) As Integer

  Dim As Integer Low,temp,u
  Dim As slistEl Ptr p

  ' Numerujemy wierzchołek, ustalamy wstępną wartość Low oraz zwiększamy numerację

  D[v] = cv: Low = cv: cv += 1

  p = graf[v]
  While p                     ' Przeglądamy listę sąsiadów
    u = p->v                  ' u - numer wierzchołka sąsiada
    If u <> vf Then           ' u nie może być ojcem v
      If D[u] = 0 Then        ' Jeśli sąsiad u nie był odwiedzany, to
        temp = DFSb(u,v)      ' rekurencyjnie odwiedzamy go
        If temp < Low Then Low = temp
      Else
        If D[u] < Low Then Low = D[u]
      End If
    End If 
    p = p->Next
  Wend

  ' Wszyscy sąsiedzi zostali odwiedzeni. Teraz robimy test na most

  If (vf > -1) AndAlso (Low = D[v]) Then
    p = new slistEl          ' Mamy most. Dodajemy go do listy L
    p->v = v
    p->next = L
    L = p
    p = new slistEl
    p->v = vf
    p->next = L
    L = p
  End If

  return Low                 ' Wynik
End Function

' **********************
' *** Program główny ***
' **********************

Dim As Integer i,u,v         ' Numery wierzchołków
Dim As slistEl Ptr p,r

Open Cons For Input As #1

Input #1,n,m                 ' Odczytujemy liczbę wierzchołków i krawędzi

graf = New slistEl Ptr [n]   ' Tworzymy zmienne dynamiczne
D    = New Integer [n]
L    = 0

For i = 0 To n - 1
  graf[i] = 0
  D[i]    = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m - 1
  Input #1,v,u               ' Wierzchołki tworzące krawędź
  p = new slistEl            ' Tworzymy nowy element
  p->v = u                   ' Numerujemy go jako u
  p->next = graf[v]          ' Dodajemy go na początek listy graf[v]
  graf[v] = p
  p = new slistEl            ' To samo dla krawędzi w drugą stronę
  p->v = v
  p->next = graf[u]
  graf[u] = p
Next

Close #1

' Szukamy mostów

For i = 0 To n - 1
  If D[i] = 0 Then          ' Szukamy nieodwiedzonego wierzchołka
    cv   =  1               ' Początek numeracji DFS
    DFSb(i,-1)              ' Szukamy mostów
  End If
Next

Print 

' Wypisujemy znalezione mosty, jednocześnie usuwając listę L

v = 0

While L
  print L->v;
  v = (v + 1) Mod 2
  If v = 0 Then Print
  p = L
  L = L->Next
  Delete [] p
Wend

' Usuwamy dynamiczne struktury danych

For i = 0 To n - 1
  p = graf[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] D
Delete [] graf

End
Wynik
17 17
0 1 0 2 0 3
1 2 1 14
4 11 4 12
5 6 5 9
6 7 6 8
10 15
11 15
12 15
13 14 13 16
14 16

5 6
6 7
6 8
5 9
15 10
1 14
0 3

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.