Перебор всех деревьев заданного размера

#algorithm #math #graph #brute-force

#алгоритм #математика #График #перебор

Вопрос:

Я часто сталкиваюсь с проблемой проверки некоторых свойств деревьев (графов) заданного размера методом перебора. Есть ли у вас какие-нибудь полезные приемы для этого? В идеале я хотел бы изучить каждый класс изоморфизма только один раз (но, в конце концов, скорость — это все, что имеет значение).

Трюки с переворачиванием битов приветствуются, поскольку n обычно меньше 32 🙂

Я прошу немного более усовершенствованные алгоритмы, чем подобные «перебирать все (n-1) подмножества ребер и проверять, образуют ли они дерево» для деревьев на n узлах.

1. Что это за дерево? Какой алгоритм вы используете в настоящее время для «обхода» дерева? О каком изоморфизме вы говорите? Вопрос очень расплывчатый

2. Общие деревья, то есть связные графы с n узлами и n-1 ребрами. Под изоморфизмом я подразумеваю en.wikipedia.org/wiki/graph_isomorphism. Я не прохожу по определенному дереву — я хочу сгенерировать список всех деревьев.

Ответ №1:

Это описано в книге Кнута «Искусство компьютерного программирования», посвященной комбинаторным алгоритмам. Если я правильно помню, это упражнение там. Поскольку у него есть решения для таких случаев, я указываю вам туда.

Ответ №2:

После некоторого поиска в Google появилось следующее описание алгоритма: http://www.cs.auckland.ac.nz/compsci720s1c/lectures/mjd/treenotes.pdf. Они адаптируют алгоритм для перечисления корневых деревьев к перечислению некорневых деревьев.

По-видимому, другие доказали, что для этого требуется только постоянное время амортизации для каждого дерева, и в PDF-файле приведены некоторые измерения производительности, демонстрирующие это.