В дереве 84 вершины, сколько концевых вершин у него может быть? Варианты ответов 83 2 4 84 85 67 1

Чтобы понять, сколько может быть концевых вершин (листьев) в дереве с 84 вершинами, давайте рассмотрим некоторые основные свойства деревьев.

1. Что такое дерево?

   • Дерево — это связный граф без циклов. Оно состоит из вершин и рёбер, которые соединяют эти вершины.

2. Определение концевых (листьевых) вершин:

   • Концевые вершины, или листья, — это такие вершины, которые имеют всего одно ребро. Все остальные вершины в дереве могут иметь больше одного ребра.

3. Формула для расчёта числа концов дерева:

   • В любом дереве с \( n \) вершинами количество концевых вершин (листьев) \( L \) всегда удовлетворяет следующей формуле: \[ L = n - k + 1 \] где \( k \) — количество внутренних вершин (вершин, у которых есть хотя бы два ребра).

4. Максимальное количество концевых вершин:

   • Чтобы максимизировать количество концевых вершины, нужно минимизировать число внутренних вершин. Это достигается, когда у нас много листьев и только одна внутренняя вершина.
   • Если у нас есть 1 внутренняя вершина, все остальные \( 83 \) вершины могут быть листьями.

5. Расчет:

   • Подставляем значения в формулу: \[ L = 84 - 1 + 1 = 84 \] Это соответствует случаю с одним корнем и 83 листьями.

6. Минимальное количество концевых вершин:

   • Чтобы минимизировать количество концевых вершин, можно создать дерево, в котором каждая внутренняя вершина соединена с несколькими другими вершинами. Но в любом случае, у дерева с 84 вершинами не может быть меньше 2 листьев (если у нас есть хотя бы одна внутренняя вершина).

Теперь мы можем перечислить возможные варианты для количества концевых вершин:

• Минимальное число листьев: 2
• Максимальное число листьев: 84

7. Выбор ответа:

• Из предложенных вариантов, подходящие числа — это 84 (максимум) и 2 (минимум). Однако, среди указанных вариантов 84 уже входит в список.

Таким образом, ответ: 84.