Задачі на графах

Abstract

Дипломна робота присвячена теоретичному та практичному дослідженню задач на графах як важливої частини дискретної математики та інформатики. Метою дослідження є аналіз основних типів задач на графах, вивчення алгоритмів їх розв’язування та можливостей практичного застосування в різних галузях. У роботі охарактеризовано базові поняття теорії графів: вершини, ребра, шляхи, цикли, дерева, орієнтовані та неорієнтовані графи. Подано класифікацію графів за структурними властивостями та особливостями задач. Розглянуто типові задачі: пошук найкоротшого шляху, побудова мінімального остовного дерева, визначення ейлерового і гамільтонового циклів, знаходження компонент зв’язності тощо. Особливу увагу приділено класичним алгоритмам: пошуку в глибину (DFS), пошуку в ширину (BFS), алгоритмам Дейкстри, Прима, Крускала, Флойда–Уоршелла. Проаналізовано їхню складність, ефективність та застосовність до реальних задач. Також розглянуто сучасні підходи, включно з евристичними та чисельними методами.