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

Открытие бесконечных семейств оптимальных двухконтурных кольцевых сетей с заданным шаблоном образующих

Э. А. Монахова, О. Г. Монахов

Институт вычислительной математики и математической геофизики СО РАН, г. Новосибирск, Россия

Аннотация: Оптимальные кольцевые циркулянтные сети степени четыре рассматриваются как модели надёжных сетей связи с минимальными задержками для сетей на кристалле и мультипроцессорных кластерных систем. Проведён поиск аналитически задаваемых бесконечных семейств оптимальных графов на основе анализа базы данных оптимальных описаний двухконтурных кольцевых циркулянтных сетей. Путём интеграции визуализации данных и аналитических описаний оптимальных графов построены и теоретически обоснованы новые бесконечные семейства оптимальных сетей с линейной образующей вида $s=4d+\alpha$, где $d$ — диаметр графа. Предложенный подход получения семейств оптимальных сетей является новым и представляет интерес для дальнейшего изучения свойств оптимальных двухконтурных кольцевых сетей.

Ключевые слова: датасет оптимальных сетей, неориентированные двухконтурные кольцевые сети, циркулянтные сети, минимальный диаметр.

УДК: 519.87:519.6:519.178

DOI: 10.17223/20710410/66/9