Условие
Сколько концевых вершин в дереве на рисунке 10?
Идея решения. Концевая вершина — вершина, из которой выходит ровно одно ребро. Считаем такие вершины в каждом дереве.
Решение
Как считать
Концевые вершины — это «кончики веток»: из них выходит по одному ребру. Вершины, где ветки разветвляются или продолжаются дальше, не считаем.
Дерево а)
Концевые вершины: две на верхней левой ветке, две на верхней правой ветке, две на ветке справа, одна слева и одна внизу, у «ствола». Всего .
Дерево б)
В дереве пять развилок. От верхней левой, верхней правой, левой и нижней развилок отходит по 3 концевые вершины, у центральной развилки концевых нет. Всего .
Дерево в)
Это цепь из 6 вершин (зигзаг). Концевые — только две крайние вершины.
Ответ
- а) 8
- б) 12
- в) 2
✓ Ответ проверен вычислением