Дано:
а) 6 вершин степени 3 и 8 вершин степени 1.
б) 1 вершина степени 4, 2 вершины степени 3, и 6 вершин степени 1.
Найти:
1. Пример дерева с 6 вершинами степени 3 и 8 вершин степени 1.
2. Пример дерева с 1 вершиной степени 4, 2 вершинами степени 3 и 6 вершинами степени 1.
Решение:
а) Дерево с 6 вершинами степени 3 и 8 вершин степени 1:
Пример:
Вершина 1 (степень 3) соединена с вершинами 2 (степень 1), 3 (степень 1), 4 (степень 3)
Вершина 4 соединена с вершинами 5 (степень 1), 6 (степень 1), 7 (степень 1)
Вершина 4 соединена с вершиной 8 (степень 1)
Вершины 2, 3, 5, 6, 7, 8 — концевые.
Ответ:
Дерево: 1 — 2, 1 — 3, 1 — 4, 4 — 5, 4 — 6, 4 — 7, 4 — 8.
б) Дерево с 1 вершиной степени 4, 2 вершинами степени 3 и 6 вершинами степени 1:
Пример:
Вершина 1 (степень 4) соединена с вершинами 2 (степень 3), 3 (степень 3), 4 (степень 1), 5 (степень 1)
Вершина 2 соединена с вершинами 6 (степень 1), 7 (степень 1)
Вершины 4, 5, 6, 7 — концевые.
Ответ:
Дерево: 1 — 2, 1 — 3, 1 — 4, 1 — 5, 2 — 6, 2 — 7.