Diameter Search Algorithms for Directed Cayley Graphs
Loading...
Date
2021-05
Authors
Olshevskyi, Maksym
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
It is considered a well known diameter search problem for finite groups. It can be formulated as follows: find the maximum possible diameter of the group over its system of generators. The diameter of a group over a specific system of generators is the diameter of the corresponding Cayley graph. In the paper a closely related problem is considered. For a specific system of generators find the diameter of corresponding Cayley graph. It is shown that the last problem is polynomially reduced to the problem of searching the minimal decomposition of elements over a system of generators.
It is proposed five algorithms to solve the diameter search problem: simple down search algorithm, fast down search algorithm, middle down search algorithms, homogeneous down search algorithm and homogeneous middle down search algorithm.
Розглянуто добре відому задачу пошуку діаметра скінченної групи. Вона формулюється так: знайти найбільший серед діаметрів групи відносно її систем твірних. Діаметром групи є діаметр графа Келі, що будується на основі групи та її системи твірних. У цій роботі розглянуто підзадачу задачі пошуку діаметра групи, а саме, задачу знаходження діаметра групи відносно заданої системи твірних. Показано, що ця задача поліноміально зводиться до задачі пошуку мінімальних розкладів елементів. Для розв’язання задачі знаходження діаметра групи відносно заданої системи твірних запропоновано п'ять алгоритмів: простий алгоритм пошуку вниз, швидкий алгоритм пошуку вниз, серединний алгоритм пошуку вниз, однорідний алгоритм пошуку вниз та однорідний серединний алгоритм пошуку вниз. Перші два алгоритми є універсальними, а інші вимагають виконання додаткових умов на системи твірних. Для алгоритму серединного спуску введено поняття строго зростаючої системи твірних. За виконання цієї умови, пошук мінімальних розкладів потенційних найдовших розкладів можна почати одразу ж із певної множини. Введено окрему теорію однорідності. В ній розглядануто ряди груп та їх систем твірних, що задовольняють певним додатковим умовам. Введено властивість однорідності таких рядів та відношення еквівалентності їх елементів. Основною метою введення такого відношення є збереження розкладів її елементів в одному класі. Ця властивість дає можливість обраховувати мінімальний розклад лише для представника класу еквівалентності. Для алгоритмів однорідного пошуку вниз та однорідного серединного пошуку вниз необхідною умовою застосування є належність групи до однорідного генеративного ряду груп. Тоді задача знаходження мінімальних розкладів елементів зводиться до знаходження мінімальних розкладів представників класів еквіваленції. Показано, що всі описані алгоритми є коректними. Зроблено оцінки складності їх роботи.
Розглянуто добре відому задачу пошуку діаметра скінченної групи. Вона формулюється так: знайти найбільший серед діаметрів групи відносно її систем твірних. Діаметром групи є діаметр графа Келі, що будується на основі групи та її системи твірних. У цій роботі розглянуто підзадачу задачі пошуку діаметра групи, а саме, задачу знаходження діаметра групи відносно заданої системи твірних. Показано, що ця задача поліноміально зводиться до задачі пошуку мінімальних розкладів елементів. Для розв’язання задачі знаходження діаметра групи відносно заданої системи твірних запропоновано п'ять алгоритмів: простий алгоритм пошуку вниз, швидкий алгоритм пошуку вниз, серединний алгоритм пошуку вниз, однорідний алгоритм пошуку вниз та однорідний серединний алгоритм пошуку вниз. Перші два алгоритми є універсальними, а інші вимагають виконання додаткових умов на системи твірних. Для алгоритму серединного спуску введено поняття строго зростаючої системи твірних. За виконання цієї умови, пошук мінімальних розкладів потенційних найдовших розкладів можна почати одразу ж із певної множини. Введено окрему теорію однорідності. В ній розглядануто ряди груп та їх систем твірних, що задовольняють певним додатковим умовам. Введено властивість однорідності таких рядів та відношення еквівалентності їх елементів. Основною метою введення такого відношення є збереження розкладів її елементів в одному класі. Ця властивість дає можливість обраховувати мінімальний розклад лише для представника класу еквівалентності. Для алгоритмів однорідного пошуку вниз та однорідного серединного пошуку вниз необхідною умовою застосування є належність групи до однорідного генеративного ряду груп. Тоді задача знаходження мінімальних розкладів елементів зводиться до знаходження мінімальних розкладів представників класів еквіваленції. Показано, що всі описані алгоритми є коректними. Зроблено оцінки складності їх роботи.
Description
Keywords
Cayley graph, diameter of group, system of generators, article, граф Келі, діаметр групи, система твірних
Citation
Olshevskyi M. Diameter search algorithms for directed Cayley graphs / Maksym Olshevskyi // Могилянський математичний журнал. - 2021. - Т. 4. - С. 7-19. - https://doi.org/10.18523/2617-7080420217-19