Параллельные алгоритмы оптимизации на графах Кэли

• Автор: Кузнецова, Александра Сергеевна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Красноярск
• Количество страниц: 116 с. : ил.

Содержание
Введение

1 Основные определения и понятия

1.1. Группы

1.1.1. Симметрическая группа 5„

1.2. Графы

1.2.1. Графы Кэли

1.3. Последовательный алгоритм А-

1.3.1. Примеры

2 Исследование графов симметрических групп

2.1. Постановка задачи

2.2. Параллельная версия алгоритма А-1 для графов групп 5„
2.3. Анализ компьютерных вычислений
3 Исследование графов конечных двупорожденных групп периода 5
3.1. Постановка задачи
3.2. Быстрое произведение элементов группы
3.3. Параллельная версия алгоритма А-1 для графов групп Вк
3.4. Изучение графов для симметричного порождающего множества
3.5. Изучение графов для несимметричного порождающего множества
Заключение
Список литературы
Работы автора по теме диссертации
Приложение

Введение
Актуальность темы. Определение графа Кэли было дано известным английским математиком Артуром Кэли в 1878 году для представления алгебраической группы, заданной фиксированным множеством порождающих элементов [11].
В последние десятилетия теория графов Кэли развивается как отдельная большая ветвь теории графов. Графы Кэли находят применение как в математике, так и за ее пределами [42]. Заметим, что известная задача по определению так называемого “числа Бога“ кубика Рубика 3 х 3 х 3, т. е. минимального количества поворотов граней кубика за которое его можно “собрать“ из любого начального положения, сводится к исследованию соответствующего графа Кэли [44].
Неожиданное применение графы Кэли нашли в информационных технологиях после пионерской работы 1986 года С. Эйкерса и Б. Криш-намурти [25], которые впервые предложили применять указанные графы для представления компьютерных сетей, в том числе для моделирования топологий многопроцессорных вычислительных систем (МВС) — суперкомпьютеров [1,4,14,24]. С тех пор данное направление активно развивается. Это связано с тем, что графы Кэли имеют много привлекательных свойств, из которых выделим их регулярность, вершинно-транзитивность, малые диаметр и степень при достаточно большом количестве вершин в графе. Кстати, такие базовые топологии сети, как

“кольцо“ и “гиперкуб“ [2], являются графами Кэли. Среди множества работ [11,26-31,33,35,39-41,43,45-47,51,52,56,57] отдельно стоит отметить статью С. Шайбелла и Р. Стаффорда 1992 года [52], в которой показано, что наряду с диаметром графа Кэли, очень важное значение для производительности МВС имеет также средний диаметр графа.
Для вычисления диаметра графа требуется решить ряд задач дискретной оптимизации [15]. В первую очередь необходимо найти кратчайшие пути, связывающие все пары вершин в графе. Затем из всех кратчайших путей выбрать наибольший путь, длина которого и будет являться диаметром графа. Соответственно, средний диаметр графа будет равен среднему арифметическому всех длин кратчайших путей.
Как известно, если граф задан в виде матрицы длин ребер, то задача по вычислению диаметра графа решается за полиномиальное время (например, при помощи алгоритма Дейкстры [15]). Специфика же графов Кэли такова, что в исходной ситуации известны только порождающие элементы и определяющие соотношения группы. Чтобы вычислить диаметр графа Кэли необходимо решить следующие задачи дискретной оптимизации. Сначала требуется найти для каждого элемента группы минимальное слово, т. е. представить элемент в виде комбинации из образующих наименьшей длины. После чего вычислить максимальную длину минимальных слов, которая и будет являться диаметром графа Кэли.
Поиск минимального слова в большой конечной группе является хотя и разрешимой, но достаточно сложной проблемой. Это связано с тем, что в общем случае задача по определению минимального слова в группе, а следовательно и диаметра графа Кэли, как показали С. Ивен и О. Голдрейх в 1981 году, является ЫР-трудной [32]. Так, при вы-числениии в 2010 году упомянутого выше “числа Бога“, которое равно

Рис. 2.6. График функции роста графа Г
Рис. 2.7. График функции роста графа Ги