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 |