Зв'язність, ланцюги, цикли та обхід графа
Рахуй компоненти зв'язності, знаходь вершини непарного степеня й вирішуй, чи можна обійти граф, не відриваючи олівця.
📖 Почніть тут: читайте кроки «Уроку» по порядку (1, 2, 3 …) і відповідайте на кожне запитання. Потім переходьте до «Практики».
- Росія: 7 клас
Поради для дорослих
В українській програмі цієї теми немає, це розширення. Після вершин, ребер і степеня вводять поняття: ланцюг — послідовність ребер, у якій кожне наступне починається там, де закінчилося попереднє; цикл — ланцюг, що повертається в початкову вершину; граф зв'язний, якщо між будь-якими двома вершинами є ланцюг. Кожен граф розпадається на компоненти зв'язності.
Ейлерів ланцюг проходить по кожному ребру рівно один раз. Він існує, якщо граф зв'язний і вершин непарного степеня нуль або дві. Коли непарних вершин нуль, можливий і замкнений обхід (ейлерів цикл); коли їх дві, ланцюг починається в одній із них і закінчується в другій. Так розв'язується задача про кенігсберзькі мости (там чотири непарні вершини) і питання «чи можна намалювати фігуру, не відриваючи олівця».
Типові помилки: не вважати окрему вершину компонентою; рахувати вершини замість ребер, коли шукаєш степінь; думати, що будь-яку фігуру можна намалювати одним розчерком.