Lekcja 3 – Izomorfizm i typy grafów

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

• Lekcja 1 (Kurs Grafy (wybrane zagadnienia)) – Wprowadzenie do grafów. Podstawowe pojęcia.
• Lekcja 7 (Kurs Relacje i Funkcje) – Funkcje. Wprowadzenie.
• Lekcja 2 (Kurs Zbiory) – Działania na zbiorach (algebra zbiorów). Dowody i tożsamości. Diagramy Venna.

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]