Jesteś tutaj: Strona główna / Kurs / Kurs Grafy (wybrane zagadnienia)Przykładowy fragment Kursu Zalicz wszystkie Testy na 80%, aby otrzymać Certyfikat !
VIDEO
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.
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: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]
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]
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 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]
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]
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]
