Lekcja wprowadzająca do grafów. Sprawdzamy, czym właściwie są grafy i podstawowe związane z nimi pojęcia: droga, cykl, wierzchołki, krawędzie…
Rysujemy wykresy i tworzymy tabelki grafów.
Na początek możesz powtórzyć sobie trochę wprowadzenie do relacji (ale nie jest to koniecznie potrzebne):
Video ma około 50 minut.
Spis treści:
- przykłady wykresów [3:15]
- definicje grafu nieskierowanego i skierowanego [5:58]
- zadanie na rysowanie wykresu grafu o zadanych wierzchołkach i krawędziach [13:34]
- zadanie na tworzenie tabelki do grafu o danym wykresie [19:17]
- definicja drogi i długości drogi [22:50]
- zadanie na drogi i ich zapis przy pomocy wierzchołków [23:44]
- definicja cyklu, drogi acyklicznej i grafu acyklicznego [27:25]
- zadanie na szukanie cyklów i określanie acykliczności [29:09]
- zadanie na rysowanie grafu z danych tekstowych [38:20]
- definicje wierzchołków sąsiednich, osiągalności, pętli, krawędzi wielokrotnych [41:22]
- zadanie na odnajdywanie podstawowych elementów grafu w grafie nieskierowanym [43:55]
Wzory potrzebne do Lekcji
Pobierz kartkę z wzorami na grafy (PDF)
Zadanie Domowe
Pobierz Rozwiązania Zadania Domowego (PDF)