Lekcja 6 – Grafy skierowane
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]
