Доказательство формулы Кэли (через коды Прюфера)

[dxd]

Добрый день. В большинстве статей используется такое доказательство формулы Кэли

Цитата:

По любой последовательности длины $n - 2$ из чисел от $1$ до $n$ можно построить помеченное дерево,для которого эта последовательность является кодом Прюфера.

Доказательство проведем по индукции.
База. $n = 1$ $-$ верно.
Переход от $n$ к $n + 1$.
Пусть у нас есть последовательность: $A = [a_1, a_2, ..., a_{n - 2}].$
Выберем минимальное число $v$ не лежащее в $A$. По предыдущей лемме $v$ $-$ вершина, которую мы удалили первой. Соединим $v$ и $a_1$ ребром. Выкинем из последовательности $A$ число $a_1$. Перенумеруем вершины, для всех $a_i > v$ заменим $a_i$ на $a_i - 1$. А теперь мы можем применить предположение индукции.

Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка $n$ и последовательностями длиной $n - 2$ из чисел от $1$ до $n$
# Каждому помеченному дереву приведенный алгоритм сопоставляет последовательность.
# Каждой последовательности, как следует из предыдущей леммы, соотвествует помеченное дерево.

[url=http://neerc.ifmo.ru/wiki/index.php?title=Коды_Прюфера]Источник[/url]

Тут Кодом прюфера называется произвольная последовательность длины $n-2$.
НО
Если же мы назовем кодом Прюфера произвольную последовательность длины $n-1$, такую, что последним членом является $n$, доказать по индукции уже не выйдет. Как быть?

[NSKuber]

dxd в сообщении #986973 писал(а):

Тут Кодом прюфера называется произвольная последовательность длины $n-2$.
НО
Если же мы назовем кодом Прюфера произвольную последовательность длины $n-1$, такую, что последним членом является $n$, доказать по индукции уже не выйдет. Как быть?

Не совсем понял, что имелось в виду. Попробую пересказать доказательство:
База индукции - понятно, как по последовательности длины $1$, состоящей из одного числа от $1$ до $3$ восстановить однозначно дерево. Пусть утверждение верно для последовательностей длины $n - 3$, состоящих из чисел от $1$ до $n - 1$,
Шаг: пусть теперь у нас есть последовательность $A = [a_1, a_2, ,..., a_{n - 2}]$ длины $n - 2$, состоящая из чисел от $1$ до $n$.
Выберем минимальное число $v$, не лежащее в $A$. По (какой-то) предыдущей лемме, это должна быть вершина, которую мы удалили первой. Соединим $v$ и $a_1$ ребром. Уберём из последовательности $A$ число $a_1$ и перенумеруем вершины, для всех $a_i > v$ заменим $a_i$ на $a_i - 1$ (а уже присоединённую вершину $v$ занумеруем числом $n$). Теперь мы получили последовательность $A' = [{a'}_1, ,..., {a'}_{n - 3}]$ длины $n - 3$, состоящую из чисел от $1$ до $n - 1$. Применяем предположение индукции.

[dxd]

Все верно, но мне хотелось бы доказать для последовательности $[a_1,a_2, .. a_{n-2}, n]$ (Именно ее назовем кодом Прюфера)
Если же мы соединим $v$ и $a_1$ ребром,и перенумеруем, то получим последовательность $[a_1'..a_{n-3}',n]$ и предположение индукции не применить.

[NSKuber]

dxd в сообщении #986981 писал(а):

Все верно, но мне хотелось бы доказать для последовательности $[a_1,a_2, .. a_{n-2}, n]$ (Именно ее назовем кодом Прюфера)
Если же мы соединим $v$ и $a_1$ ребром, и перенумеруем, то получим последовательность $[a_1'..a_{n-3}',n]$ и предположение индукции не применить.

Не вижу проблем с шагом: у вас изначально есть последовательность длины $n - 1$ чисел, лежащих в интервале от $1$ до $n + 1$, после удаления - последовательность чисел длины $n - 2$ чисел в интервале от $1$ до $n$ (Кстати, $n$ на конце останется только в том случае, если $v$ равнялось $n + 1$, в противном случае оно превратится в $n - 1$ после перенумерации). Быть может, чтобы "порушить" доказательство, вы имели в виду последовательность $[a_1,a_2, ..., a_{n-2}, n + 1]$, то есть с последней по номеру вершиной на конце (ну или вообще где-то в последовательности)? Но в таком случае любое (в том числе наименьшее) $v$, не принадлежащее последовательности и не большее $n + 1$ будет, очевидно, меньше $n + 1$, и значит после соединения и перенумерации мы получим последовательность $[a_1', ..., a_{n - 3}', n]$, снова корректную: длиной на единицу меньше и с числами, не превосходящими $n$.

[dxd]

Цитата:

то есть с последней по номеру вершиной на конце

Именно.
Была последовательность $[2 3 4]$, $n=4$.
Добавили в граф $(1,2)$, удалили $2$ из кода. Имеем последовательность $[3 4]$. По индукции рассматриваем ее с %n=3$, видим противоречие.

[NSKuber]

dxd в сообщении #986993 писал(а):

Цитата:

то есть с последней по номеру вершиной на конце

Именно.
Была последовательность $[2 3 4]$, $n=4$.
Добавили в граф $(1,2)$, удалили $2$ из кода. Имеем последовательность $[3 4]$. По индукции рассматриваем ее с %n=3$, видим противоречие.

Так, а остальную часть моего сообщения Вы прочли? И приведённого доказательства? Там такое слово хорошее было, "перенумерация".
На пальцах, на Вашем же примере:
Была последовательность $[2, 3, 4]$, $n = 4$.
Добавили в граф $(1,2)$, удалили $2$ из кода. Перенумеровали вершины следующим образом (всё чётко по доказательству):
$2 \to 1, 3 \to 2, 4 \to 3, 1 \to 4$. Теперь ребро $(1, 2)$ выглядит как $(4, 1)$, а оставшаяся последовательность - $[2, 3]$, ура, можем повторить процедуру для $n = 3$.

[dxd]

Господь Иисус, нещадно затупил.
Спасибо гигантское, вопрос решен.