• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
ФИО студента
Название работы
Руководитель
Факультет
Программа
Оценка
Год защиты
Грязнов Артём Александрович
Поиск наибольшей упаковки путей малой длины в графах
2019
В данной работе исследована проблема упаковки графов. Упаковка графа является широко известной задачей теории графов, и имеет много применений в области программирования и математики. В общем можно выделить три основных направления: упаковка графов малого размера, упаковка графов с ограниченной степенью вершин, упаковка графов с дополнительными условиями в перестановках. Считается, что главным толчком и одним из основных открытий в теории об упаковке графов было сделано Боллобашем и Элдриджем в 1978 году. Также общие сведения об упаковке графов можно найти в литературе Возняка и Япа. Задача о паросочетании (P2-упаковка) полиномиально разрешима. Если же S имеет граф с компонентой связности размера 3 и более, тогда задача является NP-полной . На сегодняшний день данная проблема изучена широко, имеется большое количество приближенных алгоритмов. В настоящее время главной целью является разработка более точных алгоритмов, которые могли бы работать не только для ограниченных в размере графов и упаковок. Более того стремление к уменьшению времени работы таких алгоритмов приветствуется.

В данном исследование разработаны два приближенных алгоритма; подробно разобраны на примерах; приведены контрпримеры, когда алгоритм работает неверно; проведены эксперименты работы алгоритмов на данных графах с сравнением. Также в данной работе содержится реализация разработанных алгоритмов на одном из языке программирования C++, приведены скриншоты работы программы.

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

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

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

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

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

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