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