3. Постройте дерево, в котором 12 вершин, причем 2 вершины имеют степень 1, 4 вершины степени 2, 2 вершины степени 3

Ответ: дерево построено

Логика такая:

Для построения дерева с заданными условиями необходимо учитывать, что сумма степеней всех вершин должна быть равна удвоенному числу рёбер. В дереве с 12 вершинами должно быть 11 рёбер. Проверим, можно ли построить такое дерево:

• Пусть x - количество вершин степени больше 3.
• Тогда сумма степеней всех вершин: 2 вершины * степень 1 + 4 вершины * степень 2 + 2 вершины * степень 3 + x вершин * степень >3 = 2 * 1 + 4 * 2 + 2 * 3 + x * степень >3 = 2 + 8 + 6 + x * степень >3 = 16 + x * степень >3
• Сумма степеней должна быть равна 2 * (количество рёбер) = 2 * 11 = 22
• Получаем уравнение: 16 + x * степень >3 = 22
• x * степень >3 = 6

Это возможно, например, если у нас есть 2 вершины степени 3 или 1 вершина степени 6. Построим дерево с 2 вершинами степени 3 и остальными вершинами степени 1 (концевые вершины).

Здесь вершины A, B имеют степень 3, вершины C, D имеют степень 1, остальные вершины имеют степень 1 или 2.

Ответ: дерево построено