Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Теория вероятности и статистика помогите!!!

эмилия Юшкова Ученик (71), закрыт 1 год назад
Количество вершин 31,какой наибольший диаметр может иметь это дерево ?
Лучший ответ
Дмитрий Алехин Мастер (1669) 1 год назад
Ответ: 30.

Дерево — это связный граф без циклов. Диаметр дерева — это наибольшее расстояние (количество рёбер в самом длинном простом пути) между любой парой вершин в дереве. Для того чтобы диаметр дерева был максимально возможным, самым длинным путём должен быть путь в форме линии (цепочки), так как каждый раз, когда мы создаём разветвление, мы имеем возможность сделать другой путь короче.

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

Таким образом, если у дерева 31 вершина, то максимальный диаметр дерева может быть 31 - 1 = 30.
Остальные ответы
Похожие вопросы