Lekcja poświęcona grafom Eulera (czyli cyklom i drogom Eulera w grafach).
Przed rozpoczęciem powinieneś powtórzyć:
Lekcja trwa 1 godzinę 14 minut.
Spis treści:
- powtórzenie i ustalenie podstawowych definicji [0:59]
- przedstawienie problemu mostów królewieckich [3:47]
- droga Eulera i cykl Eulera [7:58]
- zadanie 1: znajdywanie cyklu Eulera [13:46]
- warunki konieczne istnienia cyklu Eulera z przykładami (twierdzenie o stopniach wierzchołków) [16:46]
- warunki konieczne istnienia drogi Eulera z przykładami (twierdzenie o stopniach wierzchołków) [21:54]
- zadanie 2: znajdywanie drogi i cyklu Eulera – 4 przykłady [25:56]
- warunki wystarczające istnienia drogi i cyklu Eulera z przykładami (twierdzenie o istnieniu drogi i cyklu Eulera) [32:04]
- algorytm Fulerry’ego do znajdywania drogi i cyklu Eulera [34:04]
- przykład na zastosowanie algorytmu Fluerry’ego (droga Eulera) [39:33]
- przykład na zastosowanie algorytmu Fluerry’ego (cykl Eulera) [51:32]
- przykład na zastosowanie algorytmu Fluerry’ego (brak drogi i cyklu Eulera) [56:37]
- graf „k-kostka” [1:00:11]
- zadanie 3: k-kostka i cykl Eulera w niej [1:02:18]
- zadanie 4: grafy pełne i cykle Eulera w nich [1:04:40]
- zadanie 5: dom i przechodzenie przez drzwi [1:07:50]
Wzory potrzebne do Lekcji
Pobierz kartkę z wzorami na grafy (PDF)
Zadanie Domowe
Pobierz Rozwiązania Zadania Domowego (PDF)