: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > grafy >

C O   T O   S Ą   G R A F Y ?

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Definicje
Grafem nazywa się strukturę G=(V, E) składającą się z dwóch zbiorów: zbioru wierzchołków grafu V oraz zbioru krawędzi grafu E, przy czym każda krawędź zbioru związana jest z parą dwóch wierzchołków ze zbioru V.
Można więc powiedzieć, że zbiór E jest zbiorem par, których elementy należą do zbioru V:

E = {{x, y} : x i y należą do V}.

d15_rys4.gif 1095 B Jeśli elementami zbioru E są pary nieuporządkowane, tzn. pary (a, b) i (b, a) uważamy za równe, to graf nazywamy nieskierowanym.
Jeśli pary zbioru E traktujemy jako uporządkowane, to mówimy o grafie skierowanym. Na rysunku pokazano graf skierowany - krawędzie grafu skierowanego graficznie oznacza się strzałkami, przy czym strzałkę umieszczamy przy drugim elemencie pary uporządkowanej. Mamy więc tu krawędź (3, 7), a nie krawędź (7, 3). W grafie nieskierowanym krawędź zaznaczamy za pomocą zwykłej linii bez strzałki.

O krawędzi (u, v) w grafie nieskierowanym powiemy, że jest incydentna (przystająca) z wierzchołkami u oraz v.
O krawędzi (u, v) w grafie skierowanym powiemy, że jest wychodząca z wierzchołka u i wchodząca do wierzchołka v.

Jeśli graf zawiera krawędź (u, v), to mówimy, że wierzchołki u i v sąsiadują ze sobą lub są sąsiadami. W grafie skierowanym wierzchołek v nazywamy wówczas następnikiem wierzchołka u, natomiast wierzchołek u poprzednikiem wierzchołka v.

Krawędź grafu postaci (u, u) nazywamy pętlą własną wierzchołka. Na ogół tego typu krawędzie występują tylko w grafach skierowanych.

Ciąg wierzchołków u0-u1-u2-...-un o tej własności, że każdą para sąsiednich wierzchołków (ui, ui+1) jest krawędzią grafu, nazywamy ścieżką lub drogą. Ścieżką jest każda krawędź grafu - graf ma więc co najmniej tyle ścieżek ile krawędzi. Długością ścieżki nazywamy ilość występujących w niej krawędzi.

Jeśli istnieje ścieżka o pierwszym wierzchołku u i ostatnim wierzchołku v, to mówimy, że wierzchołek v jest osiągalny z wierzchołka u, co mniej więcej znaczy tyle, że poruszając się po krawędziach można przebyć drogę z wierzchołka u do wierzchołka v. Ścieżkę, w której wszystkie wierzchołki są różne nazywamy ścieżką prostą.

W grafie skierowanym ścieżkę postaci u-...-u zawierającą co najmniej jedną krawędź nazywamy cyklem. Cykl jest prosty, jeśli wszystkie wierzchołki ścieżki poczynając od drugiego są różne.
W grafie nieskierowanym cyklem nazywamy ścieżkę postaci u-...-u zawierającą co najmniej jedną krawędź, w której wszystkie wierzchołki poczynając od drugiego są różne.

Graf posiadajacy cykl nazywamy grafem cyklicznym, nie posiadający cykli grafem acyklicznym.

W grafie nieskierowanym stopniem wierzchołka nazywamy ilość krawędzi z nim incydentnych. W grafie skierowanym mówimy o stopniu wejściowym - ilość krawędzi wchodzących do wierzchołka, i stopniu wyjściowym - ilość krawędzi wychodzących.


Reprezentacje grafów
Prostą a zarazem "pamięciożerną" reprezentacją grafu jest macierz sąsiedztwa, czyli kwadratowa tablica a wymiaru n x n (n - ilość wierzchołków), w której:

a[i, j] = 1 , gdy istnieje krawędź (i, j)
a[i, j] = 0 , w przeciwnym przypadku

Dla grafów nieskierowanych macierz sąsiedztwa jest symetryczna względem głównej przekątnej, ponieważ a[i, j] i a[j, i] opisują tą samą krawędź.
W grafach, w których każda krawędź ma przypisaną pewną liczbę rzeczywistą zwaną kosztem krawędzi, w tablicy a można zapisać jej koszt zamiast liczby 1.
Graf widoczny na rysunku powyżej zapisany byłby następująco:

   1 2 3 4 5 6 7
    -------------
1 | 0 1 0 0 0 0 0
2 | 0 0 0 0 0 0 0
3 | 0 0 0 0 0 0 1
4 | 1 0 0 0 1 1 0
5 | 0 0 1 1 0 0 1
6 | 0 0 0 0 0 1 0
7 | 1 1 0 0 0 0 0

Taka repzentacja ma ta cenną zaletę, że pozwala w czasie O(1) sprawdzić istnienie dowolnej krawędzi.
Minusem macierzy sąsiedztwa jest natomiast długi (liniowy) czas dostępu do listy wszystkich krawędzi wychodzących z danego wierzchołka - chcąc wykonać dowolną czynność na następnikach wierzchołka 3 trzeba napisać pętlę:

For j:=1 To 7 Do
  If a[3, j]=1 Then Wykonaj(3, j);

Dla tego przykładowego grafu będzie to siedem przebiegów pętli, siedem porównań, a tylko jedno wykonanie procedury Wykonaj.

Przez |V| oznacza się moc zbioru V, czyli ilość wierzchołków grafu, przez |E| ilość krawędzi w grafie.
Do reprezentacji grafu skierowanego zwanej macierzą incydencji potrzebna jest ponumerowana lista wszystkich krawędzi oraz tablica a wymiaru |V| x |E|, w której:

a[i, j] = -1, gdy "j"-ta krawędź wychodzi z węzłą "i"
a[i, j] = 1, gdy "j"-ta krawędź wchodzi do węzłą "i"
a[i, j] = 0, w pozostałych przypadkach

Poszczególne wiersze tej macierzy związane są z węzłami grafu, kolejne wyrazy w wierszu z ponumerowanymi krawędziami. Aby graf przedstawić za pomocą macierzy incydencji nie powinien on zawierać wierzchołków z pętlami własnymi - dla pętli własnej nie bardzo wiadomo co wpisać w komórkę macierzy, ponieważ jest to krawędź zarówno wychodząca jak i wchodząca do wierzchołka. Chociaż, nic w zasadzie nie stoi na przeszkodzie, żeby wówczas wpisać w komórkę np. 2.

W tablicy wymiaru |V| x |V| w wierszu i możemy zapisać listę wszystkich następników wierzchołka i:

   
    1 2 3 4 5 6 7
    -------------
1 | 2 0 0 0 0 0 0
2 | 0 0 0 0 0 0 0
3 | 7 0 0 0 0 0 0
4 | 1 5 6 0 0 0 0
5 | 3 4 7 0 0 0 0
6 | 6 0 0 0 0 0 0
7 | 1 2 0 0 0 0 0

Taką reprecentację grafu nazywamy listami sąsiedztwa. Gdy graf jest nieskierowany na listach zapisujemy wierzchołki z nim incydentne.
Listy sąsiedztwa można przechowywać w tablicy lub na dynamicznych strukturach danych, dodatkowo dla każdej listy warto pamiętać ilość jej składników. Zaletą takiej reprezentacji jest szybki dostęp do wszystkich następników wierzchołka, wadą długi czas sprawdzania, czy graf zawiera daną krawędź - w przypadku zapisu list w tablicy poszczególne wiersze można posortować, dzięki czemu sprawdzenie, czy dany wierzchołek jest następnikiem zajmie czas O(log |V|) (przeszukiwaniem binarnym).

Nie ma idealnej reprezentacji grafu, ale zawsze zawsze można znaleźć jakiś kompromis. Poniższy przykład pokazuje w jaki sposób utworzyć dynamicznie tablice z listami sąsiedztwa zarówno poprzedników jak i następników grafu skierowanego, o znacząco mniejszej złożoności pamięciowej niż tablica wymiaru n x n, ale za to kosztem procesora. I przy założeniu, ze znane są: liczba wierzchołków (węzłów) V oraz liczba krawędzi E.

Type
  PTypWezla = ^TypWezla;
  TypWezla  = Word;
  
  PStopienWezla = ^StopienWezla;
  StopienWezla  = Word;
  
  PKrawedz  = ^Krawedz;
  Krawedz   = Record
                OdWezla, DoWezla : TypWezla;
              End;
  PWezel    = ^Wezel;            
  Wezel     = Record
                IleWej, IleWyj : StopienWezla;
                KrWej, KrWyj   : PTypWezla;
              End;

Po pierwsze trzeba utworzyć trzy tablice:

  • tablicę tymczasową Stos na wszystkie krawędzie grafu,

  • tablicę tymczasową St_Wej, w której zapamiętane będą stopnie wejściowe wszystkich wierzchołków

  • tablicę tymczasową St_Wyj, w której zapamiętane będą stopnie wyjściowe wszystkich wierzchołków

Var
  Stos           : PKrawedz;
  i              : LongInt;
  St_Wej, St_Wyj : PStopienWezla;
...
  {Utwórz tablice}
  GetMem(Stos, (E+1)*SizeOf(Krawedz));
  GetMem(St_Wej, (V+1)*SizeOf(StopienWezla));
  GetMem(St_Wyj, (V+1)*SizeOf(StopienWezla));
  {Wypelnij zerami}
  FillByte(St_Wej^, (V+1)*SizeOf(StopienWezla), 0);
  FillByte(St_Wyj^, (V+1)*SizeOf(StopienWezla), 0);

Ciekawe dlaczego E+1 i V+1?
Z lenistwa, bo tak to już jest, że tablice dynamiczne indeksowane są od 0, a wierzchołki grafu na ogół numeruje się od 1.

Po drugie do tablicy tymczasowej Stos trzeba wczytać wszystkie krawędzie grafu. Podczas wczytywania krawędzi zliczamy stopnie wejściowe i wyjściowe wszystkich wierzchołków - pojawienie się krawędzi (u, v) wiąże się z koniecznością zwiększenia o 1 stopnia wejściowego wierzchołka v (krawędź wchodząca do v) i stopnia wyjściowego wierzchołka u (krawędź wychodząca z u).

  {Dla wszystkich krawedzi grafu}
  For i:=1 To E Do
    With Stos[i] Do
      Begin
        ReadLn(OdWezla, DoWezla);
        St_Wej[DoWezla]:=St_Wej[DoWezla]+1;
        St_Wyj[OdWezla]:=St_Wyj[OdWezla]+1;
      End;

Teraz tworzymy tablicę wszystkich wierzchołków grafu G:

  {Utworz tablice wezlow grafu}
  GetMem(G, (V+1)*SizeOf(Wezel));

Znając stopnie wejściowe i wyjściowe wszystkich wierzchołków można dla każdego wierzchołka i utworzyć dynamiczną tablicę na zapamiętanie listy jego poprzedników G[i].KrWej i następników G[i].KrWyj:

  {Dla wszystkich wierzcholkow utworz tablice na poprzedniki i nastepniki}
  For i:=1 To V Do
    With G[i] Do
      Begin
        GetMem(KrWej, (St_Wej[i]+1)*SizeOf(TypWezla));
        GetMem(KrWyj, (St_Wyj[i]+1)*SizeOf(TypWezla));
        IleWej:=0;
        IleWyj:=0;
      End;

Pozostało przeniesienie końców wszystkich krawędzi ze stosu do odpowiednich tablic jako poprzedniki lub następniki. Przenoszona jest krawędź o końcach (OdWezla, DoWezla): wierzchołek DoWezla należy dopisać jako następnik dla wierzchołka OdWezla, wierzchołek OdWezla jako poprzednik wierzchołka DoWezla:

  {Dla wszystkich krawedzi grafu}
  For i:=1 To E Do
    With Stos[i] Do
      Begin
        {Krawedz: (OdWezla, DoWezla) }
        {W wierzcholku "OdWezla" na liscie nastepnikow dopisz "DoWezla" }
        Inc(G[OdWezla].IleWyj);
        G[OdWezla].KrWyj[G[OdWezla].IleWyj]:=DoWezla;
        {W wierzcholku "DoWezla" na liscie poprzednikow dopisz "OdWezla" }
        Inc(G[DoWezla].IleWej);
        G[DoWezla].KrWej[G[DoWezla].IleWej]:=OdWezla;
      End;

Ostatnia kosmetyczna czynność, to usunięcie trzech tymczasowych tablic:

  FreeMem(Stos, (E+1)*SizeOf(Krawedz));
  FreeMem(St_Wej, (V+1)*SizeOf(StopienWezla));
  FreeMem(St_Wyj, (V+1)*SizeOf(StopienWezla));

"Graf na wymiar", czyli wszystko razem bez komentarzy, zebrane w procedurę o nazwie WczytajGraf z dołożonym programem wygląda tak:

{Free Pascal Compiler}
Type
  PTypWezla   = ^TypWezla;
  TypWezla    = Word;
  PStopienWezla = ^StopienWezla;
  StopienWezla  = Word;
  PKrawedz    = ^Krawedz;
  Krawedz     = Record
                  OdWezla, DoWezla : TypWezla;
                End;
  PWezel      = ^Wezel;
  Wezel       = Record
                  IleWej, IleWyj : TypWezla;
                  KrWej, KrWyj   : PTypWezla;
                End;
  Graf        = PWezel;


Procedure WczytajGraf(V, E : LongInt; Var G : Graf);
Var
  Stos   : PKrawedz;
  i      : LongInt;
  St_Wej : PStopienWezla;
  St_Wyj : PStopienWezla;
Begin
  GetMem(Stos, (E+1)*SizeOf(Krawedz));
  GetMem(St_Wej, (V+1)*SizeOf(StopienWezla));
  GetMem(St_Wyj, (V+1)*SizeOf(StopienWezla));
  FillByte(St_Wej^, (V+1)*SizeOf(StopienWezla), 0);
  FillByte(St_Wyj^, (V+1)*SizeOf(StopienWezla), 0);

  For i:=1 To E Do
    With Stos[i] Do
      Begin
        ReadLn(OdWezla, DoWezla);
        St_Wej[DoWezla]:=St_Wej[DoWezla]+1;
        St_Wyj[OdWezla]:=St_Wyj[OdWezla]+1;
      End;

  GetMem(G, (V+1)*SizeOf(Wezel));
  For i:=1 To V Do
    With G[i] Do
      Begin
        GetMem(KrWej, (St_Wej[i]+1)*SizeOf(TypWezla));
        GetMem(KrWyj, (St_Wyj[i]+1)*SizeOf(TypWezla));
        IleWej:=0;
        IleWyj:=0;
      End;

  For i:=1 To E Do
    With Stos[i] Do
      Begin
        Inc(G[OdWezla].IleWyj);
        G[OdWezla].KrWyj[G[OdWezla].IleWyj]:=DoWezla;
        Inc(G[DoWezla].IleWej);
        G[DoWezla].KrWej[G[DoWezla].IleWej]:=OdWezla;
      End;

  FreeMem(Stos, (E+1)*SizeOf(Krawedz));
  FreeMem(st_wej, (V+1)*SizeOf(StopienWezla));
  FreeMem(st_wyj, (V+1)*SizeOf(StopienWezla));
End;

Var
  i, j, V, E : LongInt;
  G : Graf;
Begin
  Write('Ilosc wierzcholkow = ');
  ReadLn(V);
  Write('Ilosc krawedzi = ');
  ReadLn(E);

  WczytajGraf(V, E, G);
  For i:=1 To V Do
    Begin
      Write('Poprzedniki wezla ', i, ' : ');
      For j:=1 To G[i].IleWej Do Write(G[i].KrWej[j], ' ');
      WriteLn;
      Write('Nastepniki  wezla ', i, ' : ');
      For j:=1 To G[i].IleWyj Do Write(G[i].KrWyj[j], ' ');
      WriteLn;
    End;
  ReadLn;
End.  
Ilosc wierzcholkow = 5
Ilosc krawedzi = 8
1 2
1 3
1 4
2 3
4 3
4 5
3 5
2 5
Poprzedniki wezla 1 :
Nastepniki  wezla 1 : 2 3 4
Poprzedniki wezla 2 : 1
Nastepniki  wezla 2 : 3 5
Poprzedniki wezla 3 : 1 2 4
Nastepniki  wezla 3 : 5
Poprzedniki wezla 4 : 1
Nastepniki  wezla 4 : 3 5
Poprzedniki wezla 5 : 4 3 2
Nastepniki  wezla 5 :