ГДЗ по вероятности и статистике, 10 класс, Высоцкий, номер 102: *. Эйлерова характеристика

Алгоритм работает следующим образом:

1. Определяем множество всех возможных вершин V={1,2,…,n}.
2. Считаем степень каждой вершины в конечном дереве. Изначально считаем, что все вершины имеют степень 1. Затем для каждого числа, встречающегося в коде Прюфера, увеличиваем соответствующую степень на 1. Вершины, не входящие в код, останутся с степенью 1 (это листья).
3. Находим минимальную вершину из множества V, которая имеет текущую степень 1 (лист). Назовём её u.
4. Берём первое число из оставшейся части кода Прюфера, назовём его v. Соединяем ребром вершины u и v.
5. Уменьшаем степень вершины v на 1 (так как мы использовали одно её «свободное» место для соединения с листом). Удаляем u из рассмотрения (она больше не может быть минимальным листом, так как уже соединена).
6. Повторяем шаги 3–5, пока код Прюфера не опустеет.
7. Когда код пуст, у нас останется ровно две вершины со степенью 1. Соединяем их последним ребром.

Код: 2,5,3,5. Количество вершин n=6. Множество вершин: {1,2,3,4,5,6}.

Вычисление степеней:

• Вершина 1: не встречается в коде → степень 1.
• Вершина 2: встречается 1 раз → степень 1+1=2.
• Вершина 3: встречается 1 раз → степень 1+1=2.
• Вершина 4: не встречается в коде → степень 1.
• Вершина 5: встречается 2 раза → степень 1+2=3.
• Вершина 6: не встречается в коде → степень 1.

Текущие степени: d(1)=1,d(2)=2,d(3)=2,d(4)=1,d(5)=3,d(6)=1.

Итерации:

1. Итерация 1: Минимальная вершина со степенью 1 — это 1. Первое число в коде — 2. Добавляем ребро (1,2). Уменьшаем степень 2 до 1. Удаляем 1. Оставшийся код: 5,3,5. Степени: d(2)=1,d(3)=2,d(4)=1,d(5)=3,d(6)=1.
2. Итерация 2: Минимальная вершина со степенью 1 среди оставшихся (2,3,4,5,6) — это 2. Первое число в коде — 5. Добавляем ребро (2,5). Уменьшаем степень 5 до 2. Удаляем 2. Оставшийся код: 3,5. Степени: d(3)=2,d(4)=1,d(5)=2,d(6)=1.
3. Итерация 3: Минимальная вершина со степенью 1 среди оставшихся (3,4,5,6) — это 4. Первое число в коде — 3. Добавляем ребро (4,3). Уменьшаем степень 3 до 1. Удаляем 4. Оставшийся код: 5. Степени: d(3)=1,d(5)=2,d(6)=1.
4. Итерация 4: Минимальная вершина со степенью 1 среди оставшихся (3,5,6) — это 3. Первое число в коде — 5. Добавляем ребро (3,5). Уменьшаем степень 5 до 1. Удаляем 3. Оставшийся код пуст. Степени: d(5)=1,d(6)=1.
5. Финальный шаг: Остались две вершины 5 и 6 со степенью 1. Добавляем ребро (5,6).

Рёбра дерева а): (1,2),(2,5),(4,3),(3,5),(5,6).

Код: 3,3,6,4,6. Количество вершин n=7. Множество вершин: {1,2,3,4,5,6,7}.

Вычисление степеней:

• Вершина 1: не встречается → степень 1.
• Вершина 2: не встречается → степень 1.
• Вершина 3: встречается 2 раза → степень 3.
• Вершина 4: встречается 1 раз → степень 2.
• Вершина 5: не встречается → степень 1.
• Вершина 6: встречается 2 раза → степень 3.
• Вершина 7: не встречается → степень 1.

Текущие степени: d(1)=1,d(2)=1,d(3)=3,d(4)=2,d(5)=1,d(6)=3,d(7)=1.

Итерации:

1. Итерация 1: Минимальная вершина со степенью 1 — 1. Первый элемент кода 3. Ребро (1,3). Степень 3 становится 2. Код: 3,6,4,6. Степени: d(2)=1,d(3)=2,d(4)=2,d(5)=1,d(6)=3,d(7)=1.
2. Итерация 2: Минимальная вершина со степенью 1 — 2. Первый элемент кода 3. Ребро (2,3). Степень 3 становится 1. Код: 6,4,6. Степени: d(3)=1,d(4)=2,d(5)=1,d(6)=3,d(7)=1.
3. Итерация 3: Минимальная вершина со степенью 1 — 3. Первый элемент кода 6. Ребро (3,6). Степень 6 становится 2. Код: 4,6. Степени: d(4)=2,d(5)=1,d(6)=2,d(7)=1.
4. Итерация 4: Минимальная вершина со степенью 1 — 5. Первый элемент кода 4. Ребро (5,4). Степень 4 становится 1. Код: 6. Степени: d(4)=1,d(6)=2,d(7)=1.
5. Итерация 5: Минимальная вершина со степенью 1 — 4. Первый элемент кода 6. Ребро (4,6). Степень 6 становится 1. Код пуст. Степени: d(6)=1,d(7)=1.
6. Финальный шаг: Остались вершины 6 и 7. Ребро (6,7).

Рёбра дерева б): (1,3),(2,3),(3,6),(5,4),(4,6),(6,7).