ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА. ПРИЛОЖЕНИЕ

Рассмотрена структура некоторых классов турниров, состоящих из одних королей, и их количество. Вершина v турнира называется королём, если длина пути из v до любой другой вершины составляет не более чем 2. Турнир называется простым, если его решётка конгруэнций двухэлементна и содержит только тождественную и универсальную конгруэнции. Основной результат работы состоит в том, что турниры, состоящие из одних королей, не являются простыми.

Представлен обзор квазициклических альтернантных кодов и их структурный анализ относительно классификации автоморфизмов. Детализированы методы восстановления структурной информации о коде. Привлекательность рассматриваемого семейства кодов заключается в его возможном криптографическом приложении и, как следствие, в уменьшении длины ключа постквантовых схем на кодах, исправляющих ошибки. К тому же данный метод построения кодов является универсальным и может быть применён для получения альтернантных кодов квазициклических алгеброгеометрических кодов, ассоциированных с произвольной кривой с известной группой автоморфизмов. Однако, как показано в работе, ввиду особенностей построения квазициклических альтернантных кодов возникает возможность редукции ключевой безопасности оригинального кода к ключевой безопасности кода с меньшими параметрами, который может не являться стойким к структурной атаке.

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