50491

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Спектральные и комбинаторные свойства редуцированных графов Де Брейна

DOI: 

10.21681/2311-3456-2018-4-70-76

Наименование источника: 

  • Вопросы кибербезопасности

Обозначение и номер тома: 

№ 4(28)

Город: 

  • Москва

Издательство: 

  • АО НПО "Эшелон", ФБУ " НЦПИ при Минюсте России"

Год издания: 

2018

Страницы: 

70-76
Аннотация
В статье предложен класс обобщенных графов де Брейна, для которого вычислены спектры и ряд комбинаторных характеристик, включая их диаметр, число петель и циклов длины 2, а также число остовных деревьев, эйлеровых и гамильтоновых циклов. Установлено, что рассматриваемый класс графов замкнут относительно операции построения реберного графа. Указанные свойства указывают на целесообразность применения таких графов при проектировании подсистем контроля защищенности информационных систем, количество элементов которых является составным числом. Это обусловлено тем, что для подсистемы контроля, использующих архитектуру графа, обладающнго установленными свойстами, можно обеспечить эффективный доступ ко всем элементам системы в целом, ее масштабируемость, гибкую настройку маршрутов обхода элементов с минимальным риском зацикливания. При исследовании влияния числовых параметров рассматриваемых графов на их свойства установлено, что свойство единственности пути заданной длины сохраняется только для «обычных» графов де Брейна. Для получения указанных результатов разработан новый способ вычисления характеристического многочлена k-циркулянтной матрицы в терминах элементов ее первой строки. Это позволило также уточнить ряд известных результатов и упростить процедуры вычисления характеристического многочлена указанных матриц. Ключевые слова: регистр сдвига, граф де Брейна, k-циркулянт, спектр матрицы.

Библиографическая ссылка: 

Максимовский А.Ю., Мельников С.Ю. Спектральные и комбинаторные свойства редуцированных графов Де Брейна // Вопросы кибербезопасности. 2018. № 4(28). С. 70-76.