Grafy - pojęcia i definicje, metody reprezentacji grafów, algorytmy przeszukiwania i szukania ścieżek, zastosowania praktyczne

Konspect zajęć

I. Wstęp
- Przedstawienie tematu zajęć
- Zaprezentowanie celów i oczekiwań względem ucznia
- Krótka charakterystyka matematyki dyskretnej

II. Grafy - pojęcia i definicje
- Definicja grafu
- Rodzaje grafów skierowane i nieskierowane, ważone i nieważone
- Terminologia grafów wierzchołki, krawędzie, stopień wierzchołka, cykl w grafie, spójność, graf eulerowski i hamiltonowski

III. Metody reprezentacji grafów
- Macierz sąsiedztwa definicja i wskazówki do konstrukcji
- Lista krawędzi definicja i wskazówki do konstrukcji
- Grafy rysunkowe definicja i przykłady

IV. Algorytmy przeszukiwania i szukania ścieżek
- Algorytm DFS (przeszukiwanie wgłąb)
- definicja
- zastosowanie
- przykłady
- Algorytm BFS (przeszukiwanie wszerz)
- definicja
- zastosowanie
- przykłady
- Algorytmy szukania ścieżek
- algorytm Dijkstry
- algorytm Bellmana-Forda
- algorytm A*

V. Zastosowania praktyczne
- Sieci telekomunikacyjne
- Teoria gier
- Grafika komputerowa
- Systemy nawigacyjne

VI. Podsumowanie i zakończenie
- Krótka powtórka najważniejszych pojęć
- Podsumowanie osiągnięć ucznia
- Malowanie drogi do bycia lepszym w matematyce dyskretnej.