Алгоритми пошуку діаметра орієнтованих графів Келі

Автор(и)

DOI:

https://doi.org/10.18523/2617-7080420217-19

Ключові слова:

граф Келі, діаметр групи, система твірних

Анотація

Розглянуто добре відому задачу пошуку діаметра скінченної групи. Вона формулюється так: знайти найбільший серед діаметрів групи відносно її систем твірних. Діаметром групи є діаметр графа Келі, що будується на основі групи та її системи твірних. У цій роботі розглянуто підзадачу задачі пошуку діаметра групи, а саме, задачу знаходження діаметра групи відносно заданої системи твірних. Показано, що ця задача поліноміально зводиться до задачі пошуку мінімальних розкладів елементів.
Для розв’язання задачі знаходження діаметра групи відносно заданої системи твірних запропоновано п'ять алгоритмів: простий алгоритм пошуку вниз, швидкий алгоритм пошуку вниз, серединний алгоритм пошуку вниз, однорідний алгоритм пошуку вниз та однорідний серединний алгоритм пошуку вниз.
Перші два алгоритми є універсальними, а інші вимагають виконання додаткових умов на системи твірних.

Для алгоритму серединного спуску введено поняття строго зростаючої системи твірних. За виконання цієї умови, пошук мінімальних розкладів потенційних найдовших розкладів можна почати одразу ж із певної множини.

Введено окрему теорію однорідності. В ній розглядануто ряди груп та їх систем твірних, що задовольняють певним додатковим умовам. Введено властивість однорідності таких рядів та відношення еквівалентності їх елементів. Основною метою введення такого відношення є збереження розкладів її елементів в одному класі. Ця властивість дає можливість обраховувати мінімальний розклад лише для представника класу еквівалентності.

Для алгоритмів однорідного пошуку вниз та однорідного серединного пошуку вниз необхідною умовою застосування є належність групи до однорідного генеративного ряду груп. Тоді задача знаходження мінімальних розкладів елементів зводиться до знаходження мінімальних розкладів представників класів еквіваленції.

Показано, що всі описані алгоритми є коректними. Зроблено оцінки складності їх роботи.

Біографія автора

Maksym Olshevskyi , Київський національний університет імені Тараса Шевченка

Аспірант механіко-математичного факультету Київського національного університету ім. Тараса Шевченка. Сфера наукових інтересів: теорія груп, теорія графів, теорія обчислень.

Посилання

Laszlo Babai and Akos Seress, ``On the diameter of permutation groups'', European Journal of Combinatorics. 13 (4), 231-243 (1992).

Harald A. Helfgott, ``Growth and generation in '', Annals of Mathematics. 167, 601-623 (2008).

Emmanuel Breuillard and Ben Green and Terence Tao, Approximate subgroups of linear groups (2010).

Laszlo Pyber and Endre Szabo, Growth in finite simple groups of Lie type of bounded rank} (2011).

Harald A. Helfgott and Akos Seress, ``On the diameter of permutation groups'', Ann. Math. 179 (2), 611- 658 (2014).

S. Even and O. Goldreich, ``The minimum-length generator sequence problem is NP-hard'', Journal of Algorithms. 2 (3), 311-313 (1981).

S. Akers and B. Krishnamurthy and D. Harel, The Star Graph: An Attractive Alternative to the n-Cube (1987).

Thomas H. Cormenand, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms. Third Edition (The MIT Press, 2009).

##submission.downloads##

Опубліковано

2022-05-19