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

ПДМ. Приложение, 2015, выпуск 8, страницы 113–114 (Mi pdma202)

Эта публикация цитируется в 2 статьях

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

Условия примитивности системы двух графов

Я. Э. Авезоваa, В. М. Фомичевbc

a Национальный исследовательский ядерный университет "МИФИ", г. Москва
b Финансовый университет при Правительстве Российской Федерации, г. Москва
c ООО "Код Безопасности", г. Москва

Аннотация: Получены достаточные условия примитивности системы двух $n$-вершинных орграфов в случае, когда один из орграфов не содержит ациклических вершин, в частности, когда содержит гамильтонов контур. Получена оценка экспонента системы двух орграфов через экспонент их произведения. Результаты могут быть использованы для оценки перемешивающих свойств итеративных функций, построенных на основе разветвления преобразования на два заданных преобразования.

Ключевые слова: примитивный граф, экспонент графа, гамильтонов цикл.

УДК: 519.6

DOI: 10.17223/2226308X/8/43



© МИАН, 2024