Как дерево в вектор каким-нибудь однозначным образом можно вложить метрическое пространство? Интересуют не сложные эмбеддинги, а просто преобразование дерева в вектор однозначно. Детерминированный алгоритм.
-
1Код Прюфера, может быть? Или вам нужно не хранить, а использовать для каких-то вычислений? И у вас именно бинарное дерево или вы просто так тег поставили?– EzikBro12 мар 2021 в 8:14
-
Уважаемые закрывающие вопросы. Пишите причину!!!– hedgehogues12 мар 2021 в 10:09
-
Давайте тег бинарное дерево, всё-таки, уберу. Не совесем корректно будет приводить его к бинарному. Хотя, если вы предложите процедуру для бинарного -- это будет круто. Код Прюфера подразумевает наличие нумерации вершин. Её нужно как-то придумать. Иными словами. Хотелось бы научиться преобразовывать деревья из n вершин в вектор, для которых свойственно следующее отношение: два дерева изоморфны тогда и только тогда, когда их векторы равны. Здесь можно вводить приближённые отношения. Сейчас я выбрал qr-алгоритм и сравнение собственных чисел матрицы смежности.– hedgehogues12 мар 2021 в 10:11
-
Для бинарных есть нумерация Каталана.– Stanislav Volodarskiy12 мар 2021 в 10:41
-
@StanislavVolodarskiy если вы про числа каталана. То это количество деревьев. Или есть какая-то отдельная история про нумерацию? Скиньте ссылку тогда пожалуйста– hedgehogues12 мар 2021 в 10:45
|
Показать ещё 4 комментария
1 ответ
Самое тупое - дерево - это граф, граф - это матрица инцидентности, матрицу можно развернуть в вектор.
Чтобы отображение было однозначным, матрицу нужно пересортировать (переставить строки и столбики) так, чтобы на диагонали было как можно больше единиц
-
Перенумеруйте вершины в матрице смежности и увас получится два вектора, которые соответсвуют одному графу. Ответ не годится 12 мар 2021 в 11:00
-
Что значит "перенумеруйте"? Что вы хотите от графа-то сохранить, топологию?– gbg12 мар 2021 в 11:18
-
-
слушайте, да. По поводу сортировки -- норм. Тема. Подумаю. Кажется, то, что нужно. 12 мар 2021 в 11:26
-
ну вот если мне склероз не изменяет, приведение матрицы к такому вот виду делается вполне однозначным образом– gbg12 мар 2021 в 11:27