Анотація:
У застосуваннях теорії графів широку популярність отримала задача про паросполучення.
Вона полягає в знаходженні в заданому графі паросполучення з найбільшою кількістю ребер –
максимального паросполучення. Узагальненям цієї задачі є задача про зважене паросполучення.
Класичний алгоритм Едмондса для знаходження найбільшого зваженого паросполучення у
недводольному графі характеризується трудомісткістю O(V4). Відома задача про зважене
паросполучення у довільному графі H з n вершинами зводиться до однієї з задач про
паросполучення для дводольного графа з 2n вершинами. Максимальне паросполучення графа H з мінімальною сумою ваг ребер, заданих матрицею [c ] , знаходиться за час (O n3) після
впорядкування за незменшенням значень c, розташованих над головною діагоналлю.
Анотація (англ.):
In the applications of graph theory, the matching task has received a wide recognition. It consists in determination in a given graph matching with the highest number of edges i.e. the maximum matching. A generalization of this problem is a problem in the weighted matching. Classic Edmonds algorithm for finding the maximum weighted matching in non-bipartite graph is characterized by complexity A well-known problem of the weighted matching in an arbitrary graph with tops reduced to one of the tasks of the matching for a dicotyledonous graph with tops. Maximal matching of the graph with the minimum sum of scales of the ribs set by a matrix is found in a time after organization on the undecrease of values , located above the main diagonal.
