Lekcja 31 – 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ć:

• Lekcja 22 – Wprowadzenie do grafów. Podstawowe pojęcia.
• Lekcja 26 – Droga i cykl Eulera

Video trwa trochę ponad pół godziny. Lekcja składa się z:

• Video (AVI, 36 minut)
• Kartek ze wzorami
• Zadania Domowego wraz z Odpowiedziami (PDF, 10 pytań testowych i 19 przykładów do rozwiązania)
• Materiałów na Forum dotyczących tej Lekcji

---

Video

• definicja ujścia i źródła
• twierdzenie o istnieniu ujścia i źródła
• algorytm na znajdywanie ujścia
• etykietowanie uporządkowane
• twierdzenie o istnieniu etykietowania uporządkowanego
• algorytm na znajdywanie etykietowania uporządkowanego wraz z przykładem
• wierzchołki osiągalne w grafie skierowanym
• stopień wierzchołka w grafie skierowanym
• istnienie cyklu Eulera w grafie skierowanym
• istnienie drogi Eulera w grafie skierowanym
• zadanie na znajdywanie źródła i ujścia w grafie skierowanym
• zadanie na znajdywanie następników i wierzchołków osiągalnych w grafie skierowanym
• zadanie na znajdywanie etykietowań uporządkowanych
• zadanie na tworzenie grafu o zadanych właściwościach
• odwrócenie grafu
• graf zwany "turniejem"
• zadanie na "turniej"

(...)