Reprezentacje grafów

Graf to struktura składająca się z wierzchołków (zbiór V) i krawędzi (zbiór E)
W przypadku grafów skierowanych krawędzie nazywane są łukami
Reprezentacje maszynowe grafu:
- Macierz sąsiedztwa
  - Wiersze i kolumny reprezentują wierzchołki
  - Jeżeli istnieje łuk między i-tym i j-tym wierzchołkiem, to G[i][j] = 1
  - Jeżeli istnieje krawędź między i-tym i j-tym wierzchołkiem, to G[i][j] = G[j][i] = 1
- Macierz incydencji:
  - Wiersze reprezentują wierzchołki, kolumny reprezentują krawędzie
  - k-ty łuk pomiędzy i-tym i j-tym wierzchołkiem oznaczony jest przez G[i][k] = 1 i G[j][k] = -1
  - k-ta krawędź pomiędzy i-tym i j-tym wierzchołkiem oznaczona jest przez G[i][k] = G[j][k] = 1
- Lista krawędzi:
  - Lista par w formacie (i, j) dla każdego połączenia między i-tym a j-tym wierzchołkiem
  - W przypadku grafów nieskierowanych wystarczy podawać tylko takie pary (i, j), dla których i < j
- Listy incydencji/sąsiedztwa:
  - Dotyczy tylko grafów nieskierowanych
  - Dla każdego wierzchołka i utrzymywana jest osobna lista z indeksami wierzchołków połączonych z i krawędzią
- Listy następników i lista poprzedników:
  - Dotyczy tylko grafów skierowanych
  - Dla każdego wierzchołka i utrzymywana jest lista z indeksami następników i oraz druga lista z indeksami poprzedników i
- Macierz grafu:
  - Macierz grafu ma rozmiar jak macierz sąsiedztwa + 4 dodatkowe kolumny
  - Wartości w głównej części macierzy można odczytywać niczym listy następników następników, poprzedników lub listę wierzchołków niepołączonych krawędzią
  - Wartości w dodatkowych kolumnach wskazują pierwsze wierzchołki z tych list

Złożoność pamięciowa reprezentacji maszynowych grafu:

Nazwa	Rozmiar	Graf nieskierowany	Graf skierowany
Macierz sąsiedztwa	\|V\| \times \|V\|	✓	✓
Macierz incydencji	\|V\| \times \|E\|	✓	✓
Lista krawędzi	\|E\|	✓	✓
Lista incydencji/sąsiedztwa	\|V\| + \|E\|	✓	✗
Lista następników	\|V\| + \|E\|	✗	✓
Lista poprzedników	\|V\| + \|E\|	✗	✓
Macierz grafu	\|V\| \times (\|V\| + 4)	✗	✓

Macierz sąsiedztwa: przykład

M = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \end{bmatrix}

Lista sąsiedztwa: przykład

0 → 1
1 → 0, 2, 3, 5, 7
2 → 1, 3, 4
3 → 1, 2, 4
4 → 2, 3, 5
5 → 1, 4, 6
6 → 5, 7
7 → 1, 6

Przechodzenie grafu

Istnieją dwa podejścia do przechodzenia całej struktury grafu:
- DFS (depth first search): przeszukiwanie w głąb, napotykając nieodwiedzony wierzchołek rekurencyjnie odwiedzamy jego jeszcze nieodwiedzonych następników
- BFS (breadth first search): przeszukiwanie wszerz, napotykając nieodwiedzony wierzchołek zapisujemy w kolejce jego następników i następnie odwiedzamy kolejny wierzchołek według kolejki

DFS

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{Dfs}{$ G $}
    \STATE {$ colors \gets \emptyset $} \COMMENT { tablica długości $|G.V|$ }
    \FORALL {$ u \in G.V $}
        \STATE {$ colors[u] \gets \text{WHITE} $}
    \ENDFOR
    \FORALL {$ u \in G.V $}
        \IF {$ colors[u] = \text{WHITE} $}
            \STATE \CALL{DfsVisit}{$ G, u, colors $}
        \ENDIF
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{DfsVisit}{$ G, u, colors $}
    \STATE {$ colors[u] \gets \text{GRAY} $}
    \FORALL {$ v \in G.adjacent[u] $} \COMMENT { $v$ takie, że istnieje krawędź $(u,v)$ }
        \IF {$ colors[v] = \text{WHITE} $}
            \STATE \CALL{DfsVisit}{$ G, v, colors $}
        \ENDIF
    \ENDFOR
    \STATE {$ colors[u] \gets \text{BLACK} $}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

BFS

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{Bfs}{$ G, s $}
    \STATE {$ colors \gets \emptyset $} \COMMENT { tablica długości $|G.V|$ }
    \FORALL {$ u \in G.V \setminus \{s\} $}
        \STATE {$ colors[u] \gets \text{WHITE} $}
    \ENDFOR
    \STATE {$ colors[s] \gets \text{GRAY} $}
    \STATE {$ Q \gets \emptyset $} \COMMENT { kolejka FIFO }
    \STATE \CALL{Enqueue}{$ Q, s $}
    \WHILE {$ Q \neq \emptyset $}
        \STATE {$ u \gets $ \CALL{Dequeue}{$ Q $}}
        \FORALL {$ v \in G.adjacent[u] $} \COMMENT { $v$ takie, że istnieje krawędź $(u,v)$ }
            \IF {$ colors[v] = \text{WHITE} $}
                \STATE {$ colors[v] \gets \text{GRAY} $}
                \STATE \CALL{Enqueue}{$ Q, v $}
            \ENDIF
        \ENDFOR
    \STATE {$ colors[u] \gets \text{BLACK} $}
    \ENDWHILE
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Sortowanie topologiczne

Sortowanie topologiczne skierowanego grafu polega na liniowym uporządkowaniu wierzchołków w taki sposób, że jeśli istnieje łuk (u, v) to w porządku topologicznym u znajdzie się przed v
Sortowanie topologiczne możemy przeprowadzić tylko dla skierowanych grafów acyklicznych

Algorytm Kahna sortowania topologicznego:

Powtarzaj dopóki graf zawiera wierzchołki
1. Znajdź w grafie wierzchołek niezależny u tj. taki, który ma zerowy stopień wejściowy
2. Dodaj wierzchołek do rozwiązania i usuń go z grafu

4, 3

4, 3, 2

4, 3, 2, 1

4, 3, 2, 1, 5

4, 3, 2, 1, 5, 6

4, 3, 2, 1, 5, 6, 7

4, 3, 2, 1, 5, 6, 7, 8

Algorytm sortowania topologicznego oparty o DFS

Wykonaj przegląd grafu przy pomocy DFS, a w momencie kolorowania wierzchołka na czarno, umieść jego indeks na stosie
Wartości pobierane ze stosu ułożone będą zgodnie z porządkiem topologicznym

Stos:

Stos: 1

Stos: 1, 2

Stos: 1, 2, 8

Stos: 1, 2, 8, 3

Stos: 1, 2, 8, 3, 7, 6, 5, 4

Cykle w grafie

Ścieżka w grafie od u do v to sekwencja wierzchołków u, \ldots, v, taka że kolejne pary w sekwencji połączone są krawędzią
- Zielona ścieżka: 8, 1, 6, 7
- Niebieska ścieżka: 8, 2, 10, 9, 7
Cykl w grafie to ścieżka z takim samym pierwszym i ostatnim wierzchołkiem
- Pomarańczowy cykl: 5, 6, 3, 10, 5
Cykl Eulera to taki cykl w grafie, który przechodzi przez każdą krawędź dokładnie raz:
- Warunkiem koniecznym i wystarczającym by spójny graf nieskierowany posiadał cykl Eulera jest parzystość stopni wszystkich wierzchołków.
  
  2, 5, 6, 8, 4, 1, 7, 8, 3, 1, 6, 2
Cykl Hamiltona to taki cykl w grafie, który przechodzi przez każdy wierzchołek dokładnie raz

3, 7, 5, 1, 6, 4, 2, 3

Algorytm sprawdzania mostu w grafie

Most w spójnym grafie to taka krawędź, której usunięcie spowoduje utratę spójności grafu:

(3,4)
Wejście: graf nieskierowany G, krawędź (u,v)
Wyjście: TAK, jeśli krawędź (u,v) jest mostem grafu, NIE w przeciwnym razie

Uruchom DFS dla grafu G rozpoczynając w wierzchołku u, a następnie wyznacz liczbę odwiedzonych wierzchołków
Usuń krawędź (u,v), i ponownie uruchom DFS rozpoczynając z wierzchołka u; po wyznaczeniu liczby odwiedzonych wierzchołków przywróć krawędź (u,v)
Zwróć TAK jeśli liczba odwiedzonych wierzchołków w kroku 1 jest różna od wyniku w kroku 2, w przeciwnym razie zwróć NIE

Algorytm Fleury’ego znajdowania cyklu Eulera

Wejście: spójny graf nieskierowany G
Wyjście: cykl Eulera

Zacznij w dowolnym wierzchołku u (ponieważ wygenerowany graf ma wszystkie wierzchołki o parzystym stopniu)
Powtarzaj dopóki są krawędzie w grafie:
1. Dodaj u do rozwiązania
2. Jeżeli istnieje krawędź (u,v), która nie jest mostem, to wybierz ją do kolejnego kroku, w przeciwnym razie wybierz krawędź (u,v), która jest mostem
3. Usuń wybraną krawędź (u,v)
4. Przypisz u ← v

Rozwiązanie: 0

Rozwiązanie: 0, 1

Rozwiązanie: 0, 1, 2

Rozwiązanie: 0, 1, 2, 4

Rozwiązanie: 0, 1, 2, 4, 5

Rozwiązanie: 0, 1, 2, 4, 5, 2

Rozwiązanie: 0, 1, 2, 4, 5, 2, 3

Algorytm Hierholzera znajdowania cyklu Eulera

Wejście: spójny graf nieskierowany G
Wyjście: cykl Eulera

Utwórz stos, czyli strukturę danych typu LIFO (Last-In-First-Out)
Dodaj na stos dowolny wierzchołek u (ponieważ wygenerowany graf ma wszystkie wierzchołki o parzystym stopniu)
Dopóki stos nie jest pusty:
1. Niech u będzie wierzchołkiem ze szczytu stosu (bez zdejmowania wartości ze stosu)
2. Jeżeli istnieje krawędź (u,v) to usuń ją z grafu, odłóż v na stos, przypisz u ← v i powtarzaj krok 3.2
3. Zdejmij wartość ze szczytu stosu i dodaj ją do rozwiązania

Stos: 0, 1

Rozwiązanie:

Stos: 0, 1, 2

Rozwiązanie:

Stos: 0, 1, 2, 3

Rozwiązanie:

Stos: 0, 1, 2, 3, 0

Rozwiązanie:

Stos: 0, 1, 2, 3

Rozwiązanie: 0

Stos: 0, 1, 2

Rozwiązanie: 0, 3

Stos: 0, 1, 2, 4

Rozwiązanie: 0, 3

Stos: 0, 1, 2, 4, 5

Rozwiązanie: 0, 3

Stos: 0, 1, 2, 4, 5, 2

Rozwiązanie: 0, 3

Stos: 0, 1, 2, 4, 5

Rozwiązanie: 0, 3, 2

…

Stos:

Rozwiązanie: 0, 3, 2, 5, 4, 2, 1, 0

Algorytm z powracaniem znajdowania cyklu Hamiltona

Wejście: spójny graf nieskierowany G(V,E), indeks n oraz ścieżka path zawierająca początkowe n wierzchołków
Wyjście: TAK, jeśli istnieje cykl Hamiltona z początkiem w ścieżce path, NIE w przeciwnym razie. Jeśli odpowiedź brzmi TAK to path zostanie dopełnione indeksami wierzchołków

Niech u ← path[n-1] (ostatni wierzchołek na ścieżce)
Jeżeli n = |V|
1. Niech v ← path[0]. Zwróć TAK jeżeli istnieje krawędź (u,v), w przeciwnym razie zwróć NIE
Znajdź krawędź (u,v), taką że v \notin path
1. Jeżeli taka krawędź istnieje, dodaj v do path i sprawdź wynik rekurencyjnego wywołania tego algorytmu dla n+1
2. Jeżeli odpowiedź brzmi TAK to również zwróć wartość TAK. W przeciwnym razie wróć do kroku 3 i wybierz inną krawędź
Zwróć NIE

n = 1 path = [0]

n = 2 path = [0, 1]

n = 3 path = [0, 1, 2]

n = 4 path = [0, 1, 2, 3]

n = 5 path = [0, 1, 2, 3, 5]

n = 6 path = [0, 1, 2, 3, 5, 4]

Wynik: NIE

n = 5 path = [0, 1, 2, 3, 5]

Wynik: NIE

n = 4 path = [0, 1, 2, 3]

Wynik: NIE

n = 3 path = [0, 1, 2]

n = 4 path = [0, 1, 2, 4]

n = 5 path = [0, 1, 2, 4, 5]

n = 6 path = [0, 1, 2, 4, 5, 3]

Wynik: TAK

Generowanie losowych grafów

Podczas generowania losowych grafów korzysta się z parametru o nazwie gęstość, który możemy oznaczyć przez b
Nieskierowany, pełny graf o n wierzchołkach ma \frac{n(n-1)}{2} krawędzi
Skierowany, pełny graf o n wierzchołkach ma n^2 łuków
Gęstość określa jaka część wszystkich możliwych krawędzi/łuków ma się znaleźć w grafie
Przykłady:
- n=10, b=0.1 → krawędzi będzie \lfloor 0.1 \cdot \frac{10 \cdot 9}{2} \rfloor = 4
- n=10, b=0.9 → krawędzi będzie \lfloor 0.9 \cdot \frac{10 \cdot 9}{2} \rfloor = 40
- n=50, b=0.5 → krawędzi będzie \lfloor 0.5 \cdot \frac{50 \cdot 49}{2} \rfloor = 612
Na potrzeby zadania chcemy, aby losowy graf spełniał następujące cechy:
- Brak pętli własnych: nie dopuszczamy krawędzi (v_i, v_i)
- Brak wielokrotnych krawędzi: jeżeli istnieje krawędź (v_i, v_j) to istnieje ona tylko raz

Generowanie losowego grafu skierowanego

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{RandomDirectedGraph}{$ n, b $}
    \STATE {$ G \gets \emptyset $} \COMMENT { stwórz pusty graf z $n$ wierzchołkami }
    \STATE {$ m \gets b \cdot n^2 $} \COMMENT { liczba łuków w grafie }
    \FOR {$ i \gets 0 $ \TO $ m $}
        \REPEAT
            \STATE {$ u \gets $} \CALL{Random}{$ 0, n-1 $}
            \STATE {$ v \gets $} \CALL{Random}{$ 0, n-1 $}
        \UNTIL {$ u \neq v $ \AND $ (u, v) \notin G.E $}
        \STATE {$ G.E \gets G.E \cup \{ (u, v) \}  $}
    \ENDFOR
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Uwaga! Powyższy pseudokod najlepiej jest zaimplementować dla macierzy sąsiedztwa
Sprawdzenie warunku z linii 8 tj. czy (u, v) \in G.E odbywa się dla macierzy sąsiedztwa w czasie stałym
W przypadku wykonywania eksperymentów na listach następników, sugeruję tworzyć losowy graf w postaci macierzy sąsiedztwa, a następnie na jej podstawie budować listy następników

Generowanie losowego i acyklicznego grafu skierowanego (DAG)

Procedura jest identyczna jak poprzednio, ale w warunku z linii 8 z RandomDirectedGraph należy dodatkowo odrzucać łuki (u,v) gdy u > v

Generowanie losowego, nieskierowanego grafu z cyklem Eulera

Należy najpierw wygenerować losowy cykl Eulera:
- Stwórz tablicę T o rozmiarze m = \lfloor b \cdot \frac{n \cdot (n - 1)}{2} \rfloor elementów
- Wypełnij ją rosnąco modulo n
- Przetasuj tablicę
Następnie należy stworzyć graf na jego podstawie:
- Stwórz graf
- Dodaj do niego krawędzie T[i-1][i] dla 1 < i < m
- Dodaj do niego krawędź T[0][m-1]

Generowanie losowego, skierowanego grafu z cyklem Hamiltona

Należy najpierw wygenerować losowy cykl Hamiltona:
- Stwórz tablicę T o rozmiarze n
- Wypełnij ją rosnąco
- Przetasuj tablicę
Następnie należy stworzyć graf na jego podstawie (analogicznie jak poprzednio)
Na koniec należy dopełnić graf losowymi łukami jak w RandomDirectedGraph by ich łączna liczba wynosiła b \cdot n^2

Generowanie losowego, skierowanego grafu bez cyklu Hamiltona

Należy najpierw stworzyć graf z cyklem Hamiltona
Następnie znaleźć wierzchołek o minimalnym stopniu wyjściowym (minimalnej liczbie łuków wychodzących z niego)
Należy usunąć wszystkie łuki wychodzące z tego wierzchołka

Zadanie

Ocena 3.0

Zaimplementuj generowanie w pełni losowego, skierowanego grafu
Zaimplementuj algorytm DFS dla macierzy sąsiedztwa i dla list następników
Wykonaj eksperymenty obliczeniowe dla liczby wierzchołków 100, 200, …, 1000 i dla gęstości 1/8, 2/8, …, 7/8
Przedstaw wyniki w sprawozdaniu (po jednym wykresie na reprezentację grafu) i porównaj zmierzone czasy działania

Ocena 3.5

Przygotuj implementację i eksperymenty obliczeniowe jak poprzednio, ale również dla algorytmu BFS

Ocena 4.0

Zaimplementuj generowanie losowego, skierowanego, acyklicznego grafu
Zaimplementuj obie metody sortowania topologicznego
Wykonaj eksperymenty obliczeniowe i porównaj ich czasy działania

Ocena 4.5

Zaimplementuj generowanie losowego grafu z cyklem Eulera
Zaimplementuj oba algorytmy znajdowania cyklu Eulera
Porównaj ich czasy działania (n=300, b zmienne 2/16, 3/16, …, 14/16)

Ocena 5.0

Zaimplementuj generowanie losowego grafu z cyklem Hamiltona lub bez niego
Zaimplementuj algorytm znajdowania cyklu Hamiltona
Wykonaj eksperymenty obliczeniowe:
- Gęstość stała b=0.5
- Dla instancji z cyklem Hamiltona, liczba wierzchołków zmienna 100, 200, …, 1000
- Dla instancji bez cyklu Hamiltona, liczba wierzchołków zmienna 8, 9, …, 18