Дано:
а) Дерево с 8 вершинами, 5 из них концевые.
б) Дерево с 12 вершинами, 7 из них концевые.
Найти:
1. Пример дерева с 8 вершинами и 5 концевыми.
2. Пример дерева с 12 вершинами и 7 концевыми.
Решение:
а) Дерево с 8 вершинами и 5 концевыми:
Пример:
1 — 2
1 — 3
1 — 4
2 — 5 (концевая)
2 — 6 (концевая)
3 — 7 (концевая)
4 — 8 (концевая)
В этом дереве 1 — внутреняя вершина, остальные 5 — концевые.
Ответ:
Дерево: 1 — 2, 1 — 3, 1 — 4, 2 — 5, 2 — 6, 3 — 7, 4 — 8.
б) Дерево с 12 вершинами и 7 концевыми:
Пример:
1 — 2
1 — 3
1 — 4
2 — 5
2 — 6
3 — 7
3 — 8 (концевая)
4 — 9 (концевая)
5 — 10 (концевая)
6 — 11 (концевая)
1 — 12 (концевая)
В этом дереве 1, 2 и 3 — внутренние вершины, остальные 7 — концевые.
Ответ:
Дерево: 1 — 2, 1 — 3, 1 — 4, 2 — 5, 2 — 6, 3 — 7, 3 — 8, 4 — 9, 5 — 10, 6 — 11, 1 — 12.