Второй способ кодирования

Перенумеруем вершины дерева произвольным образом (рис.2.35). Найдем висячую вершину с наименьшим номером. Запишем номер единственной смежной с ней вершины и удалим висячую вершину вместе с ребром.

Пример. Построить код дерева, изображенного на рис. 2.35.

Висячая вершина с наименьшим номером – 1, смежная с ней – 2. Удаляем вершину 1 вместе с ребром и записываем в код 2. В оставшемся дереве висячая вершина с наименьшим номером – 5, смежная с ней – 4. Удаляем вершину 5 вместе с ребром и записываем в код 4. В оставшемся дереве висячая вершина с наименьшим номером – 6, смежная с ней – 4. Удаляем вершину 6 вместе с ребром и снова записываем в код 4. В оставшемся дереве висячая вершина с наименьшим номером – 7, смежная с ней – 4. Удаляем вершину 7 вместе с ребром и снова записываем в код 4. В оставшемся дереве висячая вершина с наименьшим номером – 4, смежная с ней – 2. Удаляем вершину 4 вместе с ребром и записываем в код 2. В оставшемся дереве висячая вершина с наименьшим номером – 2, смежная с ней – 3. Удаляем вершину 2 вместе с ребром и записываем в код 3. Осталось одно ребро. Получили код дерева [244423].

Восстановление дерева по коду рассмотрим на примере кода [2557389]. Вместо первого числа в коде пишем наименьшее, не встречающееся в коде: 1557389. Вместо второго числа в новой последовательности пишем наименьшее, не встречающееся в ней: 1257389 и т.д. Получаем последовательность 1245637. Расположив ее под кодом, получим список ребер: (2,1), (5, 2), (5, 4), (7, 5), (3,6), (8,3), (9, 7). Строим сначала граф по этому списку ребер (рис.2.36). В последовательности 1245637 отсутствуют числа 8 и 9. Соединяем вершины 8 и 9 ребром и получаем граф (рис. 2.37).

Можно показать, что между помеченными деревьями (т.е. деревьями с пронумерованными вершинами) и последовательностями , где существует взаимно однозначное соответствие. Поэтому количество помеченных деревьев равно (формула Кэли).