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: