Please use this identifier to cite or link to this item:
http://eztuir.ztu.edu.ua/123456789/2543
Title: | МЕТОД НАЙКОРОТШИХ ЗБІЛЬШУЮЧИХ ШЛЯХІВ У ЗАДАЧАХ ПРО ПАРОСПОЛУЧЕННЯ |
Other Titles: | Method of the shortest paths in the increasing problems of matchings |
Authors: | Кушнір, Н.О. Мацій, О.Б. Скачков, В.О. Kushnir, N.A. Matsiy, O.B. Skachkov, V.A. |
Keywords: | паросполучення максимальне паросполучення задача про зважене паросполучення matchings maximum matching the problem of weighted matching |
Issue Date: | 2015 |
Publisher: | ЖДТУ |
Series/Report no.: | Вісник ЖДТУ: Серія: Технічні науки;3(74) |
Abstract: | У застосуваннях теорії графів широку популярність отримала задача про паросполучення. Вона полягає в знаходженні в заданому графі паросполучення з найбільшою кількістю ребер – максимального паросполучення. Узагальненям цієї задачі є задача про зважене паросполучення. Класичний алгоритм Едмондса для знаходження найбільшого зваженого паросполучення у недводольному графі характеризується трудомісткістю O(V4). Відома задача про зважене паросполучення у довільному графі H з n вершинами зводиться до однієї з задач про паросполучення для дводольного графа з 2n вершинами. Максимальне паросполучення графа H з мінімальною сумою ваг ребер, заданих матрицею [c ] , знаходиться за час (O n3) після впорядкування за незменшенням значень c, розташованих над головною діагоналлю. |
URI: | http://eztuir.ztu.edu.ua/123456789/2543 |
Appears in Collections: | Вісник ЖДТУ. Серія: Технічні науки |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.