Algorytmy z powracaniem

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

Generowanie grafu z cyklem Hamiltona i Eulera

Wejście: liczba wierzchołków n oraz gęstość grafu b
Wyjście: nieskierowany graf spójny z n wierzchołkami i \frac{bn(n-1)}{2} (± 2) krawędziami zawierający cykl Hamiltona i cykl Eulera jednocześnie

Stwórz wierzchołki
Dodaj n krawędzi by utworzyć losowy cykl Hamiltona (np. 1, 6, 3, 2, 5, 8, 7, 4, 1)
Dopóki liczba krawędzi w grafie jest mniejsza niż oczekiwana, wykonuj krok 4
Znajdź losowo trzy wierzchołki u, v i w, takie że nie istnieje krawędź (u,v), (u,w) ani (v,w) i dodaj takie krawędzie (np. u=2, v=7, w=6)

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

Zadanie

Stwórz implementację następujących algorytmów:
- Hierholzera (ocena 3.0)
- Znajdowania cyklu Hamiltona (ocena 4.0)
- Fleury’ego (ocena 5.0)
Wykonaj eksperymenty obliczeniowe:
- Dla cyklu Eulera, niech liczba wierzchołków będzie stała (300), a zmieniać będzie się gęstość grafu: \frac{2}{16}, \frac{3}{16}, ..., \frac{14}{16}
- Dla cyklu Hamiltona, niech gęstość grafu będzie stała (0.5), a zmieniać będzie się liczba wierzchołków:
  - W wariancie na 4.0, gdzie cykl Hamiltona istnieje: 100, 200, ..., 1000
  - W wariancie na 4.5, gdzie cykl Hamiltona nie istnieje: 8, 9, ..., 18
- W wariancie na 4.5, należy wymusić żeby cykl Hamiltona nie istniał:
  - Po wygenerowaniu grafu, znajdź wierzchołek o minimalnym stopniu (= minimalnej liczbie krawędzi z innymi wierzchołkami)
  - Usuń wszystkie krawędzie wychodzące z tego wierzchołka
  - Wówczas usuniesz minimalną wymaganą liczbę krawędzi by jeden z wierzchołków był niepołączony z resztą grafu (a w konsekwencji cykl Hamiltona na pewno nie będzie istniał)
Przedstaw 4 wykresy:
- Czas działania algorytmu Hierholzera w zależności od liczby krawędzi (ocena 3.0)
- Czas znajdowania cyklu Hamiltona w zależności od liczby wierzchołków (ocena 4.0)
- Czas na stwierdzenie braku cyklu Hamiltona w zależności od liczby wierzchołków (ocena 4.5)
- Czas działania algorytmu Fleury’ego w zależności od liczby krawędzi (ocena 5.0)