Паросочетания с предписанными свойствами в графах: магистерская диссертация / Алексей Павлович Гапоненко; БГУ, Факультет прикладной математики и информатики, Кафедра дискретной математики и алгоритмики; науч. рук. Орлович Ю. Л.

Abstract

Объект и предмет исследования: к объекту исследования относятся различные типы паросочетаний. К предмету исследования относятся сложностной статус задач, связанных с паросочетаниями, и характеризации рассматриваемых классов графов. Цель работы: получение новых и обобщение уже известных результатов, связанных с несвязными, к-дистанционными и индуцированными паросочетаниями. Результаты: доказана полиномиальная разрешимость задачи нахождения наибольшего несвязного паросочетания в классе деревьев. Установлена NP-полнота задачи нахождения наибольшего индуцированного паросочетания в определённом классе графов. Получены новые результаты для взвешенных индуцированных паросочетаний, несвязных паросочетаний и к-дистанционных паросочетаний. Область применения: «Области эффективности» задач о различных видах паросочетаний - то есть классы графов, для которых указанные задачи могут быть решены за полиномиальное время.