Дерево — это граф, не содержащий циклов. Распознать дерево в изображении графа бывает не просто. На рисунке изображено дерево, рассмотрите его. Шаг 3: Подсчитайте количество
Реши задание на изображении
Сверь числа и знаки с фото.
Дерево — это граф, не содержащий циклов. Распознать дерево в изображении графа бывает не просто. На рисунке изображено дерево, рассмотрите его.
Шаг 3: Подсчитайте количество потомков у вершины F.
Введите ответ: ___ потомков (потомка)
[Рисунок: дерево с вершинами A, B, C, D, E, F, G, H, I, J, K, L; рёбра: A—D, C—D, D—E, C—B, B—G, G—F, G—H, E—I, H—L, F—K, K—J.]
Краткий ответ: 2 потомка — это вершины K и J.
Как рассуждать
Дерево растёт от корня — верхней вершины A. Потомки вершины — это все вершины, которые находятся ниже неё по ветвям: дети, дети детей и т. д. Саму вершину в потомки не включают.
- Найдём путь от корня к F: A → D → C → B → G → F. Значит, родитель F — вершина G.
- От F «вниз», в сторону от корня, отходит только одно ребро — F—K. Значит, у F единственный ребёнок — K.
- Идём дальше: у K есть ребёнок J (ребро K—J), а у J детей нет.
- Все вершины ниже F — это K и J. Их две.
Проверка
Если мысленно «отрезать» F от G, отделится кусочек дерева из трёх вершин: F, K, J. Потомков считаем без самой F: 3 − 1 = 2. Сходится.
Обрати внимание: детей у F один (K), а потомков два (K и J) — это разные вопросы. Общее правило: чтобы найти потомков вершины, представь дерево растущим от корня и возьми всё, что «висит» ниже неё.
