Record Details

????? ??????????? ??????????? ?????? ? ??????? ??? ??????????????

Електронний архів Житомирського державного технологічного університету

View Archive Info
 
 
Field Value
 
Title ????? ??????????? ??????????? ?????? ? ??????? ??? ??????????????
Method of the shortest paths in the increasing problems of matchings
 
Creator ??????, ?.?.
?????, ?.?.
???????, ?.?.
Kushnir, N.A.
Matsiy, O.B.
Skachkov, V.A.
 
Subject ??????????????
??????????? ??????????????
?????? ??? ??????? ??????????????
matchings
maximum matching
the problem of weighted matching
 
Description ? ????????????? ?????? ?????? ?????? ???????????? ???????? ?????? ??? ??????????????.
???? ??????? ? ??????????? ? ???????? ????? ?????????????? ? ?????????? ????????? ????? ?
????????????? ??????????????. ???????????? ???? ?????? ? ?????? ??? ??????? ??????????????.
????????? ???????? ???????? ??? ??????????? ??????????? ????????? ?????????????? ?
????????????? ????? ???????????????? ?????????????? 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.
 
Date 2016-04-05T11:20:04Z
2016-04-05T11:20:04Z
2015
 
Type Article
 
Identifier http://eztuir.ztu.edu.ua/123456789/2543
 
Language uk
 
Relation ?????? ????: ?????: ???????? ?????;3(74)
 
Publisher ????