Гришанович Т. О. Ефективні алгоритми на арифметичних графах

Дисертація присвячена дослідженню числових графів та ефективних алгоритмів на них. Досліджено теоретичні питання складності алгоритмів. Розглянуто такі підкласи числових графів як арифметичні графи. Доведена актуальність розробки алгоритмів на числових графах. Для таких графів було розроблено та реалізовано на мові програмування новий алгоритм декомпозиції графів за їх вершинами - алгоритм розкладання графів за допомогою їхніх кістяків. Показано, що цей алгоритм забезпечує більшу ефективність за часом як для традиційних способів подання графів, так і для натуральних арифметичних графів. У роботі адаптовано наступні алгоритми відшукання гамільтонових циклів у графах для числових графів: алгоритм із поверненням, Approx-TSP(G), алгоритм із поліноміальним часом. Досліджено характеристики таких алгоритмів. Показано, що числові графи дозволяють покращити оцінки часової складності алгоритмів. Побудовано програмне забезпечення у візуальному середовищі програмування, яке дозволяє розкладати граф за розробленим алгоритмом декомпозиції за умови подання графу у вигляді матриці суміжності та натурального арифметичного графу. А також здійснює відшукання гамільтонових циклів на арифметичних графах, використовуючи адаптовані алгоритми.