RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2024, выпуск 17, страницы 135–137 (Mi pdma664)

Прикладная теория кодирования, автоматов и графов

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

М. Б. Абросимов, Д. А. Томилов

Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского

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

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

УДК: 519.17

DOI: 10.17223/2226308X/17/34



© МИАН, 2024