Похожие вопросы
2024-05-06 22:03:27
Маша допустила ошибку.
Объяснение:
Дерево – это связный граф без циклов. В любом дереве количество рёбер всегда на одно меньше, чем количество вершин. Это можно доказать по индукции или рассмотреть так:
- Начинаем с одной вершины (корня дерева). В этот момент рёбер нет.
- Каждая новая вершина, добавляемая к дереву, соединяется ребром с одной из существующих вершин.
- Таким образом, с каждой новой вершиной добавляется ровно одно ребро.
- Следовательно, количество рёбер всегда будет на одно меньше, чем количество вершин.
В случае Маши, если вершин 9, то рёбер должно быть 8. Поэтому дерево, которое построила Маша, либо содержит цикл, либо несвязно, и, следовательно, не является деревом.
