Kurs Grafy (wybrane zagadnienia)

Zapisz się na ten Kurs.


Kurs Grafy (wybrane zagadnienia) jest multimedialnym kursem edukacyjnym omawiającym kilka tematów dotyczących grafów. Zawiera 6 Lekcji.

NIE jest to Kurs omawiający w pełni zagadnienie Grafów. Jest to jedna z części wydzielonych z Kursu Matematyki Dyskretnej, która nie została jeszcze ukończona. 

Pierwsza Lekcja poświęcona jest podstawowym pojęciom: czym właściwie są grafy, droga, cykl, wierzchołki, krawędzie…, ostatnia – grafom skierowanym. 

 

Kurs zawiera łącznie lekko ponad 6 godzin nagrań video, na których powoli i od podstaw tłumaczę i pokazuję jak rozwiązywać zadania.

Do nagrań dołączonych jest 60 pytań testowych sprawdzających wiedzę i 105 zadań praktycznych. 

W tym Kursie dzielę się wiedzą zgromadzoną przez wiele lat intensywnego nauczania grafów studentów różnych uczelni. Dowiesz się z niego, między innymi:

  • czym właściwie są grafy i podstawowe związane z nimi pojęcia: droga, cykl, wierzchołki, krawędzie…
  • przedstawienia grafów jako macierzy, szczególnie jako macierz sąsiedztwa
  • czym jest izomorfizm w grafach
  • jakie są podstawowe typy grafów
  • jak wyznaczać drogę i cykl Eulera oraz Hamiltona
  • czym są źródła i ujścia czy też algorytm etykietowania uporządkowanego w grafach skierowanych

…i wielu, wielu innych praktycznych, wypróbowanych “sztuczek”, które oprócz solidnej, około 6-godzinnej elementarnej porcji wiedzy pozwolą Tobie zadziwić może nawet samego siebie na kolokwium czy egzaminie z grafów.

Lekcje

Lekcja 1 – Wprowadzenie do grafów. Podstawowe pojęcia.

Długość: 50 minutAutor: KrystianPoziom trudności: Łatwy

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):

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:55]
  • 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]

Lekcja 2 – Reprezentacja macierzowa grafów

Długość: 34 minutAutor: KrystianPoziom trudności: Umiarkowany

Na tej Lekcji zajmuję się przedstawieniem grafów jako macierze, szczególnie macierzą sąsiedztwa.

Przed rozpoczęciem Lekcji powtórz koniecznie wstęp do macierzy:

Spis treści

  • macierz sąsiedztwa grafu [2:01]
  • zadanie 1: wyznaczanie macierzy sąsiedztwa dla grafu skierowanego [3:13]
  • zadanie 2: wyznaczanie macierzy sąsiedztwa dla grafu nieskierowanego [9:44]
  • zadanie 3: rysowanie wykresu grafu na podstawie jego macierzy sąsiedztwa [11:59]
  • macierz relacji, wykres relacji jako graf [14:32]
  • zliczanie długości dróg w grafie przy pomocy macierzy sąsiedztwa [18:06]
  • zadanie: zliczanie długości dróg w grafie [28:01]
  • macierz incydencji grafu [30:38]

Lekcja 3 – Izomorfizm i typy grafów

Długość: 109 minutAutor: KrystianPoziom trudności: Umiarkowany

Na tej Lekcji przedstawię kilka rzeczy związanych z grafami:

  • izomorfizm
  • zapis przy pomocy ciągów stopni
  • podstawowe typy grafów

Przed rozpoczęciem możesz powtórzyć:

Spis treści

  • pojęcie „identyczności” grafów [1:55]
  • pojęcie „izomorficzności” grafów [4:24]
  • przykład 1: pokazywanie izomorficzności grafów [6:26]
  • przykład 2: pokazywanie izomorficzności grafów [19:00]
  • przykład 3: pokazywanie nie izomorficzności grafów [26:05]
  • zadanie 1: wykazywanie izomorficzności grafów [29:25]
  • zapis grafu przy pomocy ciągu stopni wierzchołków (lub ciągu liczb kolejnych stopni wierzchołków) [38:56]
  • niezmienniki izomorfizmu – definicja z przykładem [42:35]
  • twierdzenie o sumie stopni wierzchołków [48:55]
  • grafy proste, regularne, puste – definicja z przykładem [50:04]
  • zadanie 2: rysowanie grafów prostych i regularnych – 2 przykłady [52:31]
  • zadanie 3: zliczanie liczby grafów prostych [1:03:00]
  • zadanie 4: rysowanie grafu z zadanego ciągu stopni wierzchołków [1:08:23]
  • zadanie 5: rysowanie grafów z zadanego ciągu liczb wierzchołków kolejnych stopni – 2 przykłady [1:15:39]
  • zadanie 6: zastosowanie twierdzenia o sumie stopni wierzchołków (liczenie wierzchołków) [1:19:54]
  • suma grafów z przykładami [1:23:08]
  • zadanie 7: znajdowanie sumy grafów [1:26:02]
  • podgraf [1:27:56]
  • różnica grafów [1:29:25]
  • dopełnienie grafu z przykładem [1:31:44]
  • graf pełny [1:33:58]
  • zadanie 8: graf regularny, którego dopełnienie zawiera podgraf [1:35:35]
  • zadanie 9: grafy samodopełniające się (izomorficzne ze swoim dopełnieniem) [1:39:56]
  • grafy dwudzielne z przykładem [1:44:35]
  • zadanie 10: sprawdzanie, czy graf jest dwudzielny [1:45:58]

Lekcja 4 – Droga i cykl Eulera

Długość: 74 minutAutor: KrystianPoziom trudności: Umiarkowany

Lekcja poświęcona grafom Eulera (czyli cyklom i drogom Eulera w grafach).

Przed rozpoczęciem powinieneś powtórzyć:

Lekcja trwa 1 godzinę 14 minut.

Spis treści

  • powtórzenie i ustalenie podstawowych definicji [0:59]
  • przedstawienie problemu mostów królewieckich [3:47]
  • droga Eulera i cykl Eulera [7:58]
  • zadanie 1: znajdywanie cyklu Eulera [13:46]
  • warunki konieczne istnienia cyklu Eulera z przykładami (twierdzenie o stopniach wierzchołków) [16:46]
  • warunki konieczne istnienia drogi Eulera z przykładami (twierdzenie o stopniach wierzchołków) [21:54]
  • zadanie 2: znajdywanie drogi i cyklu Eulera – 4 przykłady [25:56]
  • warunki wystarczające istnienia drogi i cyklu Eulera z przykładami (twierdzenie o istnieniu drogi i cyklu Eulera) [32:04]
  • algorytm Fulerry’ego do znajdywania drogi i cyklu Eulera [34:04]
  • przykład na zastosowanie algorytmu Fluerry’ego (droga Eulera) [39:33]
  • przykład na zastosowanie algorytmu Fluerry’ego (cykl Eulera) [51:32]
  • przykład na zastosowanie algorytmu Fluerry’ego (brak drogi i cyklu Eulera) [56:37]
  • graf „k-kostka” [1:00:11]
  • zadanie 3: k-kostka i cykl Eulera w niej [1:02:18]
  • zadanie 4: grafy pełne i cykle Eulera w nich [1:04:40]
  • zadanie 5: dom i przechodzenie przez drzwi [1:07:50]

Lekcja 5 – Droga i cykl Hamiltona

Długość: 64 minutAutor: KrystianPoziom trudności: Umiarkowany

Na tej Lekcji przerabiam grafy hamiltonowskie (czyli drogi i cykle Hamiltona).

Przed rozpoczęciem powinieneś powtórzyć:

Video trwa około 1 godzinę.

Spis treści

  • droga Hamiltona [1:52]
  • cykl Hamiltona [3:22]
  • grafy hamiltonowskie [5:08]
  • warunek wystarczający 1 na to, aby graf był grafem hamiltonowskim [5:23]
  • warunek wystarczający 2 na to, aby graf był grafem hamiltonowskim [9:32]
  • warunek wystarczający 3 na to, aby graf był grafem hamiltonowskim [11:50]
  • graf dwudzielny [13:58]
  • graf dwudzielny pełny [16:39]
  • warunek konieczny na to, aby graf był grafem hamiltonowskim [18:36]
  • zadanie 1: szukanie cyklu Hamiltona w grafie [23:28]
  • zadanie 2: szukanie cyklu Hamiltona w grafie [25:12]
  • zadanie 3: szukanie cyklu Hamiltona w grafie [32:06]
  • zadanie 4: sprawdzanie czy podany graf jest pełny, dwudzielny, pełny dwudzielny i hamiltonowski [35:51]
  • zadanie 5: sprawdzanie czy podany graf jest pełny, dwudzielny, pełny dwudzielny i hamiltonowski [38:21]
  • kod Greya [41:22]
  • kody Greya jako cykle Hamiltona [45:09]
  • zadanie 6: grafy hamiltonowskie, powstałe przez przekształcenie grafów pełnych, regularnych i reprezentantów kodów Greya [48:39]
  • zadanie 7: grafy hamiltonowskie, powstałe przez przekształcenie grafów pełnych, regularnych i reprezentantów kodów Greya [52:32]
  • zadanie 8: dowód – graf regularny, którego dopełnienie jest grafem hamiltonowskim [58:55]

Lekcja 6 – Grafy skierowane

Długość: 36 minutAutor: KrystianPoziom trudności: Umiarkowany

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:20]