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 22 – Wprowadzenie do grafów. Podstawowe pojęcia.
- Lekcja 4 – Funkcje. Wprowadzenie.
- Lekcja 2 – Działania na zbiorach (algebra zbiorów). Dowody i tożsamości. Diagramy Venna.
Spis treści
- pojęcie "identyczności" grafów
- pojęcie "izomorficzności" grafów
- 4 zadania na pokazywanie izomorficzności (lub nie) grafów
- zapis grafu przy pomocy ciągu stopni wierzchołków (lub ciągu liczb kolejnych stopni wierzchołków)
- niezmienniki izomorfizmu - z przykładem
- twierdzenie o sumie stopni wierzchołków
- grafy proste, regularne, puste - 2 przykłady
- zadanie na zliczanie liczby grafów prostych
- zadanie na rysowanie grafu z zadanego ciągu stopni wierzchołków
- 2 zadania na rysowanie grafów z zadanego ciągu liczb wierzchołków kolejnych stopni
- zadanie na zastosowanie twierdzenia o sumie stopni wierzchołków (liczenie wierzchołków)
- suma grafów z zadaniem
- podgraf z zadaniem
- dopełnienie grafu z zadaniem
- graf pełny z zadaniem
- zadanie na grafy samodopełniające się (izomorficzne ze swoim dopełnieniem)
- grafy dwudzielne z zadaniem
