О применении условий локальной примитивности и оценок локальных экспонентов орграфов | Прикладная дискретная математика. 2016. № 4(34). DOI: 10.17223/20710410/34/7

В развитие матрично-графового подхода к исследованию перемешивающих свойств итеративных преобразований С.Н. Кяжиным, В.М. Фомичевым были введены понятия локальной примитивности и локального экспонента орграфа, обобщающие известные понятия примитивности и экспонента и позволяющие расширить область приложений, и получены универсальный критерий i х j-прими-тивности и универсальная оценка i х j-экспонента орграфа. Однако применение данных результатов не всегда удобно, так как затруднено общностью математической модели. В данной работе для различных классов орграфов, определяемых взаимным расположением компонент сильной связности и их строением, получены условия i х j-примитивности и оценки (в ряде случаев точные значения) i х j-экспонента, улучшающие универсальную оценку. Условия локальной примитивности и величина оценок локальных экспонентов определяются свойствами множества длин путей из i в j в перемешивающем орграфе, а также длинами контуров, содержащихся в компонентах сильной связности, через которые проходят данные пути. Полученные результаты значительно упрощают для исследователя распознавание локальной примитивности и получение оценок локальных экспонентов конкретных перемешивающих орграфов преобразований, возникающих, в том числе, в криптографических приложениях.