Линейный алгоритм для решения задачи о минимальном остовном дереве в минорно-замкнутых классах графов

Тема дипломной работы — «Линейные алгоритмы для решения задачи о минимальном остовном дереве в минорно-замкнутых классах графов». Задача состоит в том, чтобы показать существуют ли алгоритмы поиска MST, которые работают за линейное время для любого нетривиального класса графов, замкнутых на минорах, так как для общих графов данный вопрос по-прежнему остается открытым. Цель работы: изучить и реализовать два алгоритма для поиска минимального остовного дерева в классе графов, замкнутых на минорах, в частности на планарных графах, и убедиться, что они выполняют свою задачу за линейное время и работают лучше других известных алгоритмов. Исходя из поставленных задач и целей, в дипломной работе была изучена научная литература и другие источники информации по выбранной теме, проанализированы основные определения и теоремы, необходимые для понимания алгоритмов. В работе приведено доказательство того, что алгоритмы работают за линейное время. В практической части первоначально была создана функция генерации случайных планарных графов. После чего реализованы два алгоритма поиска MST в классе графов, замкнутых на минорах, и рассчитано время работы реализованных алгоритмов, на котором наглядно убедились в линейности выполнения задачи для двух алгоритмов. И на последнем шаге на определенно заданном планарном графе были реализованы наши два алгоритма и известные алгоритмы: Прима, Краскала и Борувки, и с ростом генерируемых вершин и ребер было произведено сравнение быстродействия всех алгоритмов. Актуальность данной научной работы обуславливается большим практическим применением, так как теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем.