а) Дано: Степени вершин 1, 1, 2, 2, 2.
Найти: Построить дерево с заданными степенями вершин.
Решение:
1. Сумма степеней вершин должна быть четной для построения дерева. Суммируем степени: 1 + 1 + 2 + 2 + 2 = 8 (четное число).
2. У нас есть две вершины степени 1, три вершины степени 2.
3. Вершины степени 1 будут листьями и должны соединяться с вершинами степени 2.
4. Соединяем вершины:
- Вершина A (степень 1) соединяется с вершиной B (степень 2).
- Вершина C (степень 1) соединяется с вершиной B (степень 2).
- Две оставшиеся вершины D и E (обе степени 2) соединяются с двумя другими вершинами степени 2 (одна из которых уже соединена с вершинами степени 1).
Получаем следующее дерево:
```
B
/ \
A D
|
E
```
Ответ: Дерево существует.
б) Дано: Степени вершин 2, 2, 2, 3.
Найти: Построить дерево с заданными степенями вершин.
Решение:
1. Сумма степеней вершин: 2 + 2 + 2 + 3 = 9 (нечетное число).
2. Сумма степеней в дереве всегда должна быть четной, так как каждое ребро соединяет две вершины.
Ответ: Дерево не существует.
в) Дано: Степени вершин 1, 1, 1, 1, 1.
Найти: Построить дерево с заданными степенями вершин.
Решение:
1. Сумма степеней вершин: 1 + 1 + 1 + 1 + 1 = 5 (нечетное число).
2. Для построения дерева сумма степеней снова должна быть четной.
Ответ: Дерево не существует.
г) Дано: Степени вершин 1, 1, 1, 1, 1, 1, 2, 4.
Найти: Построить дерево с заданными степенями вершин.
Решение:
1. Сумма степеней вершин: 1 + 1 + 1 + 1 + 1 + 1 + 2 + 4 = 12 (четное число).
2. Шесть вершин имеют степень 1, одна вершина имеет степень 2, одна - степень 4.
3. Вершина со степенью 4 будет центральной, соединяем её с четырьмя вершинами степени 1.
4. Вершину со степенью 2 можно соединить с одной из оставшихся вершин степени 1.
Получаем:
```
D
/|\
A B C
|
E
```
Где A, B, C — вершины степени 1, D — вершина степени 4, E — вершина степени 2.
Ответ: Дерево существует.