Informatyka dla klas II

Grafy

Pojęcia wstępne

Graf (ang. graph) jest strukturą danych składającą się z dwóch zbiorów: zbioru wierzchołków (ang. vertices) i zbioru krawędzi (ang. edges), co matematycznie zapisujemy w postaci uporządkowanej pary (tzn. takiej, gdzie istotna jest kolejność elementów tworzących tę parę):

 

G = (V, E)    
V = { v1, v2,...,vn }    zbiór n ponumerowanych wierzchołków (ang. V = Vertex)
E = { e1, e2, ... em }    zbiór m ponumerowanych krawędzi (ang. E = Edge). Każda krawędź jest parą (w grafie skierowanym parą uporządkowaną) wierzchołków grafu połączonych tą krawędzią:

E = {(u,v): u,v V}

 

Rząd grafu (ang. graph order) to liczba wierzchołków w grafie.

Rozmiar grafu (ang. graph size) to liczba krawędzi w grafie.

Wierzchołki grafu przechowują informację, natomiast krawędzie określają sposób poruszania się po grafie: z wierzchołka u można przejść do wierzchołka v tylko wtedy, gdy istnieje ścieżka (ciąg krawędzi), która prowadzi w grafie od wierzchołka u do v.

Grafem zerowym (ang. null graph) jest graf, który posiada wierzchołki, lecz nie posiada żadnych krawędzi:

 

       G = (V, E)
V = { v1,v2,v3,v4,v5 }
E = {  } = Ø

 

W grafie zwykłym mamy wierzchołki oraz krawędzie, które łączą ze sobą pary wierzchołków grafu:

 

       G = (V, E)
V = { v1,v2,v3,v4,v5 }
E = { e1,e2,e3,e4,e5 }

e1 = (v1,v2)
e2 = (v2,v3)
e3 = (v3,v5)
e4 = (v1,v5)
e5 = (v4,v5)

 

Wierzchołek nie połączony krawędzią z żadnym innym wierzchołkiem grafu nazywamy wierzchołkiem izolowanym (ang. isolated vertex):

 

       G = (V, E)
V = { v1,v2,v3,v4,v5,v6 }
E = { e1,e2,e3,e4,e5 }

e1 = (v1,v2)
e2 = (v2,v3)
e3 = (v3,v5)
e4 = (v1,v5)
e5 = (v4,v5)

v6 – wierzchołek izolowany

 

Dane dwa wierzchołki mogą być połączone ze sobą za pomocą więcej niż jednej krawędzi, które nazywamy krawędzią wielokrotną (ang. multi-edge). Również wierzchołek może łączyć się krawędzią z samym sobą. Otrzymujemy wtedy tzw. pętlę (ang. loop). Graf zawierający pętle lub krawędzie wielokrotne nazywamy multigrafem (ang. multigraph).

 

       G = (V, E)
V = { v1,v2,v3,v4,v5 }
E = { e1,e2,e3,e4,e5,e6,e7 }

e1 = (v1,v2)
e2 = (v1,v2)
e3 = (v2,v3)
e4 = (v3,v5)
e5 = (v1,v5)
e6 = (v4,v5)
e7 = (v4,v4)

e1,e2 – krawędź wielokrotna
e7 – pętla

 

Graf nie posiadający pętli oraz krawędzi podwójnych nazywamy grafem prostym (ang. simple graph lub strict graph).

Krawędź, którą można przebywać tylko w określoną stronę, nazywa się krawędzią skierowaną (ang. directed edge). Na rysunku krawędzie skierowane oznaczamy strzałkami. Graf zawierający krawędzie skierowane nazywamy grafem skierowanym (ang. directed graph) lub w skrócie digrafem (ang. digraph). Graf nie posiadający krawędzi skierowanych nazywamy grafem nieskierowanym (ang. not directed graph). W definicji digrafu zbiór krawędzi tworzą uporządkowane pary wierzchołków (u,v), z których u oznacza wierzchołek początkowy krawędzi, a v wierzchołek końcowy. Krawędź nieskierowana może być przedstawiona jako dwie krawędzie skierowane w przeciwnych kierunkach.

 

       G = (V, E)
V = { v1,v2,v3,v4,v5 }
E = { e1,e2,e3,e4,e5,e6 }

e1 = (v1,v2)
e2 = (v2,v1)
e3 = (v2,v3)
e4 = (v3,v5)
e5 = (v5,v1)
e6 = (v5,v4)

 

Zwróć uwagę, że w grafie skierowanym mogą istnieć wierzchołki, pomiędzy którymi nie da się przejść, pomimo istnienia łączących je krawędzi. Oto najprostszy przykład:

 

       G = (V, E)
V = { v1,v2 }
E = { e1 }

e1 = (v1,v2)

 

W grafie tym istnieje droga od wierzchołka v1 do v2, jednakże nie ma drogi powrotnej od v2 do v1, ponieważ łącząca te wierzchołki krawędź może być przebyta tylko w jednym kierunku.

Z krawędziami grafu mogą być związane dodatkowe wartości (np. w świecie rzeczywistym pokonanie drogi z jednego miasta do drugiego może wymagać określonej ilości czasu lub energii). Wartości te nazywamy wagami (ang. weight), a graf posiadający takie krawędzie nazywamy grafem ważonym (ang. weighted graph). Graf ważony posiada zbiór krawędzi zbudowany z uporządkowanych trójek, gdzie dwa pierwsze elementy określają wierzchołki połączone daną krawędzią (w grafie skierowanym wierzchołki te są parą uporządkowaną), a trzeci element określa wagę tej krawędzi.

 

       G = (V, E)
V = { v1,v2,v3,v4,v5 }
E = { e1,e2,e3,e4,e5 }

e1 = (v1,v2,w1)
e2 = (v2,v3,w2)
e3 = (v3,v5,w3)
e4 = (v1,v5,w4)
e5 = (v4,v5,w5)

 

Stopniem wierzchołka (ang. degree) nazywamy liczbę krawędzi, które łączą się z danym wierzchołkiem. Jeśli graf posiada pętle, to liczymy je za 2. W poniższym grafie wierzchołki posiadają następujące stopnie:

 

       deg(v1) = 3
deg(v2) = 3
deg(v3) = 2
deg(v4) = 3
deg(v5) = 3

 

W grafie skierowanym rozróżniamy stopień wchodzący (ang. indegree) – liczba krawędzi wchodzących do wierzchołka oraz stopień wychodzący (ang. outdegree) – liczba krawędzi wychodzących z wierzchołka.

Wierzchołek izolowany posiada zawsze stopień 0.

Ścieżka lub droga (ang. path) jest uporządkowanym ciągiem kolejnych krawędzi, po których należy przejść, aby dotrzeć z wierzchołka startowego (ang. start vertex) do wierzchołka końcowego (ang. end vertex). W grafie może istnieć wiele różnych ścieżek pomiędzy dwoma wybranymi wierzchołkami.

 

       P(v1,v4) = { e1, e2, e7 }

P(v1,v4) = { e1, e5 }

P(v1,v4) = { e4, e6 }

P(v1,v4) = { e4, e3, e7 }

...

 

Ścieżki można również definiować za pomocą ciągu kolejno mijanych wierzchołków (oczywistym jest, iż każde dwa kolejne wierzchołki muszą być połączone krawędzią).

 

       P(v1,v4) = { v1, v2, v3, v4 }

 

Najkrótsza ścieżka (ang. shortest path) to ta, która zawiera najmniej krawędzi/wierzchołków. Długość ścieżki (ang. path length) to liczba zawartych w niej krawędzi/wierzchołków.

Mówimy, że ścieżka jest prosta (ang. strait path lub simple path), jeśli każdą krawędź/wierzchołek przechodzimy tylko jeden raz.

Cykl (ang. cycle) to ścieżka, która rozpoczyna się i kończy w tym samym wierzchołku. Uwaga: nie myl cyklu z pętlą – pętla to pojedyncza krawędź.

 

       C(v1) = { e1, e2, e7, e6, e4 }

C(v1) = { v1, v2, v3, v4, v5, v1 }

 

Cykl nazywamy prostym (ang. simple cycle), jeśli każda jego krawędź/wierzchołek jest przechodzona dokładnie jeden raz. Nie odnosi się to oczywiście do wierzchołka startowego i końcowego, które w cyklu muszą być tym samym wierzchołkiem, innymi słowy ścieżka musi być zamknięta.

Ścieżka prosta zawierająca wszystkie wierzchołki grafu nosi nazwę ścieżki Hamiltona (ang. Hamiltonian path).

Cykl prosty zawierający wszystkie wierzchołki grafu nazywa się cyklem Hamiltona (ang. Hamiltonian cycle).

Ścieżka prosta, która przechodzi przez wszystkie krawędzie grafu nazywa się ścieżką Eulera (ang. Eulerian path).

Cykl Eulera (ang. Eulerian cycle) to cykl prosty, który przechodzi przez wszystkie krawędzie grafu. Zwróć uwagę, że cykl Eulera i cykl Hamiltona to nie to samo! W cyklu Hamiltona ważne jest przejście przez wszystkie wierzchołki dokładnie jeden raz (niektóre krawędzie grafu mogą być w ogóle nie przechodzone). W cyklu Eulera z kolei musimy przejść przez każdą krawędź, zatem niektóre wierzchołki mogą zostać kilkakrotnie odwiedzone, jeśli łączą się z kilkoma krawędziami.

Graf nazywamy acyklicznym (ang. acyclic graph), jeśli nie posiada żadnych cykli.

Graf nazywamy planarnym (ang. planar graph), jeśli da się go narysować na płaszczyźnie tak, aby żadne jego krawędzie się nie przecinały.

 

Graf planarny

      
Graf nieplanarny

 

Jeśli graf jest planarny, to spełnia wzór Eulera (jeśli graf nie spełnia tego wzoru, to na pewno nie jest planarny):

 

|E| ≤ 3 • |V| – 6

gdzie:

    |E| – liczba krawędzi w grafie
    |V| – liczba wierzchołków

 

Graf pełny (ang. complete graph) jest grafem, w którym każda para wierzchołków łączy się krawędzią. Grafy pełne o n wierzchołkach oznacza się symbolem Kn. Graf pełny o n wierzchołkach posiada krawędzi. Poniżej przedstawiamy kilka początkowych grafów pełnych:

K1 K2 K3 K4 K5 K6

Grafy pełne od K5 w górę nie są planarne.

Resztę definicji i pojęć związanych z grafami podamy zgodnie z potrzebami. W następnym rozdziale zajmiemy się podstawowymi sposobami reprezentacji grafów w komputerze.

Do reprezentacji grafów w pamięci komputera wymyślono kilka różnych struktur danych. Każda z nich posiada swoje zalety, lecz również wady. Dlatego należy je rozsądnie dobierać do zadań, w których używamy grafów. Źle dobrana reprezentacja może znacząco wydłużyć czas obliczeń lub rozmiar zajmowanej pamięci. Graf zwykle nie jest strukturą hierarchiczną, jak np. opisane wcześniej drzewa. Jego węzły nie muszą się ze sobą łączyć w określony sposób. Mogą również istnieć grupy węzłów, które nie są w żaden sposób połączone z innymi. Dlatego sposoby reprezentacji drzew niezbyt nadają się do reprezentacji grafów, która powinna zapewniać dostęp do wszystkich wierzchołków bez względu na ich wzajemne połączenia krawędziami. Takie cechy posiadają tablice i macierze. W rozdziale tym omawiamy trzy najczęściej spotykane sposoby przedstawiania grafów: macierz sąsiedztwa (ang. adjacency matrix), macierz incydencji (ang. incidence matrix) oraz listy sąsiedztwa (ang. adjacency lists). Cechą charakterystyczną tych implementacji jest wykorzystanie tablic do przechowywania danych na temat wierzchołków lub łączących je krawędzi. Wykorzystuje się również struktury mieszane, np. tablicę, której elementami są listy.

Wprowadzanie grafu do pamięci komputera

Chcąc realizować algorytmy grafowe, będziemy zmuszeni wprowadzać różne grafy do pamięci komputera. Istnieje bardzo prosty sposób realizacji tego zadania i jest on następujący: 

Na początku podajemy dwie liczby n – ilość wierzchołków oraz m – ilość krawędzi. Następnie wprowadzamy m par liczb a i b, które definiują kolejne krawędzie grafu, gdzie a to wierzchołek startowy, a b wierzchołek końcowy (dla grafu nieskierowanego kolejność tych wierzchołków nie ma znaczenia). Umówmy się dodatkowo, że wierzchołki w grafie posiadają numery od 0 do n-1. Kolejność numeracji wierzchołków nie ma znaczenia. Dla porządku krawędzie również będą numerowane od 0 do m-1. Dzięki tej umowie uprości się tworzenie struktur danych w języku C++, gdzie, jak pamiętamy, indeksy tablic rozpoczynają się od 0.

Przykład:

5 6 
0 1 
1 2 
2 3 
3 0 
1 4 
3 4 
 – 5 wierzchołków i 6 krawędzi 
 – krawędź e0
 – krawędź e1
 – krawędź e2
 – krawędź e3
 – krawędź e4
 – krawędź e5

 

Jeśli krawędzie będą posiadały wagi, to warości tych wag podamy jako trzecią liczbę w definicji krawędzi.

Przykład:

5 6 
0 1 5 
1 2 -3 
2 3 0 
3 0 -1 
1 4 2 
3 4 4 
 – 5 wierzchołków i 6 krawędzi 
 – krawędź e0
 – krawędź e1
 – krawędź e2
 – krawędź e3
 – krawędź e4
 – krawędź e5

 

Jeśli z wierzchołkami grafu zechcemy skojarzyć dane, to po podaniu dwóch pierwszych liczb n i m najpierw przekazujemy do programu n danych dla wierzchołków, a następnie m par (lub trójek) dla poszczególnych krawędzi.

Przykład:

5 6 
5 
3 
1 
6 
8 

0 1 
1 2 
2 3 
3 0 
1 4 
3 4 
 – 5 wierzchołków i 6 krawędzi 
 – dane dla v0
 – dane dla v1
 – dane dla v2
 – dane dla v3
 – dane dla v4

 – krawędź e0
 – krawędź e1
 – krawędź e2
 – krawędź e3
 – krawędź e4
 – krawędź e5

 

Macierz sąsiedztwa

Graf reprezentujemy za pomocą macierzy kwadratowej A o stopniu n, gdzie n oznacza liczbę wierzchołków w grafie. Macierz tą nazywamy macierzą sąsiedztwa (ang. adjacency matrix). Odwzorowuje ona połączenia wierzchołków krawędziami. Wiersze macierzy sąsiedztwa odwzorowują zawsze wierzchołki startowe krawędzi, a kolumny odwzorowują wierzchołki końcowe krawędzi. Komórka A[i,j], która znajduje się w i-tym wierszu i j-tej kolumnie odwzorowuje krawędź łączącą wierzchołek startowy vi z wierzchołkiem końcowym vj. Jeśli A[i,j] ma wartość 1, to dana krawędź istnieje. Jeśli A[i,j] ma wartość 0, to wierzchołek vi nie łączy się krawędzią z wierzchołkiem vj.

 

        

 

Przykład:

 
  0 1 2 3 4
0 0 1 0 0 0
1 0 0 1 0 0
2 0 0 0 1 0
3 1 0 0 0 1
4 0 1 0 0 0

 

Dla grafu nieskierowanego macierz sąsiedztwa A jest symetryczna względem głównej przekątnej, ponieważ jeśli istnieje krawędź od vi do vj (A[i,j] = 1), to również musi istnieć krawędź w kierunku odwrotnym, od vj do vi (A[j,i] = 1).

Przykład:

 
  0 1 2 3 4
0 0 1 0 1 0
1 1 0 1 0 1
2 0 1 0 1 0
3 1 0 1 0 1
4 0 1 0 1 0

 

Interpretacja zawartości macierzy sąsiedztwa jest bardzo prosta. Poszczególne wiersze traktujemy jako wierzchołki grafu. Zatem wiersz 0 odpowiada wierzchołkowi v0, wiersz 1 odpowiada wierzchołkowi v1, itd. Weźmy dla przykładu wiersz nr 3, który odpowiada wierzchołkowi v3:

 

  0 1 2 3 4
3 1 0 1 0 1

 

W kolumnach o numerach 0, 2 i 4 mamy wartości 1. Oznacza to, że wierzchołek v3 jest połączony krawędziami kolejno z wierzchołkami v0, v2 i v4. Wierzchołek v3 jest początkiem tych krawędzi, a wierzchołki  v0, v2 i v4 są ich końcami. Z wierzchołka v3 nie wychodzą żadne krawędzie do wierzchołków v1 i v3. Porównaj to z rysunkiem grafu umieszczonym powyżej.

Podobnie jest dla kolumn. Weźmy na przykład kolumnę nr 1, która odpowiada wierzchołkowi v1:

 

  1
0 1
1 0
2 1
3 0
4 1

 

W kolumnie mamy wartość 1 w wierszach o numerach 0, 2 i 4. Znaczy to, że wierzchołek v1 jest końcem krawędzi wychodzących z wierzchołków v0, v2 i v4. Do wierzchołka v1 nie dochodzą krawędzie z wierzchołków v1 i v3.

 

Aby sprawdzić, czy w grafie dane dwa wierzchołki vi i vj są połączone krawędzią, sprawdzamy, czy komórka A[i,j] zawiera wartość 1. Jeśli tak, to dana krawędź istnieje. Zwróć uwagę, że operację tę można wykonać w czasie stałym, zatem dla macierzy sąsiedztwa sprawdzenie połączenia wierzchołków krawędzią ma klasę złożoności obliczeniowej równą O(1). Wadą jest klasa zajętość pamięci równa O(n2), gdzie n oznacza liczbę wierzchołków w grafie. Z drugiej strony komórki macierzy mogą być pojedynczymi bitami.

 

Z macierzy sąsiedztwa można odczytać wiele pożytecznych informacje. Oto niektóre z nich:

  • Dla grafu nieskierowanego: stopień wierzchołka vi wyznaczamy, zliczając w i-tym wierszu lub i-tej kolumnie liczbę komórek o wartości 1.
  • Dla grafu skierowanego: stopień wychodzący wierzchołka vi wyznaczymy przez zliczenie komórek o wartości 1 w i-tym wierszu, stopień wchodzący wierzchołka vi wyznaczymy przez zliczenie komórek o wartości 1 w i-tej kolumnie.
  • Sąsiedzi wierzchołka vi to te wierzchołki grafu, do których prowadzą krawędzie z vi, a znajdziemy je przeglądając wiersz i-ty.
  • Wierzchołki, dla których vi jest sąsiadem, to te, od których prowadzą krawędzie do vi, a znajdziemy je przeglądając kolumnę i-tą.
  • Wierzchołek vi jest izolowany, jeśli wiersz i-ty i kolumna i-ta zawiera same zera. Dla grafu nieskierowanego wystarczy sprawdzić tylko wiersz lub tylko kolumnę (dlaczego?).
  • Wierzchołek vi posiada pętlę, jeśli komórka A[i,i] ma wartość 1 (dlaczego?).
  • W grafie skierowanym wierzchołki vi i vj są połączone krawędzią dwukierunkową, jeśli jednocześnie komórki A[i,j] oraz A[j,i] mają wartość 1 (dlaczego?).

Dane do ćwiczenia

           6 8
0 1
1 2
2 2
1 3
3 1
2 4
4 0
4 3
  1. Napisz program, który dla danego grafu skierowanego wyznaczy dla każdego wierzchołka wszystkich jego sąsiadów.
  2. Napisz program, który dla danego grafu skierowanego wyznaczy dla każdego wierzchołka wszystkie wierzchołki, dla których jest on sąsiadem..
  3. Napisz program, który dla danego grafu nieskierowanego wyznaczy stopnie wszystkich wierzchołków. Uważaj na pętle!
  4. Napisz program, który dla danego grafu skierowanego wyznaczy stopnie wychodzące i wchodzące wszystkich wierzchołków.
  5. Napisz program, który dla danego grafu skierowanego wyznaczy wszystkie pętle, krawędzie dwukierunkowe oraz wierzchołki izolowane.

Listy sąsiedztwa

Do reprezentacji grafu wykorzystujemy tablicę n elementową A, gdzie n oznacza liczbę wierzchołków. Każdy element tej tablicy jest listą. Lista reprezentuje wierzchołek startowy. Na liście są przechowywane numery wierzchołków końcowych, czyli sąsiadów wierzchołka startowego, z którymi jest on połączony krawędzią. Tablica ta nosi nazwę list sąsiedztwa (ang. adjacency lists).

Przykład:

 
0 1  
1 2  
2 3  
3 0 4
4 1  

 

W przypadku grafu nieskierowanego listy są dłuższe, ponieważ muszą odzwierciedlać krawędzie biegnące w obu kierunkach.

Przykład:

 
0 1 3  
1 0 4 2
2 1 3  
3 0 2 4
4 1 3  

 

Listy sąsiedztwa są efektywnym pamięciowo sposobem reprezentacji grafu w pamięci komputera, ponieważ zajmują pamięć rzędu O(m), gdzie m oznacza liczbę krawędzi grafu. Listy sąsiedztwa pozwalają w prosty sposób reprezentować pętle oraz krawędzie wielokrotne, co sprawia, że są bardzo chętnie stosowane w algorytmach grafowych.

Oto kilka podstawowych operacji na listach sąsiedztwa:

  • Dla grafu nieskierowanego: stopień wierzchołka vi jest równy liczbie elementów na liście A[i].
  • Dla grafu skierowanego: stopień wychodzący wierzchołka vi jest równy liczbie elementów na liście A[i], stopień wchodzący wierzchołka vi jest równy liczbie elementów o wartości i we wszystkich listach sąsiedztwa..
  • Sąsiedzi wierzchołka vi są określeni przez kolejne elementy listy A[i]..
  • Wierzchołki, dla których vi jest sąsiadem, znajdziemy szukając na listach elementu o wartości i.
  • Wierzchołek vi jest izolowany, jeśli lista A[i] jest pusta.
  • Wierzchołek vi posiada pętlę, jeśli na liście A[i] znajduje się element o wartości i.
  • W grafie skierowanym wierzchołki vi i vj są połączone krawędzią dwukierunkową, jeśli lista A[i] zawiera element o wartości j, a lista A[j] zawiera element o wartości i.

Dane do ćwiczenia

           6 8
0 1
1 2
2 2
1 3
3 1
2 4
4 0
4 3
  1. Napisz program, który dla danego grafu skierowanego wyznaczy dla każdego wierzchołka wszystkie wierzchołki, dla których jest on sąsiadem..
  2. Napisz program, który dla danego grafu nieskierowanego wyznaczy stopnie wszystkich wierzchołków. Uważaj na pętle!
  3. Napisz program, który dla danego grafu skierowanego wyznaczy stopnie wychodzące i wchodzące wszystkich wierzchołków.
  4. Napisz program, który dla danego grafu skierowanego wyznaczy wszystkie pętle, krawędzie dwukierunkowe oraz wierzchołki izolowane.


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.