Страница 60 номер 102, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Придумайте алгоритм, восстанавливающий помеченное дерево по коду Прюфера (см. задачу 101). Восстановите дерево по коду Прюфера: а) 2, 5, 3, 5; б) 3, 3, 6, 4, 6.
Алгоритм. Пусть код состоит из \(n - 2\) чисел; тогда в дереве \(n\) вершин с номерами от 1 до \(n\). Число записывают в код тогда и только тогда, когда удаляют концевую вершину: записывают номер смежной с ней вершины.
Номер концевой вершины в код не попадает: к концевой вершине \(y\) примыкает единственное ребро \(xy\), и номер \(y\) записали бы только при удалении вершины \(x\); но удаляют лишь концевые вершины, значит, у \(x\) в тот момент тоже было бы единственное ребро \(xy\), и всё оставшееся дерево состояло бы из одних вершин \(x\) и \(y\) — а на этом алгоритм уже останавливается.
Номер неконцевой вершины в коде есть: у такой вершины \(y\) не меньше двух рёбер, а к концу работы алгоритма при ней остаётся не больше одного, ведь либо \(y\) удаляют, и в этот момент она концевая, либо \(y\) — одна из двух последних вершин. Значит, хотя бы одно ребро при \(y\) исчезло раньше, а исчезнуть оно могло только вместе с концевой вершиной на другом конце — и тогда номер \(y\) записали в код.
После удаления концевой вершины снова получается дерево, а оставшаяся часть кода — это его код, поэтому на каждом шаге концевые вершины текущего дерева — это в точности те из оставшихся номеров, которых нет в оставшейся части кода. Отсюда алгоритм восстановления:
1) число вершин на 2 больше длины кода; выписываем номера \(1, 2, \ldots, n\);
2) берём наименьший из оставшихся номеров, которого нет в оставшейся части кода, и проводим ребро от этой вершины к вершине, номер которой стоит в коде первым;
3) вычёркиваем этот номер из списка вершин, а первое число — из кода;
4) повторяем шаги 2) и 3), пока код не кончится;
5) две оставшиеся вершины соединяем ребром.
а) Код 2, 5, 3, 5 состоит из четырёх чисел, значит, вершин \(4 + 2 = 6\): номера 1, 2, 3, 4, 5, 6.
Шаг 1. В коде 2, 5, 3, 5 нет номеров 1, 4, 6; наименьший — 1, первое число кода — 2, проводим ребро 1—2.
Шаг 2. Остались вершины 2, 3, 4, 5, 6 и код 5, 3, 5; в коде нет номеров 2, 4, 6, наименьший — 2, первое число кода — 5, проводим ребро 2—5.
Шаг 3. Остались вершины 3, 4, 5, 6 и код 3, 5; в коде нет номеров 4 и 6, наименьший — 4, первое число кода — 3, проводим ребро 3—4.
Шаг 4. Остались вершины 3, 5, 6 и код 5; в коде нет номеров 3 и 6, наименьший — 3, первое число кода — 5, проводим ребро 3—5.
Код кончился, остались вершины 5 и 6 — соединяем их ребром 5—6. Получилось дерево с рёбрами 1—2, 2—5, 3—4, 3—5, 5—6.
б) Код 3, 3, 6, 4, 6 состоит из пяти чисел, значит, вершин \(5 + 2 = 7\): номера 1, 2, 3, 4, 5, 6, 7.
Шаг 1. В коде 3, 3, 6, 4, 6 нет номеров 1, 2, 5, 7; наименьший — 1, первое число кода — 3, проводим ребро 1—3.
Шаг 2. Остались вершины 2, 3, 4, 5, 6, 7 и код 3, 6, 4, 6; в коде нет номеров 2, 5, 7, наименьший — 2, первое число кода — 3, проводим ребро 2—3.
Шаг 3. Остались вершины 3, 4, 5, 6, 7 и код 6, 4, 6; в коде нет номеров 3, 5, 7, наименьший — 3, первое число кода — 6, проводим ребро 3—6.
Шаг 4. Остались вершины 4, 5, 6, 7 и код 4, 6; в коде нет номеров 5 и 7, наименьший — 5, первое число кода — 4, проводим ребро 4—5.
Шаг 5. Остались вершины 4, 6, 7 и код 6; в коде нет номеров 4 и 7, наименьший — 4, первое число кода — 6, проводим ребро 4—6.
Код кончился, остались вершины 6 и 7 — соединяем их ребром 6—7. Получилось дерево с рёбрами 1—3, 2—3, 3—6, 4—5, 4—6, 6—7.
Ответ: концевые вершины на каждом шаге — это те номера, которых нет в оставшейся части кода; наименьшую из них соединяют ребром с вершиной, номер которой стоит в коде первым, и вычёркивают оба, а две последние вершины соединяют между собой. По этому алгоритму получаются деревья: а) с рёбрами 1—2, 2—5, 3—4, 3—5, 5—6; б) с рёбрами 1—3, 2—3, 3—6, 4—5, 4—6, 6—7.
Придумайте алгоритм, восстанавливающий помеченное дерево по коду Прюфера (см. задачу 101). Восстановите дерево по коду Прюфера: а) 2, 5, 3, 5; б) 3, 3, 6, 4, 6.
Алгоритм. Пусть код состоит из \(n - 2\) чисел; тогда в дереве \(n\) вершин с номерами от 1 до \(n\).
Число записывают в код тогда и только тогда, когда удаляют концевую вершину: записывают номер смежной с ней вершины. Отсюда видно, какие вершины концевые.
Номер концевой вершины в код не попадает. Действительно, к концевой вершине \(y\) примыкает единственное ребро \(xy\), и номер \(y\) записали бы только при удалении вершины \(x\); но удаляют лишь концевые вершины, значит, у \(x\) в тот момент тоже было бы единственное ребро \(xy\), и всё оставшееся дерево состояло бы из одних вершин \(x\) и \(y\) — а на этом алгоритм уже останавливается.
Номер неконцевой вершины в коде есть. У такой вершины \(y\) не меньше двух рёбер, а к концу работы алгоритма при ней остаётся не больше одного: либо \(y\) удаляют, и в этот момент она концевая, либо \(y\) — одна из двух последних вершин. Значит, хотя бы одно ребро при \(y\) исчезло раньше, а исчезнуть оно могло только вместе с концевой вершиной на другом конце — и тогда номер \(y\) записали в код.
После удаления концевой вершины снова получается дерево, а оставшаяся часть кода — это его код, поэтому сказанное верно на каждом шаге: концевые вершины текущего дерева — это в точности те из оставшихся номеров, которых нет в оставшейся части кода.
Отсюда получается алгоритм восстановления:
1) число вершин на 2 больше длины кода; выписываем номера \(1, 2, \ldots, n\);
2) берём наименьший из оставшихся номеров, которого нет в оставшейся части кода, и проводим ребро от этой вершины к вершине, номер которой стоит в коде первым;
3) вычёркиваем этот номер из списка вершин, а первое число — из кода;
4) повторяем шаги 2) и 3), пока код не кончится;
5) две оставшиеся вершины соединяем ребром.
а) Код 2, 5, 3, 5 состоит из четырёх чисел, значит, вершин \(4 + 2 = 6\): это номера 1, 2, 3, 4, 5, 6.
Шаг 1. В коде 2, 5, 3, 5 нет номеров 1, 4, 6; наименьший из них — 1. Первое число кода — 2, проводим ребро 1—2. Вычёркиваем вершину 1 и первое число кода.
Шаг 2. Остались вершины 2, 3, 4, 5, 6 и код 5, 3, 5. В коде нет номеров 2, 4, 6; наименьший — 2. Первое число кода — 5, проводим ребро 2—5. Вычёркиваем вершину 2 и первое число кода.
Шаг 3. Остались вершины 3, 4, 5, 6 и код 3, 5. В коде нет номеров 4 и 6; наименьший — 4. Первое число кода — 3, проводим ребро 3—4. Вычёркиваем вершину 4 и первое число кода.
Шаг 4. Остались вершины 3, 5, 6 и код 5. В коде нет номеров 3 и 6; наименьший — 3. Первое число кода — 5, проводим ребро 3—5. Вычёркиваем вершину 3 и первое число кода.
Код кончился, остались вершины 5 и 6 — соединяем их ребром 5—6.
Получилось дерево с рёбрами 1—2, 2—5, 3—4, 3—5, 5—6.
б) Код 3, 3, 6, 4, 6 состоит из пяти чисел, значит, вершин \(5 + 2 = 7\): это номера 1, 2, 3, 4, 5, 6, 7.
Шаг 1. В коде 3, 3, 6, 4, 6 нет номеров 1, 2, 5, 7; наименьший — 1. Первое число кода — 3, проводим ребро 1—3. Вычёркиваем вершину 1 и первое число кода.
Шаг 2. Остались вершины 2, 3, 4, 5, 6, 7 и код 3, 6, 4, 6. В коде нет номеров 2, 5, 7; наименьший — 2. Первое число кода — 3, проводим ребро 2—3. Вычёркиваем вершину 2 и первое число кода.
Шаг 3. Остались вершины 3, 4, 5, 6, 7 и код 6, 4, 6. В коде нет номеров 3, 5, 7; наименьший — 3. Первое число кода — 6, проводим ребро 3—6. Вычёркиваем вершину 3 и первое число кода.
Шаг 4. Остались вершины 4, 5, 6, 7 и код 4, 6. В коде нет номеров 5 и 7; наименьший — 5. Первое число кода — 4, проводим ребро 4—5. Вычёркиваем вершину 5 и первое число кода.
Шаг 5. Остались вершины 4, 6, 7 и код 6. В коде нет номеров 4 и 7; наименьший — 4. Первое число кода — 6, проводим ребро 4—6. Вычёркиваем вершину 4 и первое число кода.
Код кончился, остались вершины 6 и 7 — соединяем их ребром 6—7.
Получилось дерево с рёбрами 1—3, 2—3, 3—6, 4—5, 4—6, 6—7.
Ответ: концевые вершины на каждом шаге — это те номера, которых нет в оставшейся части кода; наименьшую из них соединяют ребром с вершиной, номер которой стоит в коде первым, и вычёркивают оба, а две последние вершины соединяют между собой. По этому алгоритму получаются деревья: а) с рёбрами 1—2, 2—5, 3—4, 3—5, 5—6; б) с рёбрами 1—3, 2—3, 3—6, 4—5, 4—6, 6—7.
