дано: Дерево с n вершинами.
найти: Доказать, что количество рёбер в дереве равно (n - 1).
решение:
1. Дерево — это связный ациклический граф. Это означает, что в дереве нет циклов и существует путь между любыми двумя вершинами.
2. Рассмотрим процесс построения дерева:
- Начинаем с одной вершины. Эта вершина не имеет рёбер (количество рёбер = 0).
- При добавлении каждой новой вершины мы соединяем её с уже существующими вершинами при помощи одного ребра.
3. Если у нас есть одна вершина, то:
- количество рёбер = 0.
4. Когда мы добавляем первую вершину (всего 2 вершины), мы добавляем 1 ребро:
- количество рёбер = 1.
5. При добавлении третьей вершины мы добавляем ещё одно ребро:
- количество рёбер = 2.
6. Таким образом, для добавления каждой из n-1 новых вершин мы всегда добавляем ровно по одному ребру.
7. Следовательно, если мы имеем n вершин, количество рёбер можно выразить как:
- количество рёбер = n - 1.
ответ: В дереве с n вершинами количество рёбер равно (n - 1).