Відновити дерево по коду Прюфера , даю 100 б 1, 5, 5, 9, 4, 3, 7, 11, 16,9,10,10,11,15

Ответ:

Крок 1: Створюємо список частот (frequency) для кожної вершини.

| Вершина | Частота |

|---------|---------|

| 1 | 1 |

| 2 | 0 |

| 3 | 1 |

| 4 | 1 |

| 5 | 2 |

| 6 | 0 |

| 7 | 1 |

| 8 | 0 |

| 9 | 2 |

| 10 | 2 |

| 11 | 2 |

| 12 | 0 |

| 13 | 0 |

| 14 | 0 |

| 15 | 1 |

| 16 | 1 |

Крок 2: Минуле крок забезпечує нам відсутність вершини №2 та №6 в коді Прюфера. Створюємо списки суміжності для кожної вершини, що залишилася.

| Вершина | Список суміжності |

|---------|------------------|

| 1 | 5, 16 |

| 3 | 4, 7 |

| 4 | 3, 5 |

| 5 | 1, 4, 9 |

| 7 | 3, 9, 11 |

| 9 | 5, 7, 10, 11 |

| 10 | 9, 11, 15 |

| 11 | 7, 9, 10 |

| 15 | 10 |

| 16 | 1 |

Крок 3: Знаходимо вершину з мінімальною частотою - це вершина №1.

Крок 4: Знаходимо вершину в її списку суміжності, яка має мінімальну частоту - це вершина №16. Додаємо ребро (1,16) до нашого дерева і віднімаємо 1 від частоти обох вершин.

Крок 5: Повторюємо кроки 3 та 4 до тих пір, поки не залишиться лише дві вершини.

Крок 3: Вершина з найменшою частотою - це вершина №6.

Крок 4: Вершина з найменшою частотою в її списку суміжності - це вершина №15. Додаємо ребро (6,15) до нашого дерева і віднімаємо 1 від частоти обох вершин.

Залишилися лише дві вершини, тому додаємо останнє ребро (5,9) та отримуємо наше дерево за кодом Прюфера:

5---1---16

|

4

|

9---5 15

| |

7 10

| |

3 11

|

9

Для відновлення дерева за кодом Прюфера необхідно виконати наступні кроки:

1. Створити список степенів вершин, що складається з нулів.
2. Пройтися по коду Прюфера та знайти кількість повторень кожного числа. Додавати знайдену кількість до відповідних степенів вершин.
3. Знайти вершину з найменшою степенню та додати ребра до неї, щоб утворити дерево. Зменшити степені суміжних вершин на 1.
4. Повторити крок 3, поки не будуть додані всі ребра.

Отже, за кодом Прюфера 1, 5, 5, 9, 4, 3, 7, 11, 16, 9, 10, 10, 11, 15 будується наступне дерево:

1

/

5 5

/

9 4

/

7 3

/

11 16

/

10 9

/

10 15