Поиск наибольшей упаковки путей малой длины в графах

В данной работе исследована проблема упаковки графов. Упаковка графа является широко известной задачей теории графов, и имеет много применений в области программирования и математики. В общем можно выделить три основных направления: упаковка графов малого размера, упаковка графов с ограниченной степенью вершин, упаковка графов с дополнительными условиями в перестановках. Считается, что главным толчком и одним из основных открытий в теории об упаковке графов было сделано Боллобашем и Элдриджем в 1978 году. Также общие сведения об упаковке графов можно найти в литературе Возняка и Япа. Задача о паросочетании (P2-упаковка) полиномиально разрешима. Если же S имеет граф с компонентой связности размера 3 и более, тогда задача является NP-полной . На сегодняшний день данная проблема изучена широко, имеется большое количество приближенных алгоритмов. В настоящее время главной целью является разработка более точных алгоритмов, которые могли бы работать не только для ограниченных в размере графов и упаковок. Более того стремление к уменьшению времени работы таких алгоритмов приветствуется. В данном исследование разработаны два приближенных алгоритма; подробно разобраны на примерах; приведены контрпримеры, когда алгоритм работает неверно; проведены эксперименты работы алгоритмов на данных графах с сравнением. Также в данной работе содержится реализация разработанных алгоритмов на одном из языке программирования C++, приведены скриншоты работы программы.