Czego się nauczysz
Nauczysz się odpowiadać na pytania, które matura najczęściej zadaje o graf: czy jest spójny, z ilu kawałków się składa, jak duży jest największy i czy ma cykl.
Po co ci to na maturze
Czy z każdego miasta da się dojechać do każdego, ile jest osobnych wysp, jak duża jest największa grupa znajomych: to najczęstsze pytania o graf w zadaniach z plikiem.
Etapy lekcji
Spis lekcji
Teoria
4 rozdziałyNie zaczęte- 1.1Czy da się dojść wszędzieJedno przeszukiwanie z dowolnego wierzchołka. Spójny, jeśli dotrze do wszystkich.
- 1.2Ile osobnych kawałkówPętla po wszystkich wierzchołkach. Każdy nieodwiedzony zaczyna nowy kawałek i nowe przeszukiwanie.
- 1.3Drzewo i cykleSpójny graf bez cykli ma n - 1 krawędzi. Każda dodatkowa zamyka cykl.
- 1.4PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.