8.10.2012
1. Wstęp do Teorii Grafów:
- Co to jest graf?
- Podział grafów na skierowanie i nieskierowane.
- Co to jest cykl?
- Co to znaczy że graf jest spójny?
2. Specyficzne odmiany grafów:
- KLIKA (każdy wierzchołek sąsiaduje z każdym innym).
- DRZEWO (spójny graf acykliczny).
- MULTIGRAF (graf z krawędziami wielokrotnymi i/lub z pętlami).
- GRAF PROSTY (przeciwieństwo Multigrafu).
3. Trasa, ścieżka, droga:
- Trasa może przechodzić wiele razy te same wierzchołki i krawędzie.
- Ścieżka może przechodzić wiele razy te same wierzchołki, ale nie krawędzie.
- Droga nie może przechodzić ani tych samych wierzchołków, ani krawędzi.
4. Stopień wierzchołka:
- W grafie nieskierowanym jest to ilość krawędzi łączących ten wierzchołek z innymi.
- W grafie skierowanym wyróżniamy stopnie wchodzące (ilość krawędź kończąca się w wierzchołku) i wychodzące (krawędź zaczyna się w wierzchołku).
5. Cykl Eulera:
- Jest to cykl zaczynający się w danym wierzchołku, przechodzący wszystkie krawędzie grafu i kończący się w danym wierzchołku.
- Dla grafu nieskierowanego stopnie wszystkich wierzchołków muszą być parzyste.
6. Lista sąsiedztwa:
- Implementacja w C++ z użyciem tablicy dynamicznej (vector).
- Rozwiązanie alternatywne z użyciem wskaźników.
7. ALGORYTM DFS
- Ogólna zasada działania z wyjaśnieniem funkcji tablicy vis.
- DFS jako sposób sprawdzania czy graf jest spójny.
- Możliwość użycia DFS-a, do sprawdzania czy występuje cykl w grafie nieskierowanym.
8.Sprawdzanie cyklu w grafie skierowanym
- Należy podzielić tablice na 3 stany (biały, szary, czarny)
- Jeśli podczas przeszukiwania grafu natrafimy na krawędz prowadząca do szarego wierzchołka, to w grafie występuje cykl.
- NOTKA: Pomyliłem nazwy czasu przetworzenia wieszchołka i opuszczenia go.
- Zmieńcie sobie w notatkach nazwę pre-order na czas przetworzenia, a post-order na czas opuszczenia.
- W kodzie na stronie nazwa tablicy będzie już zmieniona.
9. Zastosowania czasu przetworzenia i opuszczenia wieszchołków (ciekawostka)
- Sprawdzanie w drzewie czy wieszchołek a jest potomkiem b.
- Jeśli jest to zachodzi nierówność czas_przetworzenia[b]<=czas_przetworzenia[a]<czas_opuszczenia[b].
10. Linki do artykułów, kodów, i zadań domowych:
- LINK DO ARTYKUŁU: TEORIA GRAFÓW
- LINK DO ARTYKUŁU: ALGORYTM DFS
- TE ZADANIA WARTO ZROBIĆ: DFS TEORIA GRAFÓW
- KODY Z WYKŁADU
wersja strony: 6, ostatnia edycja: 08 Oct 2012 17:27