В дереве 5 вершин. Определите, какое наибольшее число концевых вершин в нем может быть.

Решение:

Концевые вершины в дереве — это вершины, у которых степень равна 1. В дереве всегда выполняется равенство: сумма степеней всех вершин равна удвоенному числу рёбер. В дереве из 5 вершин число рёбер равно 4 (n-1, где n - число вершин).

Чтобы максимизировать число концевых вершин, нужно минимизировать степени остальных вершин.

Пусть у нас есть 1 центральная вершина, к которой присоединены остальные 4 вершины. Тогда степени этих 4 вершин будут равны 1 (они станут концевыми).

Графически это можно представить так:

• Вершина 1 соединена с вершинами 2, 3, 4, 5.
• Степени вершин: deg(1)=4, deg(2)=1, deg(3)=1, deg(4)=1, deg(5)=1.
• Число концевых вершин: 4.

Другой вариант — это линейное дерево:

• 1-2-3-4-5
• Степени вершин: deg(1)=1, deg(2)=2, deg(3)=2, deg(4)=2, deg(5)=1.
• Число концевых вершин: 2.

Таким образом, наибольшее число концевых вершин достигается, когда одна вершина соединена со всеми остальными.

Ответ: 4