ОБЧИСЛЮВАЛЬНА СКЛАДНІСТЬ ДЕЯКИХ АЛГОРИТМІВ НА ГРАФАХ

Анотація

Розглянуто задачу обчислення складності алгоритму будови максимального простого
ланцюга графа. Викладено теоретичні міркування щодо обчислення складності для
рекурсивного алгоритму будови максимального ланцюга. Опрацьовано метод обчислення
кількості операцій, потрібних для будови ланцюгів. Зроблено висновки щодо складності
алгоритму. Викладено результати практичного обчислення складності для тестових графів.
Ключові слова: граф, простий ланцюг, максимальний ланцюг, алгоритм, складність.