МЕТОД НАЙКОРОТШИХ ЗБІЛЬШУЮЧИХ ШЛЯХІВ У ЗАДАЧАХ ПРО ПАРОСПОЛУЧЕННЯ

Abstract

У застосуваннях теорії графів широку популярність отримала задача про паросполучення. Вона полягає в знаходженні в заданому графі паросполучення з найбільшою кількістю ребер – максимального паросполучення. Узагальненям цієї задачі є задача про зважене паросполучення. Класичний алгоритм Едмондса для знаходження найбільшого зваженого паросполучення у недводольному графі характеризується трудомісткістю O(V4). Відома задача про зважене паросполучення у довільному графі H з n вершинами зводиться до однієї з задач про паросполучення для дводольного графа з 2n вершинами. Максимальне паросполучення графа H з мінімальною сумою ваг ребер, заданих матрицею [c ] , знаходиться за час (O n3) після впорядкування за незменшенням значень c, розташованих над головною діагоналлю.