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