Дмитрий Алехин
Мастер
(1669)
1 год назад
Ответ: 30.
Дерево — это связный граф без циклов. Диаметр дерева — это наибольшее расстояние (количество рёбер в самом длинном простом пути) между любой парой вершин в дереве. Для того чтобы диаметр дерева был максимально возможным, самым длинным путём должен быть путь в форме линии (цепочки), так как каждый раз, когда мы создаём разветвление, мы имеем возможность сделать другой путь короче.
Если у нас есть дерево с 31 вершиной, максимальный диаметр будет, когда дерево представляет собой прямую линию из вершин, т.е. "развернуто" в одну ветвь. В этом случае максимальный диаметр будет равен количеству рёбер, которое всегда на единицу меньше количества вершин в дереве, поскольку в дереве всегда на одно ребро меньше, чем вершин (это свойство определяется формулой для деревьев: |E| = |V| - 1, где |E| — количество рёбер, а |V| — количество вершин).
Таким образом, если у дерева 31 вершина, то максимальный диаметр дерева может быть 31 - 1 = 30.