2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Доказательство формулы Кэли (через коды Прюфера)
Сообщение07.03.2015, 15:47 


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

Цитата:
По любой последовательности длины $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$, доказать по индукции уже не выйдет. Как быть?

 Профиль  
                  
 
 Re: Доказательство формулы Кэли (через коды Прюфера)
Сообщение07.03.2015, 16:16 
Заслуженный участник


26/10/14
380
Новосибирск
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$. Применяем предположение индукции.

 Профиль  
                  
 
 Re: Доказательство формулы Кэли (через коды Прюфера)
Сообщение07.03.2015, 16:26 


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

 Профиль  
                  
 
 Re: Доказательство формулы Кэли (через коды Прюфера)
Сообщение07.03.2015, 16:37 
Заслуженный участник


26/10/14
380
Новосибирск
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$.

 Профиль  
                  
 
 Re: Доказательство формулы Кэли (через коды Прюфера)
Сообщение07.03.2015, 16:57 


07/03/15
27
Цитата:
то есть с последней по номеру вершиной на конце

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

 Профиль  
                  
 
 Re: Доказательство формулы Кэли (через коды Прюфера)
Сообщение07.03.2015, 17:04 
Заслуженный участник


26/10/14
380
Новосибирск
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$.

 Профиль  
                  
 
 Re: Доказательство формулы Кэли (через коды Прюфера)
Сообщение07.03.2015, 17:11 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group