Страница 60 номер 103, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Докажите, что разным кодам Прюфера соответствуют разные помеченные деревья, и наоборот: разным помеченным деревьям соответствуют разные коды Прюфера.
Пусть в помеченном дереве \(n\) вершин с номерами от 1 до \(n\); его код состоит из \(n - 2\) чисел. Номер записывают в код тогда и только тогда, когда удаляют смежную с этим номером концевую вершину.
Утверждение. На каждом шаге концевые вершины текущего дерева — это в точности те из оставшихся номеров, которые не встречаются в ещё не записанной части кода.
Пусть вершина \(y\) — концевая, к ней примыкает единственное ребро \(xy\). Её номер записали бы только при удалении вершины \(x\), но удаляют лишь концевые вершины, значит, у \(x\) в этот момент тоже было бы единственное ребро \(xy\); тогда ни с \(x\), ни с \(y\) никакая другая вершина не соединена, а дерево связно — следовательно, кроме \(x\) и \(y\), вершин не осталось и алгоритм уже остановился. Значит, номер концевой вершины в оставшуюся часть кода не попадает.
Пусть теперь степень вершины \(y\) не меньше 2. Алгоритм останавливается, когда остаются две вершины, соединённые одним ребром, поэтому либо \(y\) будет удалена — а удаляют её концевой, то есть с единственным ребром, — либо \(y\) окажется одной из двух последних вершин, и при ней снова останется одно ребро. И в том, и в другом случае какое-то ребро \(yz\) исчезло раньше, а исчезнуть оно могло только вместе с концевой вершиной \(z\); в этот момент в код записали номер \(y\). Значит, номер неконцевой вершины в коде есть.
После удаления концевой вершины вместе с её ребром снова получается дерево: связность не нарушается, а циклов и не было. Оставшаяся часть кода — это код нового дерева, поэтому доказанное верно на каждом шаге.
Разным помеченным деревьям отвечают разные коды. Число вершин \(n\) на 2 больше длины кода. По утверждению концевые вершины дерева — это номера, которых нет в коде; значит, первой удаляется наименьшая из них, и она соединена ребром с вершиной, номер которой стоит в коде первым, — первое ребро найдено, причём выбора не было. Остаётся дерево на остальных номерах, кодом которого служит оставшаяся часть кода; тем же рассуждением однозначно находим второе ребро, затем третье и так далее, а когда код кончится, останутся ровно две вершины, соединённые последним ребром. Все \(n - 1\) рёбер найдены однозначно, поэтому два помеченных дерева с одинаковым кодом состоят из одних и тех же рёбер, то есть совпадают.
Разным кодам отвечают разные помеченные деревья. Кодирование тоже не оставляет выбора: на каждом шаге концевая вершина с наименьшим номером одна, и смежная с ней вершина одна, потому что у концевой вершины единственное ребро. Значит, у каждого помеченного дерева ровно один код. Если бы коды \(c\) и \(c'\) были различны, а деревья, которым они отвечают, совпали, то у одного и того же дерева оказалось бы два разных кода, — это невозможно.
Ответ: утверждение доказано: у каждого помеченного дерева ровно один код Прюфера, а по коду дерево восстанавливается однозначно, поэтому разным кодам Прюфера отвечают разные помеченные деревья, а разным помеченным деревьям — разные коды Прюфера.
Докажите, что разным кодам Прюфера соответствуют разные помеченные деревья, и наоборот: разным помеченным деревьям соответствуют разные коды Прюфера.
Пусть в помеченном дереве \(n\) вершин с номерами от 1 до \(n\); его код состоит из \(n - 2\) чисел. Номер записывают в код тогда и только тогда, когда удаляют смежную с этим номером концевую вершину.
Утверждение. На каждом шаге концевые вершины текущего дерева — это в точности те из оставшихся номеров, которые не встречаются в ещё не записанной части кода.
Пусть вершина \(y\) — концевая, к ней примыкает единственное ребро \(xy\). Её номер записали бы только при удалении вершины \(x\). Но удаляют лишь концевые вершины, значит, у \(x\) в этот момент тоже было бы единственное ребро \(xy\); тогда ни с \(x\), ни с \(y\) никакая другая вершина не соединена, а дерево связно — следовательно, кроме \(x\) и \(y\), вершин не осталось и алгоритм уже остановился. Значит, номер концевой вершины в оставшуюся часть кода не попадает.
Пусть теперь степень вершины \(y\) не меньше 2, то есть при ней не меньше двух рёбер. Алгоритм останавливается, когда остаются две вершины, соединённые одним ребром. Поэтому либо \(y\) будет удалена — а удаляют её концевой, то есть с единственным ребром, — либо \(y\) окажется одной из двух последних вершин, и при ней снова останется одно ребро. И в том, и в другом случае какое-то ребро \(yz\) исчезло раньше, а исчезнуть оно могло только вместе с концевой вершиной \(z\); в этот момент в код записали номер \(y\). Значит, номер неконцевой вершины в коде есть.
После удаления концевой вершины вместе с её ребром снова получается дерево: связность не нарушается, а циклов и не было. Алгоритм продолжает работать с ним так же, и оставшаяся часть кода — это код нового дерева. Поэтому доказанное верно на каждом шаге.
Разным помеченным деревьям отвечают разные коды. Покажем, что код полностью определяет дерево.
Число вершин \(n\) известно: оно на 2 больше длины кода. По утверждению концевые вершины дерева — это номера, которых нет в коде; значит, первой удаляется наименьшая из них, и она соединена ребром с вершиной, номер которой стоит в коде первым. Так первое ребро найдено, причём выбора не было. Остаётся дерево на остальных номерах, кодом которого служит оставшаяся часть кода; тем же рассуждением однозначно находим второе ребро, затем третье и так далее. Когда код кончится, останутся ровно две вершины, соединённые ребром, — это последнее ребро. Все \(n - 1\) рёбер найдены однозначно.
Значит, два помеченных дерева с одинаковым кодом состоят из одних и тех же рёбер, то есть совпадают. Другими словами, у разных помеченных деревьев коды разные.
Разным кодам отвечают разные помеченные деревья. Кодирование тоже не оставляет выбора: на каждом шаге концевая вершина с наименьшим номером одна, и смежная с ней вершина одна, потому что у концевой вершины единственное ребро. Значит, у каждого помеченного дерева ровно один код.
Пусть коды \(c\) и \(c'\) различны, а деревья, которым они отвечают, совпали. Тогда у одного и того же дерева оказалось бы два разных кода, а это невозможно. Значит, разным кодам отвечают разные помеченные деревья.
Ответ: утверждение доказано: у каждого помеченного дерева ровно один код Прюфера, а по коду дерево восстанавливается однозначно, поэтому разным кодам Прюфера отвечают разные помеченные деревья, а разным помеченным деревьям — разные коды Прюфера.
