1 Algorytmy i struktury danychReprezentacja grafu Wybrane problemy

2 Graf Pętle Wielokrotne krawędzie Wagi 10 11 7 Prosty Skierowany

3 Reprezentacja grafu Macierz sąsiedztwa Lista sąsiedztwaB D A B C D Macierz sąsiedztwa A B C D 1 C Lista sąsiedztwa A B C D B A C D B D B C Jeśli macierz jest symetryczna (graf nieskierowany), można przechowywać tylko jedną połówkę.

4 Reprezentacja grafu Macierz incydencji Lista incydencji m p m n o p n1 o Lista incydencji m n o p p n m o p p n m n o

5 Reprezentacja wag Macierz sąsiedztwa Lista incydencji A 2 7 B D A B C3 A B C D 5 7 2 3 5 C 2 Lista incydencji A B C D A,2 B,3 D,2 B,7 C,5

6 Składowe spójnosci DFS

7 Minimalne drzewo spinające1 3 6 2 4 8 5 Zastosowania – np. budowa sieci dróg

8 Minimalne drzewo spinająceAlg Kruskala: Wybieraj kolejno krawędzie o minimalnej wadze tak, by nie tworzyły cyklu. Pot. problem: stwierdzanie obecności cyklu. Alg Prima-Dijkstry: Drzewo = krawędź o minimalnej wadze; Spośród krawędzi incydentnych z aktualnym drzewem wybierz krawędź o najmniejszej wadze; Dodaj krawędź do drzewa. Pot. problem: grafy niespójne.

9 Minimalna droga 1 3 6 7 4 9 2 Zastosowania: - wybór najkrótszej (najszybszej) trasy przejazdu; - wybór najtańszego procesu technologicznego.

10 Alg. Dijkstry Z.: Wagi są nieujemneDla sąsiadów wierzchołka startowego S ustaw odległość di równą wadze krawędzi e(s,i), dla każdego wierzchołka innego niż S inicjujemy di =  Spośród nieodwiedzonych wierzchołków wybierz wierzchołek i o mininimalnej ogległości di Dla sąsiadów j wybranego wierzchołka aktualizuj odległość jako min{ dj, di+e(j,w) } Jeżeli są nieosiągnięty został wierzchołek końcowy K (lub są nieodwiedzone wierzchołki gdy nie zadajemy K) przejdź do punktu 2

11 Droga, cykl Eulera Marszruta – otwarta (zamknięta), zawierająca wszystkie krawędzie w grafie Zastosowania: Problem chińskiego listonosza; Rysowanie/wycinanie figur przy pomocy plotera.

12 Minimalne drzewo spinająceAlgorytm Dijkstry: Dla wszystkich wierzchołków ustal s=¥; Dla w. początkowego P ustal s=0. Podstaw D={P}; Zaktualizuj odległość s’ dla wszystkich wierzchołków sąsiednich do D; s’[w] = min { s[x] + waga krawędzi {x, w} ; po wszystkich x należących do D }; Wybierz wierzchołek o minimalnej s’, podstaw dla niego s=s’. D = D È {w}. Algorytm pozwala efektywnie wyznaczyć sieć dróg z określonego wierzchołka do wszystkich innych. Pot. problem: ujemne wagi.

13 Cykl Eulera - alg Fleury’egoWystartuj z wierzchołka o nieparzystym stopniu (jeśli jest); Wybierz dowolną krawędź, ale most wybieraj w ostateczności; Przejdź do kolejnego wierzchołka. Algorytm działa dla grafów eulerowkich, półeulerowskich. Problematyczna jest jednak implementacja testu, czy krawędź jest mostem.

14 Cykl Eulera – alg. ze stosemWystartuj z dowolnego wierzchołka; Jeżeli istnieją nie przechodzone dotąd krawędzie incydentne z bieżącym wierzchołkiem: Wybierz dowolną krawędź; Przejdź do kolejnego wierzchołka i odłóż go na stos; W przeciwnym wypadku: Przenieś wierzchołek do rozwiązania i zdejmij go ze stosu; Przejdź do wierzchołka na szczycie stosu. Algorytm wymaga grafu eulerowskiego.

15 Kolorowanie grafów KOLOROWANIENależy przeprowadzić przydział kolorów w taki sposób, aby sąsiedzi otrzymali różne kolory KOLOROWANIE wierzchołków krawędzi

16 Kolorowanie grafów heuryst. LFWybierz niepomalowany wierzchołek o największym stopniu; Przydziel wierzchołkowi najniższy możliwy kolor. Dobroć algorytmu jest liniowa, tj. można pokazać graf, dla którego: liczba użytych kolorów ~ liczba wierzchołków optymalna liczba kolorów

17 Kolorowanie grafów heuryst. SLWybierz wierzchołek o najmniejszym stopniu w nieprzetworzonym podgrafie; Wstaw wierzchołek na początek sekwencji; Usuń z podgrafu wierzchołek i incydentne z nim krawędzie; Po uporządkowaniu wszystkich wierzchołków przydzielaj kolejnym wierzchołkom w sekwencji najniższe możliwe kolory. Dobroć algorytmu jest liniowa

18 Kolorowanie grafów heuryst. SLFWybierz wierzchołek o największym stopniu saturacyjnym (największej liczbie różnobarwnych sąsiadów), a w przypadku kilku wierzchołków o tym samym stopniu wybierz ten o najwyższym stopniu klasycznym; Przydziel wierzchołkowi najniższy możliwy kolor.

19 Cykl Hamiltona Cykl Hamiltona; Problem Komiwojażera;Algorytm przybliżony.