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

Рассмотрим алгоритм построения кода Прюфера для данного дерева T. Он заключается в последовательном удалении листов (вершин степени 1) с наименьшими номерами и записи их соседей.

Допустим, у нас есть два различных помеченных дерева T₁ и T₂. Так как они различны, то существует хотя бы одно ребро (u,v), которое входит в состав T₁, но не входит в состав T₂ (или наоборот).

Процесс декодирования кода Прюфера является детерминированным: по коду можно восстановить дерево единственным образом. Если бы разным деревьям соответствовали одинаковые коды, то при попытке восстановить дерево по этому общему коду мы получили бы противоречие: один и тот же набор шагов восстановления привел бы к двум разным структурам связей. Следовательно, если T₁≠T₂, то их коды Прюфера P(T₁) и P(T₂) также должны быть различными. Это доказывает инъективность отображения «дерево → код».

Теперь рассмотрим обратную задачу: восстановление дерева по коду Прюфера. Пусть даны два различных кода Прюфера C₁=(c_1,c_2,…,c_n-2) и C₂=(d_1,d_2,…,d_n-2).

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

• Инициализируем множество вершин V={1,2,…,n}.
• На каждом шаге i находим минимальный элемент v_i в множестве V, который отсутствует в оставшейся части кода.
• Соединяем вершину v_i с элементом кода c_i (для первого кода) или d_i (для второго кода).
• Удаляем v_i из множества V и переходим к следующему элементу кода.

Так как коды C₁ и C₂ различны, пусть k — первый индекс, на котором они отличаются (c_k≠d_k). На шагах 1,…,k-1 алгоритмы будут работать идентично, так как начальные условия и предыдущие элементы кода совпадают. Однако на шаге k вершина v_k будет соединена с c_k в первом случае и с d_k во втором случае. Поскольку c_k≠d_k, то добавленное ребро (v_k,c_k) отличается от ребра (v_k,d_k). Следовательно, итоговые множества ребер (а значит, и сами деревья) будут различными.

Это доказывает, что отображение «код → дерево» также является инъективным.

Мы показали, что:

1. Если деревья разные, то их коды разные (разным деревьям ⇒ разные коды).
2. Если коды разные, то восстановленные деревья разные (разным кодам ⇒ разные деревья).

Таким образом, между множеством всех помеченных деревьев с n вершинами и множеством всех возможных кодов Прюфера длины n-2 над алфавитом {1,…,n} существует взаимно однозначное соответствие (биекция). Каждый код однозначно определяет одно дерево, и каждое дерево однозначно порождает один код.