3

Как дерево в вектор каким-нибудь однозначным образом можно вложить метрическое пространство? Интересуют не сложные эмбеддинги, а просто преобразование дерева в вектор однозначно. Детерминированный алгоритм.

9
  • 1
    Код Прюфера, может быть? Или вам нужно не хранить, а использовать для каких-то вычислений? И у вас именно бинарное дерево или вы просто так тег поставили?
    – EzikBro
    12 мар 2021 в 8:14
  • Уважаемые закрывающие вопросы. Пишите причину!!! 12 мар 2021 в 10:09
  • Давайте тег бинарное дерево, всё-таки, уберу. Не совесем корректно будет приводить его к бинарному. Хотя, если вы предложите процедуру для бинарного -- это будет круто. Код Прюфера подразумевает наличие нумерации вершин. Её нужно как-то придумать. Иными словами. Хотелось бы научиться преобразовывать деревья из n вершин в вектор, для которых свойственно следующее отношение: два дерева изоморфны тогда и только тогда, когда их векторы равны. Здесь можно вводить приближённые отношения. Сейчас я выбрал qr-алгоритм и сравнение собственных чисел матрицы смежности. 12 мар 2021 в 10:11
  • Для бинарных есть нумерация Каталана. 12 мар 2021 в 10:41
  • @StanislavVolodarskiy если вы про числа каталана. То это количество деревьев. Или есть какая-то отдельная история про нумерацию? Скиньте ссылку тогда пожалуйста 12 мар 2021 в 10:45

1 ответ 1

1

Самое тупое - дерево - это граф, граф - это матрица инцидентности, матрицу можно развернуть в вектор.

Чтобы отображение было однозначным, матрицу нужно пересортировать (переставить строки и столбики) так, чтобы на диагонали было как можно больше единиц

10
  • Перенумеруйте вершины в матрице смежности и увас получится два вектора, которые соответсвуют одному графу. Ответ не годится 12 мар 2021 в 11:00
  • Что значит "перенумеруйте"? Что вы хотите от графа-то сохранить, топологию?
    – gbg
    12 мар 2021 в 11:18
  • точно, хочу топологию. 12 мар 2021 в 11:26
  • слушайте, да. По поводу сортировки -- норм. Тема. Подумаю. Кажется, то, что нужно. 12 мар 2021 в 11:26
  • ну вот если мне склероз не изменяет, приведение матрицы к такому вот виду делается вполне однозначным образом
    – gbg
    12 мар 2021 в 11:27

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.