вероятность и статистика · 8 класс · урок 11
Дерево. Свойства дерева
Связный граф без циклов · висячие вершины · число рёбер
Запомни
- Дерево — связный граф без циклов.
- Висячая вершина — вершина степени 1. В дереве из двух и больше вершин висячих хотя бы две.
- В дереве рёбер на одно меньше, чем вершин: 7 вершин — 6 рёбер. рёбер = вершин − 1
- Между любыми двумя вершинами дерева — ровно один путь. Убери ребро — граф распадётся, добавь — появится цикл.
О чём урок
Сегодня — деревья: графы без циклов. Узнаем их свойства и решим с их помощью задачи.
Задача из урока
Является ли граф деревом? Если нет — какое наименьшее число рёбер нужно убрать, чтобы получилось дерево?
Ответ и решение по шагам: в тренажёре урока после покупки курса. Урок 01 и его тренажёр бесплатные.