• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
ФИО студента
Название работы
Руководитель
Факультет
Программа
Оценка
Год защиты
Линовицкая Арина Дмитриевна
Линейный алгоритм для решения задачи о минимальном остовном дереве в минорно-замкнутых классах графов
8
2019
Тема дипломной работы — «Линейные алгоритмы для решения задачи о минимальном остовном дереве в минорно-замкнутых классах графов».

Задача состоит в том, чтобы показать существуют ли алгоритмы поиска MST, которые работают за линейное время для любого нетривиального класса графов, замкнутых на минорах, так как для общих графов данный вопрос по-прежнему остается открытым.

Цель работы: изучить и реализовать два алгоритма для поиска минимального остовного дерева в классе графов, замкнутых на минорах, в частности на планарных графах, и убедиться, что они выполняют свою задачу за линейное время и работают лучше других известных алгоритмов.

Исходя из поставленных задач и целей, в дипломной работе была изучена научная литература и другие источники информации по выбранной теме, проанализированы основные определения и теоремы, необходимые для понимания алгоритмов. В работе приведено доказательство того, что алгоритмы работают за линейное время. В практической части первоначально была создана функция генерации случайных планарных графов. После чего реализованы два алгоритма поиска MST в классе графов, замкнутых на минорах, и рассчитано время работы реализованных алгоритмов, на котором наглядно убедились в линейности выполнения задачи для двух алгоритмов. И на последнем шаге на определенно заданном планарном графе были реализованы наши два алгоритма и известные алгоритмы: Прима, Краскала и Борувки, и с ростом генерируемых вершин и ребер было произведено сравнение быстродействия всех алгоритмов.

Актуальность данной научной работы обуславливается большим практическим применением, так как теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем.
Текст работы (работа добавлена 21 мая 2019г.)

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Расширенный поиск ВКР