восстановить дерево по коду прюфера 2,2,4,1

Код Прюфера: $(2,2,4,1)$. Длина 4 ⇒ число вершин $n=4+2=6$, метки $1,2,3,4,5,6$.

Считаем степени: $\deg(v)=1+$ (сколько раз $v$ встречается в коде)

• 1 встречается 1 раз ⇒ $\deg(1)=2$
• 2 встречается 2 раза ⇒ $\deg(2)=3$
• 3 встречается 0 раз ⇒ $\deg(3)=1$
• 4 встречается 1 раз ⇒ $\deg(4)=2$
• 5 встречается 0 раз ⇒ $\deg(5)=1$
• 6 встречается 0 раз ⇒ $\deg(6)=1$

Дальше на каждом шаге берём наименьший лист (вершина со степенью 1) и соединяем с текущим элементом кода:

1. лист 3 + элемент 2 ⇒ ребро (3,2)
2. лист 5 + элемент 2 ⇒ ребро (5,2)
3. лист 2 + элемент 4 ⇒ ребро (2,4)
4. лист 4 + элемент 1 ⇒ ребро (4,1)
   Остались два листа 1 и 6 ⇒ финальное ребро (1,6)

Ответ: рёбра дерева

$$\{(2,3),\ (2,5),\ (2,4),\ (4,1),\ (1,6)\}.$$

Удобный вид (как рисунок)

• $2$ соединена с $3,5,4$
• $4$ соединена с $2,1$
• $1$ соединена с $4,6$

ASCII-схема:

text
3
 \
  2—5
  |
  4—1—6