????? ??????????? ??????????? ?????? ? ??????? ??? ??????????????
Електронний архів Житомирського державного технологічного університету
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 |
????
|
|