Дано:
Количество вершин в дереве: 11.
Найти:
Примеры дерева с диаметром:
а) 2;
б) 10.
Решение:
а) Дерево с диаметром 2:
Для получения дерева с диаметром 2 нужно, чтобы все вершины были связаны с центральной вершиной. Пример:
1. Центральная вершина: V1.
2. Вершины, соединенные с V1: V2, V3, V4, V5, V6, V7, V8, V9, V10, V11 (всего 10 вершин).
Структура дерева:
- V1 связано с V2, V3, V4, V5, V6, V7, V8, V9, V10, V11.
В этом случае:
- Диаметр: максимальное расстояние между любыми двумя вершинами (например, V2 и V3) равно 2.
б) Дерево с диаметром 10:
Для дерева с диаметром 10 нужно выстроить его в виде цепочки. Пример:
1. Вершины: V1, V2, V3, V4, V5, V6, V7, V8, V9, V10, V11.
2. Связи: V1 - V2 - V3 - V4 - V5 - V6 - V7 - V8 - V9 - V10 - V11.
Структура дерева:
- V1 связано с V2, V2 связано с V3 и так далее до V11.
В этом случае:
- Диаметр: максимальное расстояние между V1 и V11 равно 10.
Ответ:
а) Дерево с диаметром 2: центральная вершина с 10 связанными вершинами.
б) Дерево с диаметром 10: линейная цепь из 11 вершин.