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

Задание №1

В дереве с 4 вершинами может быть от 2 до 3 концевых вершин. Рассмотрим возможные варианты:

• 2 концевые вершины: Это случай, когда дерево представляет собой путь (цепь) из 4 вершин. В этом случае две вершины имеют степень 1 (концевые), а две другие — степень 2.
• 3 концевые вершины: Это случай, когда одна вершина соединена с тремя другими. Одна вершина имеет степень 3, а три другие — степень 1 (концевые).

Задание №3

В дереве количество рёбер всегда на 1 меньше количества вершин. Давай вычислим количество рёбер для каждого случая:

1. 87 вершин: Количество рёбер = 87 - 1 = 86.
2. 487 вершин: Количество рёбер = 487 - 1 = 486.
3. 317 вершин: Количество рёбер = 317 - 1 = 316.

Задание №4

a) Дерево с 8 вершинами, 5 из которых концевые:

Такое дерево возможно. Например, можно представить дерево в виде звезды, где одна центральная вершина соединена с 5 концевыми вершинами, и еще две вершины соединены с центральной.

б) Дерево с 10 вершинами, 6 из которых концевые:

Такое дерево возможно. Аналогично предыдущему случаю, можно представить дерево в виде звезды, где одна центральная вершина соединена с 6 концевыми вершинами, и еще три вершины соединены с центральной.

Ответ: Решения выше.