1. Електронний архів Державного університету «Житомирська політехніка»
  2. Фахові видання
  3. Вісник ЖДТУ. Серія: Технічні науки
Please use this identifier to cite or link to this item: http://eztuir.ztu.edu.ua/123456789/2543
Full metadata record
DC FieldValueLanguage
dc.contributor.authorКушнір, Н.О.
dc.contributor.authorМацій, О.Б.
dc.contributor.authorСкачков, В.О.
dc.contributor.authorKushnir, N.A.
dc.contributor.authorMatsiy, O.B.
dc.contributor.authorSkachkov, V.A.
dc.date.accessioned2016-04-05T11:20:04Z
dc.date.available2016-04-05T11:20:04Z
dc.date.issued2015
dc.identifier.urihttp://eztuir.ztu.edu.ua/123456789/2543
dc.description.abstractУ застосуваннях теорії графів широку популярність отримала задача про паросполучення. Вона полягає в знаходженні в заданому графі паросполучення з найбільшою кількістю ребер – максимального паросполучення. Узагальненям цієї задачі є задача про зважене паросполучення. Класичний алгоритм Едмондса для знаходження найбільшого зваженого паросполучення у недводольному графі характеризується трудомісткістю O(V4). Відома задача про зважене паросполучення у довільному графі H з n вершинами зводиться до однієї з задач про паросполучення для дводольного графа з 2n вершинами. Максимальне паросполучення графа H з мінімальною сумою ваг ребер, заданих матрицею [c ] , знаходиться за час (O n3) після впорядкування за незменшенням значень c, розташованих над головною діагоналлю.uk_UA
dc.language.isoukuk_UA
dc.publisherЖДТУuk_UA
dc.relation.ispartofseriesВісник ЖДТУ: Серія: Технічні науки;3(74)
dc.subjectпаросполученняuk_UA
dc.subjectмаксимальне паросполученняuk_UA
dc.subjectзадача про зважене паросполученняuk_UA
dc.subjectmatchingsuk_UA
dc.subjectmaximum matchinguk_UA
dc.subjectthe problem of weighted matchinguk_UA
dc.titleМЕТОД НАЙКОРОТШИХ ЗБІЛЬШУЮЧИХ ШЛЯХІВ У ЗАДАЧАХ ПРО ПАРОСПОЛУЧЕННЯuk_UA
dc.title.alternativeMethod of the shortest paths in the increasing problems of matchingsuk_UA
dc.typeArticleuk_UA
dc.description.abstractenIn 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
Appears in Collections:Вісник ЖДТУ. Серія: Технічні науки

Files in This Item:
File Description SizeFormat 
17.pdf425.56 kBAdobe PDFView/Open
Show simple item record


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.