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

Анотація

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

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

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

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

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