Дерево — это граф, не содержащий циклов. Распознать дерево в изображении графа бывает не просто. На рисунке изображено дерево, рассмотрите его.
Реши задание на изображении
Сверь числа и знаки с фото.
2.6. Элементы дерева
Дерево — это граф, не содержащий циклов. Распознать дерево в изображении графа бывает не просто. На рисунке изображено дерево, рассмотрите его.
Шаг 2: Подсчитайте количество листьев в этом дереве.
Введите ответ: ___ листьев (листа)
[Рисунок: граф из 12 вершин, обозначенных буквами A, B, C, D, E, F, G, H, I, J, K, L. Рёбра: A–D, D–E, D–C, C–B, C–G, G–F, G–H, H–I, F–K, K–J, K–L.]
Краткий ответ: 6 листьев.
Лист в дереве — это вершина, из которой выходит ровно одно ребро (то есть её степень равна 1). Дальше достаточно аккуратно перебрать все вершины по рисунку.
Шаг 1. Выписываем, с чем соединена каждая вершина.
| Вершина | Соседи | Степень |
|---|---|---|
| A | D | 1 — лист |
| B | C | 1 — лист |
| C | D, B, G | 3 |
| D | A, C, E | 3 |
| E | D | 1 — лист |
| F | G, K | 2 |
| G | C, F, H | 3 |
| H | G, I | 2 |
| I | H | 1 — лист |
| J | K | 1 — лист |
| K | F, J, L | 3 |
| L | K | 1 — лист |
Шаг 2. Отмечаем вершины со степенью 1: A, B, E, I, J, L.
Их шесть — это и есть листья. В поле ответа нужно ввести 6.
Проверка. У дерева из 12 вершин должно быть ровно 11 рёбер, и на рисунке их 11: A–D, D–C, D–E, C–B, C–G, G–F, G–H, H–I, F–K, K–J, K–L. Сумма степеней: \[ 1+1+3+3+1+2+3+2+1+1+3+1=22, \] а она должна равняться удвоенному числу рёбер: \(2\cdot 11=22\). Всё сходится, ни одна вершина и ни одно ребро не потеряны.
Как решать похожие задания. Не нужно искать «главную» вершину или рисовать стрелки: просто для каждого кружка посчитай, сколько линий к нему подходит. Одна линия — лист, две и больше — внутренний узел. Для самопроверки помни: в дереве с \(n\) вершинами всегда \(n-1\) ребро.
