Учебник «Вероятность и статистика. 7–9 классы», часть 2, с. 8, §47*
№9. Сколько концевых вершин в дереве на рисунке 10?
✎ Запись в тетрадь
Дано:деревья а), б), в) на рис. 10
Найти:число концевых вершин
Концевая вершина — вершина степени 1.
1а) считаем концы веток: 8;
2в) цепь из 6 вершин: 2 конца.
3Ответ: а) 8; б) 12; в) 2.
Пояснение
Идея. Концевая (висячая) вершина — это вершина, из которой выходит ровно одно ребро (§47*). Её легко узнать по рисунку: это конец ветки.
- 1Достаточно найти вершины степени 1. Развилки (две и больше ветвей) и «проходные» вершины степени 2 не считаем.
- 2Идём по дереву и отмечаем каждый конец ветки, ничего не пропуская и не считая дважды. Удобно отмечать их цветом, как на рисунке, а потом пересчитать.
- 3У цепочки концов всегда два: у начала и у конца. Вершины посередине — «проходные», у каждой степень 2, хоть цепочка и ломается зигзагом.
Проверка. Конечное дерево, в котором есть хотя бы одно ребро, всегда имеет концевую вершину (свойство 2, §47*) — если пересчёт дал 0, где-то ошибка.
