Zastosowania teorii grafów
Znamy już podstawowe pojęcia związane z teorią grafów. Nauczyliśmy się również przedstawiać grafy w pamięci komputera za pomocą macierzy sąsiedztwa, listy sąsiedztwa i macierzy incydencji. Wiemy także, jak przedstawić relacje w języku teorii grafów.
W tym e‑materiale nauczymy się badać, czy graf zawiera cykl lub ścieżkę Eulera oraz cykl lub ścieżkę Hamiltona.
Implementację tego problemu języku C++ znajdziesz w e‑materiale:
Zastosowania teorii grafów w języku C++Zastosowania teorii grafów w języku C++,
Więcej na temat Eulera i badanych przez niego grafów znajdziesz w e‑materiale Zagadnienie mostów królewieckichZagadnienie mostów królewieckich.
Wyjaśnisz, czym są cykl i ścieżka Eulera oraz cykl i ścieżka Hamiltona.
Scharakteryzujesz kryteria, jakie musi spełniać graf, by istniał w nim cykl lub ścieżka Eulera.
Zapoznasz się z algorytmami szukania w grafie cyklu i ścieżki Eulera oraz cyklu i ścieżki Hamiltona.
Wykonasz ćwiczenia, w których wykorzystasz wiedzę dotyczącą szukania w grafie cyklu i ścieżki Eulera oraz Hamiltona.