Математика / Дискретная математика

Код Прюфера: число деревьев с заданными степенями

В коде Прюфера метка вершины встречается на единицу меньше её степени. Поэтому число помеченных деревьев с фиксированной степенью каждой вершины равно мультиномиальному коэффициенту.

Опубликовано: Обновлено:

Формула

$$N(d_1,\ldots,d_n)=\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!},\qquad d_i\ge1,\quad\sum_i d_i=2(n-1)$$
Схема Дерево для кода112
12345

Рёбра13,14,12,25дают степени(3,2,1,1,1). Метки листьев3,4,5в коде не встречаются.

Обозначения

$n$
число помеченных вершин, n≥2, шт.
$d_i$
степень конкретной вершины с меткой i, рёбер
$N$
число деревьев с указанной степенью каждой метки, шт.
$d_i-1$
число появлений метки iв коде Прюфера, шт.

Условия применения

Граф простой, неориентированный и является деревом на вершинах 1,…,nпри n≥2. Все d_iположительные целые и в сумме дают 2(n−1). Дана степень каждой метки, а не только неупорядоченный набор степеней. Код Прюфера имеет длину n−2; для n=2 он пустой.

Ограничения

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

Подробное объяснение

Код Прюфера получают последовательным удалением листа с наименьшей меткой и записью его соседа, пока не останутся две вершины. Длина последовательности n−2. Обратный алгоритм восстанавливает дерево однозначно, поэтому можно считать последовательности вместо графов.

Вершина iпопадает в код всякий раз, когда удаляется один из её соседей до её собственного превращения в лист. Из d_iинцидентных рёбер последнее остаётся к моменту удаления самой вершины или к финальной паре, а остальные дают d_i−1 записей. Поэтому условие степеней эквивалентно фиксированным кратностям меток в последовательности.

Сумма кратностей равна Σ(d_i−1)=2(n−1)−n=n−2, то есть точно длине кода. Число последовательностей с такими кратностями равно(n−2)!/∏(d_i−1)!. Деление на факториалы убирает перестановки одинаковых копий одной метки; разные метки при этом не отождествляются.

У листьев d_i=1 и кратность 0, поэтому они в коде не встречаются. У звезды с заданным центром код состоит из одной повторяющейся метки, и формула даёт 1. Суммируя по всем допустимым последовательностям степеней, получают общее число Кэли n^(n−2), но данная статья отвечает на более узкий вопрос о фиксированных степенях каждой вершины.

Как пользоваться формулой

  1. Привяжите требуемую степень к каждой метке и проверьте положительность целых d_i, а затем сумму 2(n−1).
  2. Вычтите единицу из каждой степени, получив кратности меток в коде; их сумма должна равняться n−2.
  3. Найдите мультиномиальное число(n−2)!/∏(d_i−1)!, используя 0!=1 для всех листьев дерева.
  4. Для малого nперечислите коды с этими кратностями и декодируйте их; проверьте степени восстановленных деревьев и число вариантов.

Историческая справка

Код Прюфера относится к классическим биективным методам подсчёта помеченных деревьев. Его назначение—поставить дерево в однозначное соответствие короткой последовательности меток, после чего графовый подсчёт становится подсчётом слов. Общее число последовательностей даёт формулу Кэли, а фиксированные кратности позволяют уточнить её по степеням.

В современных университетских лекциях, в том числе курсе теории графов 2017 года, отдельный раздел посвящён числу деревьев с заданной последовательностью степеней. В учебнике Foundations of Data Science также используется соответствие с последовательностями длины n−2. Современная алгоритмическая запись уточняет детерминированный выбор наименьшего листа, чтобы кодирование и восстановление были взаимно обратными; сам подсчёт зависит от кратностей, а не от способа рисования дерева.

Историческая линия формулы

Используется традиционное имя кода Прюфера. Здесь не устанавливается отдельное первенство для мультиномиальной записи: она непосредственно следует из биекции и кратностей меток. Формула Кэли для общего числа деревьев остаётся связанным, но отдельным результатом.

Пример

На метках 1,2,3,4,5 требуются степени 3,2,1,1,1 соответственно. Сумма 8 равна 2·(5−1), условия выполнены. Кратности в коде равны 2,1,0,0,0, так что код состоит из двух единиц и одной двойки. Число деревьев равно 3!/(2!1!0!0!0!)=3. Все коды:112,121,211. Для 112 декодирование удаляет лист 3 и соединяет его с 1, затем лист 4 с 1, затем лист 1 с 2; последние 2 и 5 соединяются. Получены рёбра 13,14,12,25. Степень 1 равна 3, степень 2 равна 2, а 3,4,5—листья, как требовалось. Два других кода дают другие помеченные деревья. Их нельзя склеить по похожему виду рисунка, потому что вершины различимы.

Частая ошибка

Степень d_iнельзя брать как число повторений метки: в коде повторений d_i−1. Нельзя делить на перестановки разных меток, если задана степень каждой из них. Нулевая степень недопустима при n≥2. Сумма степеней равна 2(n−1), а не n−1. Формула не учитывает запрет отдельных рёбер; для остовов заданной сети нужна другая проверка.

Практика

Задачи с решением

Два узла степени два

Условие. n=4, степени меток равны 2,2,1,1. Найдите число деревьев.

Решение. Код длины 2 содержит по одной метке 1 и 2. Коды 12 и 21 дают 2!/(1!1!)=2 дерева.

Ответ. 2 дерева.

Заданный центр звезды

Условие. n=5, степени 4,1,1,1,1. Сколько деревьев?

Решение. Код длины 3 содержит только метку 1, то есть 111. Формула 3!/3!=1.

Ответ. Одно дерево с центром 1.

Дополнительные источники

  • https://ptwiddle.github.io/MAS341-Graph-Theory-2017/lecturenotes/lecture8.html
  • https://www.cs.cornell.edu/jeh/book.pdf

Связанные формулы

Математика

Хроматический многочлен графа: правило удаления и стягивания

$P_G(k)=P_{G-e}(k)-P_{G/e}(k)$

Хроматический многочлен P_G(k) считает правильные раскраски вершин графа в k цветов. Правило удаления и стягивания выражает его через два меньших графа и позволяет считать ответ рекурсивно.

Информатика

Алгоритм A*: кратчайший путь по оценке f=g+h

$f(v)=g(v)+h(v)$

Алгоритм A* выбирает вершину по сумме уже пройденной стоимости g и допустимой оценки оставшегося пути h. При не завышающей эвристике он находит оптимальный маршрут и обычно просматривает меньше вершин, чем поиск Дейкстры.

Математика

Теорема Кирхгофа: число остовов через лапласиан

$\tau(G)=\det L^{(i)},\qquad L=D-A$

Число остовных деревьев неориентированного графа равно определителю любого главного минора его лапласиана. Теорема Кирхгофа заменяет перебор связных подграфов одним матричным вычислением.

Математика

Формула Кэли: число деревьев с помеченными вершинами

$T_n=n^{n-2},\qquad n\ge2$

Формула Кэли считает неориентированные деревья на заданных n различных вершинах: связные графы без циклов. Метки вершин сохраняются, а расположение рисунка на плоскости не создаёт новых деревьев.