Математика / Дискретная математика
Код Прюфера: число деревьев с заданными степенями
В коде Прюфера метка вершины встречается на единицу меньше её степени. Поэтому число помеченных деревьев с фиксированной степенью каждой вершины равно мультиномиальному коэффициенту.
Формула
Рёбра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), но данная статья отвечает на более узкий вопрос о фиксированных степенях каждой вершины.
Как пользоваться формулой
- Привяжите требуемую степень к каждой метке и проверьте положительность целых d_i, а затем сумму 2(n−1).
- Вычтите единицу из каждой степени, получив кратности меток в коде; их сумма должна равняться n−2.
- Найдите мультиномиальное число(n−2)!/∏(d_i−1)!, используя 0!=1 для всех листьев дерева.
- Для малого 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) считает правильные раскраски вершин графа в k цветов. Правило удаления и стягивания выражает его через два меньших графа и позволяет считать ответ рекурсивно.
Информатика
Алгоритм A*: кратчайший путь по оценке f=g+h
Алгоритм A* выбирает вершину по сумме уже пройденной стоимости g и допустимой оценки оставшегося пути h. При не завышающей эвристике он находит оптимальный маршрут и обычно просматривает меньше вершин, чем поиск Дейкстры.
Математика
Теорема Кирхгофа: число остовов через лапласиан
Число остовных деревьев неориентированного графа равно определителю любого главного минора его лапласиана. Теорема Кирхгофа заменяет перебор связных подграфов одним матричным вычислением.
Математика
Формула Кэли: число деревьев с помеченными вершинами
Формула Кэли считает неориентированные деревья на заданных n различных вершинах: связные графы без циклов. Метки вершин сохраняются, а расположение рисунка на плоскости не создаёт новых деревьев.