Исследование графов Кэли конечных двупорожденных бернсайдовых групп периода семь

Впервые определение графа Кэли было дано известным английским математиком Артуром Кэли в XIX веке для представления алгебраической группы, заданной фиксированным множеством порождающих элементов. В настоящее время графы Кэли нашли широкое применение как в математике, так и в прикладных задачах. В частности, указанные графы используются для представления компьютерных сетей, в том числе для моде- лирования топологий многопроцессорных вычислительных систем (МВС) - суперкомпьютеров. Это связано с тем, что графы Кэли имеют много привлекательных свойств, из которых выделим их регулярность, вершин- ную транзитивность, малые диаметр и степень при достаточно большом количестве вершин в графе. На- пример, такие базовые топологии сети, как кольцо, гиперкуб и тор, являются графами Кэли. Одной из широко применяемых топологий МВС является k-мерный гиперкуб. Данный граф задается k-порожденной бернсайдо- вой группой периода 2. Эта группа имеет простую структуру и равна прямому произведению k экземпляров циклической группы порядка 2. Ранее авторами уже были изучены графы Кэли групп периода 3, 4 и 5. Проведе- ны исследования по определению структуры графов Кэли некоторых конечных двупорожденных бернсайдовых групп периода 7. Вычисление диаметра графа Кэли большой конечной группы является хотя и разрешимой, но весьма сложной проблемой. Это связано с тем, что в общем случае задача по определению минимального сло- ва в группе является NP-трудной (nondeterministic polynomial). Таким образом, в наихудшем случае количество элементарных операций, которые необходимо выполнить для решения указанной задачи, представляет собой экспоненциальную функцию от количества порождающих элементов. Поэтому для эффективного решения задач на графах Кэли, имеющих большое количество вершин, необходимо применять МВС.