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

Кушнір, Н.О.; Мацій, О.Б.; Скачков, В.О.; Kushnir, N.A.; Matsiy, O.B.; Skachkov, V.A.

dc.contributor.author	Кушнір, Н.О.
dc.contributor.author	Мацій, О.Б.
dc.contributor.author	Скачков, В.О.
dc.contributor.author	Kushnir, N.A.
dc.contributor.author	Matsiy, O.B.
dc.contributor.author	Skachkov, V.A.
dc.date.accessioned	2016-04-05T11:20:04Z
dc.date.available	2016-04-05T11:20:04Z
dc.date.issued	2015
dc.identifier.uri	http://eztuir.ztu.edu.ua/123456789/2543
dc.description.abstract	У застосуваннях теорії графів широку популярність отримала задача про паросполучення. Вона полягає в знаходженні в заданому графі паросполучення з найбільшою кількістю ребер – максимального паросполучення. Узагальненям цієї задачі є задача про зважене паросполучення. Класичний алгоритм Едмондса для знаходження найбільшого зваженого паросполучення у недводольному графі характеризується трудомісткістю O(V4). Відома задача про зважене паросполучення у довільному графі H з n вершинами зводиться до однієї з задач про паросполучення для дводольного графа з 2n вершинами. Максимальне паросполучення графа H з мінімальною сумою ваг ребер, заданих матрицею [c ] , знаходиться за час (O n3) після впорядкування за незменшенням значень c, розташованих над головною діагоналлю.	uk_UA
dc.language.iso	uk	uk_UA
dc.publisher	ЖДТУ	uk_UA
dc.relation.ispartofseries	Вісник ЖДТУ: Серія: Технічні науки;3(74)
dc.subject	паросполучення	uk_UA
dc.subject	максимальне паросполучення	uk_UA
dc.subject	задача про зважене паросполучення	uk_UA
dc.subject	matchings	uk_UA
dc.subject	maximum matching	uk_UA
dc.subject	the problem of weighted matching	uk_UA
dc.title	МЕТОД НАЙКОРОТШИХ ЗБІЛЬШУЮЧИХ ШЛЯХІВ У ЗАДАЧАХ ПРО ПАРОСПОЛУЧЕННЯ	uk_UA
dc.title.alternative	Method of the shortest paths in the increasing problems of matchings	uk_UA
dc.type	Article	uk_UA
dc.description.abstracten	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.	uk_UA