Значит, первое.
Очевидно, подумайте над этим, но это, конечно, очевидно,
что для разных деревьев, для разных деревьев
коды разные.
Ну если хотите, для разных баранов разные камни.
То есть не может такого быть, чтоб мы выпустили двух баранов,
а положили только один камень.
Камней столько, сколько баранов в этом смысле.
Но нам бы надо еще как-то доказать, что любая последовательность может получиться.
То есть что любая последовательность соответствует дереву и заодно описать
процедуру декодирования.
То есть описать процедуру, как,
наоборот, имея на руках какую-нибудь последовательность, построить дерево.
Но самое симпатичное объяснение — это взять вот эту последовательность, описать
для нее процедуру декодирования и увидеть, что получится ровно вот это дерево.
Тогда наступит катарсис, вот.
Ну хорошо, давайте опишем процедуру.
Так, запишем нашу последовательность, вот эту самую 2,
3, 2, код Прюфера, 3, 4, 11, 11,
4, 3, а сверху, если хотите, или снизу, как вам удобнее,
напишем последовательность всех наших натуральных чисел от 1 до 11: 4,
5, 6, 7, 8, 9, 10, 11.
Ну понятное дело, что поскольку последовательность, написанная сверху,
длинее, чем последовательность, написанная снизу, то в этой последовательности
встречаются, заведомо встречаются числа, которых нету здесь.
Наверху есть числа, которых нету внизу.
Давайте выберем среди этих чисел число с самым маленьким номером,
число с самым маленьким номером отсюда, которое отсутствует вот здесь.
Но это, очевидно, 1.
Видите, 1 есть сверху, но 1 вовсе нет снизу.
Отлично!
Удалим 1, удалим 2 и напишем (1,
2), а дальше посмотрим на нашу исходную картинку и попытаемся вспомнить,
какое висячее ребро мы отсекли самым первым с помощью нашего секатора.
Да вот ровно вот это — 1, 2.
Смотрите, мы это ребро только что восстановили.
Подумайте, почему это правильно, почему это всегда так будет?
Хорошо, сейчас фокус продолжится.
Опять у нас осталось здесь сколько-то чисел и опять среди них есть число
с наименьшим номером, которое отсутствует в нижней оставшейся последовательности.
Ну 2 присутствует, 3 присутствует, 4 есть, а 5 нет.
Вычеркиваем 5, вычеркиваем 3 и пишем (3, 5).
После чего смотрим на картинку и вспоминаем, что ровно вот это ребро
мы отсекли на втором шаге нашей процедуры построения кода Прюфера.
То есть мы действительно в точности воспроизводим то самое дерево,
из которой была получена вот эта вот последовательность путем таких вот
махинаций.
Ну, честно говоря, я буду очень зануден,
если сейчас продолжу все это дело воспроизводить, вы, конечно,
можете самостоятельно это проделать руками и убедиться в том,
что вы восстановите все дерево путем такого вот последовательного вычеркивания.
Здесь что-то, здесь что-то, здесь что-то, здесь что-то, и так далее.
Но самое замечательное — что в самый последний момент после всех этих
вычеркиваний здесь окажутся вычеркнутыми все числа.
А знаете, какие два окажутся не вычеркнутыми в верхней последовательности?
Очень легко догадаться.
Ровно те самые, с которыми мы ничего не делали.
В самый последний момент останутся числа (3, 4).
Мы их вот так напишем, и это будет то самое последнее ребро (3, 4).
Ой, (3, 11), да?
Извините, (3, 11), черт возьми.
Э, все плохо.
(3, 11).
(3, 11).
Вот то самое (3, 11), с которым мы в результате,
когда строили код Прюфера, ничего не делали.
Конечно, да, (3, 11).
Вот оно здесь и выживет.
3 выживет и 11 выживет.
А все остальное, можете проверить, в итоге окажется вычеркнутым, равно как и снизу.
Вот такая вот интересная процедура декодирования.
Еще раз повторяю, очень легкое упражнение — понять,
почему это действительно декодирование.
И я надеюсь на то, что слушатели это проделают в общем случае.
Но, друзья, остался еще один момент, который,
на самом деле, здесь нужно как-то прояснить.
Почему все-таки соответствие взаимно однозначное?
Значит, смотрите, что мы поняли?
Мы поняли, что для разных деревьев коды разные,
то есть для разных баранов разные камни.
Мы поняли, что если мы какому-то барану сопоставили некоторый камень,
то мы по этому камню можем прямо идентифицировать этого барана,
то есть камень является паспортом барана, если хотите, порядковым номером.
Вот.
Но мы пока не поняли, почему произвольному камню соответствует именно баран.
А вдруг есть какая-нибудь последовательность, которую мы начнем
декодировать согласно вот этой процедуре и в итоге получим что-нибудь,
не являющееся деревом?
Вот еще какая есть тонкая деталь.
Ну давайте это обсудим.
Так, конечно, не будет на самом деле.
И если мы поймем, почему так не будет, то, естественно,
мы завершим доказательство теоремы Кэли.
Смотрите, вот в рамках этой процедуры,
конечно, мы построили.
В рамках этой процедуры, конечно,
мы построили n − 1 ребро на n вершинах.
Но помните замечательную теорему о четырех эквивалентных
определениях дерева, одно из которых состояло из того,
что если у графа число ребер отличается в меньшую сторону от числа вершин на 1,
то есть если число вершин n, то число ребер n − 1.
И если этот граф еще, к тому же, является ациклическим, тогда он является деревом.
То есть для связанности этого вполне достаточно: n, n − 1 и отсутствия циклов.
Иными словами, вот это условие, что на n вершинах у нас n − 1 ребро,
мы по построению автоматически реализовали.
Это-то понятно.
И, по сути, все, что нужно доказать, — это то,
что в результате вот этой процедуры циклов не возникнет.
Ну, давайте я тоже в этом месте
сформулирую последнее несложное упражнение.
Докажите с помощью индукции,
с помощью индукции, что вот в
этой процедуре циклы возникать не могут.
Это очень просто.
В этой процедуре циклы не возникают.
Все.
Как только вы это доказываете, у нас получается,
что разным баранам соответствуют разные камни, и для каждого камня есть ну,
на самом деле, ровно один баран, которому этот камень является паспортом.
Все. Камней n в степени n − 2, стало быть,
и баранов, то есть деревьев на n вершинах, в точности n в степени n − 2,
и теорема доказана.
Ну, повторяю, нужно немножко поднапрячься и решить вот это упражнение,
которое мне кажется в этом месте очень полезным.
Все.
Теорема доказана.