Том 16, номер 4, 2009 г., Стр. 47-60

УДК 519.176
Э. А. Монахова
Оптимальные обобщённые графы Петерсена

Аннотация:
В качестве модели сетей связи вычислительных систем рассмотрены обобщенные графы Петерсена. Решается задача оптимизации, состоящая в минимизации диаметра (максимальной структурной задержки в сети) при заданном числе вершин графа. Найдено отображение множества оптимальных двумерных циркулянтных сетей в класс обобщёенных графов Петерсена, сохраняющее оптимальность графа. Получены параметры описаний оптимальных обобщёенных графов Петерсена для любого порядка графа. Даёется аналитическое решение задачи поиска кратчайших путей для полученных оптимальных графов.
Ил. 2, табл. 1, библиогр. 24.

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

Монахова Эмилия Анатольевна ¹
1. Институт вычислительной математики и математической геофизики СО РАН,
пр. Акад. М. А. Лаврентьева, 6, 630090 Новосибирск, Россия
е-mail: emilia@rav.sscc.ru

Статья поступила 26 января 2009 г.
Исправленный вариант — 30 апреля 2009 г.