drogi i cykle w grafach 2
Drogi i cykle w grafach
Droga prosta – gdy wszystkie jej krawędzie są różne.
Cykl – droga zamknięta, w której wszystkie wierzchołki oprócz Graf – zbiór wierzchołków V i krawędzi E.
pierwszego i ostatniego są różne.
Krawędź - para wierzchołków.
Graf nie zawierający cykli nazywamy acyklicznym.
Krawędź może mieć wagę (graf z wagami).
Graf jest spójny gdy między każdą parę wierzchołków można Graf nieskierowany - gdy pary wierzchołków krawędzi są poprowadzić drogę. Składowa spójności – maksymalny spójny nieuporządkowane.
podgraf.
Kolejność wierzchołków krawędzi istotna - graf skierowany Własność:
Każda droga zamknięta o różnych wierzchołkach v
(digraf).
0, v1, ..., vk-1 i
co najmniej trzech krawędziach jest cyklem.
Stopień wierzchołka v - liczba krawędzi wychodzących z tego Własność:
Droga ma wszystkie wierzchołki różne wtedy i tylko wtedy, gdy wierzchołka. Oznaczać przez d(v).
jest prosta i acykliczna.
Ponadto
Własność:
Jeżeli w grafie istnieje droga od wierzchołka u do v
|E| - liczba krawędzi grafu
(u ≠ v) , to istnieje także droga prosta acykliczna od u do v.
|V| - liczba wierzchołków grafu.
Drogi i cykle Eulera
Własność: Suma stopni wierzchołków w grafie jest równa podwojonej liczbie krawędzi grafu.
Droga Eulera - droga która przechodzi dokładnie jeden raz
∑d(v) = 2| E |
przez każdą krawędź grafu.
v V
∈
Cykl Eulera – droga zamknięta w której każda krawędź grafu Wniosek: liczba wierzchołków o nieparzystych stopniach jest występuje dokładnie jeden raz.
parzysta.
Cykl Eulera jest związany z mostami w Królewcu (XVIII w) –
czy można przejść dokładnie raz przez mosty i wrócić do punktu Drogi i cykle
wyjścia?
ląd
Droga (ścieżka) – ciąg wierzchołków v0, v1, ..., vk taki, ze każde dwa kolejne v
rzeka
wyspa
wyspa
i, vi+1 są połączone krawędzią.
Długością drogi dla grafów bez wag jest liczba tych krawędzi, a ląd
graf
dla grafów z wagami suma wag tych krawędzi.
Rys. Mosty królewieckie i odpowiadający im graf
Droga jest zamknięta, gdy v0 = vk.
drogi i cykle w grafach 4
Jak wykazał Euler (1736), dla mostów królewieckich
rozwiązanie takie nie istnieje.
Powyższy algorytm jest niezbyt wygodny , ponieważ na każdym kroku wymaga sprawdzania czy graf pozostaje spójny.
Twierdzenie:
Graf spójny posiada:
- cykl Eulera wtedy i tylko wtedy, gdy każdy jego
Cykl Eulera – algorytm I (z badaniem spójności grafu}
wierzchołek jest parzystego stopnia
1
3
6
1
3
6
1
3
6
- drogę Eulera – jeżeli co najwyżej dwa jego wierzchołki są stopnia nieparzystego
5
8
2
5
8
2
5
8
Uzasadnienie: Droga Eulera przechodzi dokładnie raz przez 2
każdą krawędź. Przechodząc przez wierzchołek możemy usunąć krawędź którą przyszliśmy i krawędź którą wyszliśmy. Dlatego z 4
7
9
4
7
9
4
7
9
każdego wierzchołka musi wychodzić parzysta liczba krawędzi,
{1 2}
{1 2 3}
{1 2 3 5}
z wyjątkiem co najwyżej początku i końca drogi. Jeżeli jednak początek drogi pokrywa się z jej końcem, to także i ten wierzchołek musi być stopnia parzystego (wychodzimy i 1
3
6
1
3
6
wchodzimy).
niedopuszczalne
Algorytm wyszukiwania cyklu Eulera:
2
5
8
2
5
8
1. Wybieramy wierzchołek początkowy v0 (dowolnie)
4
7
9
2. Powtarzamy aż do wyczerpania krawędzi
4
7
9
{1 2 3 5 8}
a) jeżeli z bieżącego wierzchołka nie odchodzi żadna krawędź, to koniec
b) jeżeli z bieżącego wierzchołka v odchodzi tylko jedna 1
3
6
1
3
6
Dalej nie ma
krawędź, to przechodzimy wzdłuż tej krawędzi do
wyboru:
następnego wierzchołka, usuwamy tę krawędź i
Cykl Eulera
5
8
wierzchołek v z grafu
2
5
8
2
{1 2 3 5 8 7 4} ∪
{2 5 7 9 8 6 3 1}
c) jeżeli z v odchodzi więcej niż jedna krawędź, wtedy wybieramy taką, by po jej usunięciu graf pozostał spójny; 4
7
9
4
7
9
wzdłuż tej krawędzi przechodzimy do następnego
{1 2 3 5 8 7}
{1 2 3 5 8 7 4 }
wierzchołka i usuwamy tę krawędź z grafu.
drogi i cykle w grafach 6
Drugi algorytm wyznaczania cyklu Eulera
Droga Hamiltona
Założenie:
Graf spójny, wszystkie wierzchołki są stopnia parzystego Droga Hamiltona jest to droga, która przechodzi dokładnie Algorytm II (z wykorzystaniem stosu)
raz przez każdy wierzchołek grafu. Cykl Hamiltona – zamknięta 1. Wybieramy wierzchołek początkowy v; stos:= {v} CE = ∅
(cykl Eulera pusty)
droga Hamiltona.
2. dopóki stos ≠ ∅ wykonuj:
2
a) v:= front (stos)
2
2
1
b) jeżeli z v wychodzą nie odwiedzone krawędzie, to
1
1
wybieramy jedną z nich, przechodzimy wzdłuż niej do
5
5
5
4
4
sąsiedniego wierzchołka w. Krawędź (v, w) zaznaczamy 4
jako odwiedzoną oraz
3
6
3
3
6
stos = stos + {w}
6
c) jeżeli wszystkie krawedzie wychodzące z v już były odwiedzone, to usuwamy v ze stosu, dokładając do cyklu Rys. Cykle Hamiltona w grafie
Eulera CE. Przechodzimy do następnego wierzchołka na stosie.
Grafem pełnym - graf, w którym każde dwa wierzchołki są Przykład:
połączone krawędzia.
Graf 9 wierzchołków – start 1 – algorytm II (ze stosem) Graf pełny o n wierzchołkach jest oznaczany prze Kn.
1
3
1
3
6
1
3
6
6
Własność: Każdy graf pełny o n ≥ 3 wierzchołkach ma cykl Hamiltona.
2
5
8
Nie jest znane żadne kryterium na istnienie cyklu Hamiltona, ani 2
5
8
2
5
8
tez żaden algorytm działający w czasie wielomianowym.
Algorytm naiwny – sprawdzanie wszystkich permutacji
4
7
9
4
7
9
4
7
9
wierzchołków (n! permutacji dla n wierzchołków).
1
3
6
Wynik – cykl Eulera:
Algorytm szukania drogi Hamiltona (algorytm z nawrotami).
{1 3 6 8 9 7 8 5 7 4 2 5 3 2 1}
Zasada; idziemy pierwszą możliwą ścieżką tak daleko jak to 2
5
8
możliwe, odkładając kolejne wierzchołki na stos. Gdy nie ma już dokąd iść, zdejmujemy bieżący wierzchołek ze stosu i 4
7
9
próbujemy iść inną drogą, od następnego na stosie.
Algorytm z nawrotami.
1. wybieramy wierzchołek początkowy v; stos = {v}
2. Powtarzamy do skutku
a) jeżeli u = front (stos), to wybieramy w taki ,że
- w połączony z u krawędzią
- w nie należy do stosu
- w spełnia dodatkowe kryterium wyboru – np. ma najniższy numer ze spełniających w/w warunki
b) jeżeli istnieje wierzchołek spełniający warunki z p. a, to stos
= stos +{w}. Sprawdzamy, czy wierzchołki na stosie tworzą drogę Hamiltona. Jeżeli tworzą, to koniec.
c) jeżeli wierzchołek w o własnościach podanych w p. a nie istnieje, to stos = stos – {u} (u = front(stos)) Przykład:
2
3
1
7
5
4
6
Start z 4
droga 4 1 2 3 6 5 dalej nie ma dokąd bo 1 zamyka a 7 nie było 5 ze stosu
droga 4 1 2 3 6
dokładamy 7
droga 4 1 2 3 6 7
znowu nie ma dokąd ( 3 i 1 były, 5 brak)
7 ze stosu
droga 4 1 2 3 6
6 ze stosu (obie drogi, do 5 i 7 wycofane)
droga 4 1 2 3
dokładamy 7
(druga z możliwych, do 6, już była )
droga 4 1 2 3 7 dalej przez 6, 5 – razem 7 wierzchołków droga 4 1 2 3 7 6 5 droga Hamiltona, wszystkie wierzchołki (ale z tej drogi nie można utworzyć
cyklu Hamiltona)