Естественные и технические науки, № 1, 2015 Информатика, вычислительная техника и управление Системный анализ, управление и обработка информации Малистов А.С., кандидат технических наук, зам. руководителя отдела ЗАО «ЭЛВИС-НеоТек» АЛГОРИТМ ПОИСКА ПАРОСОЧЕТАНИЯ НАИБОЛЬШЕГО И НАИМЕНЬШЕГО ВЕСА, ПОКРЫВАЮЩЕГО ЗАДАННЫЕ ВЕРШИНЫ ПРОИЗВОЛЬНОГО ГРАФА В статье рассматривается обобщение известной задачи о построении максимального взвешенного паросочетания. <...> Предлагается быстрый алгоритм, который строит паросочетание наибольшего (наименьшего) веса в произвольном графе, покрывающее заданные вершины. <...> AN ALGORITHM FOR FINDING A MAXIMUM AND MINIMUM WEIGHTED MATCHING COVERING GIVEN VERTICES IN GENERAL GRAPHS We construct an fast algorithm for finding a maximum (minimum) weighted matching in general graphs covering given vertices of a graph. <...> Паросочетанием в графе называется множество рёбер, не имеющих общих вершин. <...> В этой статье мы обобщаем классическую задачу поиска паросочетания максимального веса в графе . <...> Кроме общей формулировки имеется три частных случая: задача поиска паросочетания в двудольных графах, известная как задача о назначениях, поиск паросочетания максимальной мощности (все ребра имеют единичный вес) или оба ограничения одновременно. <...> Последний случай известен в литературе как задача о свадьбах. <...> Во взвешенном графе каждому ребру приписан вес . <...> Можно считать, что вес ребра всегда положителен, потому что ребра с отрицательным весом не могут входить в максимальное паросочетание и их можно предварительно отбросить при решении задачи. <...> Обратим также внимание, что задача поиска минимального паросочетания эквивалентна задаче поиска максимального, если поменять знак весов для всех ребер. <...> Для положительных весов исходного графа задача поиска минимального паросочетания имеет тривиальное решение – пустое множество. <...> Однако, иногда задачу о назначениях формулируют в терминах минимизации, требуя поиска совершенного паросочетания минимального веса. <...> Совершенным паросочетанием называется паросочетание <...>