РОЗВ’ЯЗАННЯ ПРИКЛАДНИХ ЗАДАЧ З ВИКОРИСТАННЯМ БАЗОВИХ АЛГОРИТМІЧНИХ ПРИМІТИВІВ ТЕОРІЇ ГРАФІВ

Анотація

Розглянуто можливість постановки прикладних задач у термінах теорії графів. Зокрема, розглянуто задачі про оптимальну структуру підприємства, контроль за фінансовими операціями, визначення оптимальної послідовності робіт. Реалізовано підхід до розв’язання таких задач з використанням алгоритмічних примітивів на графах. Застосування графів як моделей багатьох прикладних задач зумовлене як наочністю поняття графа, так і наявністю точних алгоритмів на графах з поліноміальною складністю.Процес розв’язання задачі побудови оптимальної структури послідовно включає обчислення сильно зв’язних компонент на графі задачі, побудову графа компонентів і топологічне сортування графа компонентів з метою переходу до лінійної структури. Під оптимальною структурою підприємства розуміється лінійне впорядкування його підрозділів. Метод розв’язання задачі контролю за фінансовими операціями базується на властивостях пошуку у глибину для ациклічного графа. Класифікація ребер лісу пошуку у глибину дозволяє робити припущення про приховані зв’язки за наявності зворотних ребер. Варто зазначити, що запропонована методика не дає відповіді про кількісний характер зв’язку, тільки фіксує його як факт. Частинним випадком загальної задачі лінійного програмування є задача визначення послідовності виконання робіт, задана системою різницевих обмежень.Розв’язання системи різницевих обмежень зводиться до обчислення ваги найкоротшого шляху у відповідному графі обмежень. Для обчислення найкоротшого шляху з однієї вершини застосовано алгоритм Беллмана – Форда, застосування якого дозволяє отримати результат навіть за наявності ребер від’ємної ваги.Коректність теоретичних міркувань підтверджується практичними обчисленнями за допомогою спеціально розробленого програмного забезпечення. Обчислення проводились у середовищі “Mathcad v. 13”. Розроблено відповідні процедури STRONG_COMP, DFS_CTRL, BELL_FORD_CONST.