W tej Lekcji znajdziesz rozwinięcie tematu grafów skierowanych: definicje źródła i ujścia, algorytm etykietowania uporządkowanego, twierdzenie Eulera dla grafów skierowanych… Lekcja prosta, mająca charakter wprowadzeniowy.
Przed rozpoczęciem powinieneś powtórzyć:
Video trwa trochę ponad pół godziny.
Spis treści:
- definicja ujścia i źródła [1:22]
- twierdzenie o istnieniu ujścia i źródła [3:16]
- algorytm na znajdywanie ujścia [4:13]
- etykietowanie uporządkowane [6:28]
- twierdzenie o istnieniu etykietowania uporządkowanego [11:32]
- algorytm na znajdywanie etykietowania uporządkowanego wraz z przykładem [11:56]
- wierzchołki osiągalne w grafie skierowanym [18:44]
- stopień wierzchołka w grafie skierowanym [20:44]
- istnienie cyklu Eulera w grafie skierowanym (twierdzenie o cyklu Eulera) [21:43]
- istnienie drogi Eulera w grafie skierowanym (twierdzenie o drodze Eulera) [23:10]
- zadanie 1: znajdywanie źródła i ujścia w grafie skierowanym [25:48]
- zadanie 2: znajdywanie następników i wierzchołków osiągalnych w grafie skierowanym [27:30]
- zadanie 3: znajdywanie etykietowań uporządkowanych [29:07]
- zadanie 4: tworzenie grafu o zadanych właściwościach [32:14]
- odwrócenie grafu [32:55]
- graf zwany „turniejem” [33:17]
- zadanie na „turniej” [34:24]
Wzory potrzebne do Lekcji
Pobierz kartkę z wzorami na grafy (PDF)
Zadanie Domowe
Pobierz Rozwiązania Zadania Domowego (PDF)