Классификация деревьев, все максимальные поддеревья которых изоморфны

Абросимов, Михаил Борисович; Томилов, Дмитрий Александрович

Классификация деревьев, все максимальные поддеревья которых изоморфны

Абросимов, Михаил Борисович, Томилов, Дмитрий Александрович

Дата публикации: 2024

Дата публикации в реестре: 2024-10-01T21:20:32Z

Аннотация:

Рассматривается задача описания деревьев, все максимальные поддеревья которых изоморфны. Приводится характеристическая теорема для таких деревьев: все максимальные поддеревья дерева изоморфны тогда и только тогда, когда все его листья подобны. Вводится класс многоуровневых звёзд. Доказывается, что этот класс совпадает с классом деревьев, все максимальные поддеревья которых изоморфны.

Ключевые слова:
графы, деревья (теория графов), реконструируемость

Тип: статьи в журналах

Источник: Прикладная дискретная математика. Приложение. 2024. № 17. С. 135-137