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