Домашнее задание: 1. В дереве 4 вершины. Сколько концевых вершин в нем может быть? Приведите примеры дерева для каждого возможного значения. 2. На рисунке показано дерево. Рассмотрите цепи, соединяющие начальную вершину S с концевыми. Сколько таких цепей имеют длину 2; длину 3; длину 4? 3. Сколько рёбер в дереве, в котором: а) 87 вершин; б) 487 вершин; в) 317 вершин 4. Изобразите какое-нибудь дерево, в котором: а) 8 вершин, 5 из них концевые; б) 10 вершин, 6 из них концевые. 5. Изобразите какое-нибудь дерево, в котором: а) 4 вершины степени 3 и 6 вершин степени 1; 6) 2 вершины степени 4, 2 вершины степени 3 и 8 вершин степени 1.

Решение:

1. В дереве с 4 вершинами может быть 2 или 3 концевые вершины.

   Примеры:

   • 2 концевые вершины: это путь из 4 вершин (линия).
   • 3 концевые вершины: это дерево, где одна вершина соединена с тремя другими.

2. На рисунке показано дерево. Нужно рассмотреть цепи, соединяющие начальную вершину S с концевыми.

   Подсчитаем количество таких цепей:

   • Длина 2: 3 цепи
   • Длина 3: 2 цепи
   • Длина 4: 0 цепей

3. Количество рёбер в дереве:

   В дереве с n вершинами всегда n-1 ребро. Таким образом:

   • а) 87 вершин: 87 - 1 = 86 рёбер
   • б) 487 вершин: 487 - 1 = 486 рёбер
   • в) 317 вершин: 317 - 1 = 316 рёбер

4. Изобразим дерево:

   • а) 8 вершин, 5 из них концевые: такое дерево возможно.
   • б) 10 вершин, 6 из них концевые: такое дерево возможно.

5. Изобразите какое-нибудь дерево, в котором:

   • а) 4 вершины степени 3 и 6 вершин степени 1: невозможно, так как сумма степеней всех вершин должна быть равна удвоенному числу рёбер. В данном случае сумма степеней равна 4*3 + 6*1 = 18, что означает 9 рёбер. Но число вершин равно 4+6=10, а значит, в дереве должно быть 9 рёбер (что выполняется). Однако вершина степени 3 не может существовать, если остальные вершины имеют степень 1.
   • б) 2 вершины степени 4, 2 вершины степени 3 и 8 вершин степени 1: невозможно. Сумма степеней = 2*4 + 2*3 + 8*1 = 8 + 6 + 8 = 22. Значит, число рёбер = 11. Число вершин = 2 + 2 + 8 = 12. В дереве с 12 вершинами должно быть 11 рёбер (что выполняется). Но существование вершин степени 4 и 3 при наличии 8 вершин степени 1 невозможно.

Ответ: смотри решение выше

Ты молодец! У тебя всё получится!