Na tej Lekcji przerabiam grafy hamiltonowskie (czyli drogi i cykle Hamiltona).
Przed rozpoczęciem powinieneś powtórzyć:
- Lekcja 1 – Wprowadzenie do grafów. Podstawowe pojęcia.
- Lekcja 3 – Izomorfizm i typy grafów
- Lekcja 4– Droga i cykl Eulera
Video trwa około 1 godzinę.
Spis treści:
- droga Hamiltona [1:52]
- cykl Hamiltona [3:22]
- grafy hamiltonowskie [5:08]
- warunek wystarczający 1 na to, aby graf był grafem hamiltonowskim [5:23]
- warunek wystarczający 2 na to, aby graf był grafem hamiltonowskim [9:32]
- warunek wystarczający 3 na to, aby graf był grafem hamiltonowskim [11:50]
- graf dwudzielny [13:58]
- graf dwudzielny pełny [16:39]
- warunek konieczny na to, aby graf był grafem hamiltonowskim [18:36]
- zadanie 1: szukanie cyklu Hamiltona w grafie [23:28]
- zadanie 2: szukanie cyklu Hamiltona w grafie [25:12]
- zadanie 3: szukanie cyklu Hamiltona w grafie [32:06]
- zadanie 4: sprawdzanie czy podany graf jest pełny, dwudzielny, pełny dwudzielny i hamiltonowski [35:51]
- zadanie 5: sprawdzanie czy podany graf jest pełny, dwudzielny, pełny dwudzielny i hamiltonowski [38:21]
- kod Greya [41:22]
- kody Greya jako cykle Hamiltona [45:09]
- zadanie 6: grafy hamiltonowskie, powstałe przez przekształcenie grafów pełnych, regularnych i reprezentantów kodów Greya [48:39]
- zadanie 7: grafy hamiltonowskie, powstałe przez przekształcenie grafów pełnych, regularnych i reprezentantów kodów Greya [52:32]
- zadanie 8: dowód – graf regularny, którego dopełnienie jest grafem hamiltonowskim [58:55]
Wzory potrzebne do Lekcji
Pobierz kartkę z wzorami na grafy (PDF)
Zadanie Domowe
Pobierz Rozwiązania Zadania Domowego (PDF)