Совершенные паросочетания и полиматроиды / Шарифов Ф. А. (2017)
Ukrainian

інтернет-адреса сторінки: http://jnas.nbuv.gov.ua/article/UJRN-0000754489
  Кибернетика и системный анализ      А - 2019  /     Випуск (2017, Т. 53, № 5)

Шарифов Ф. А.
Совершенные паросочетания и полиматроиды

Показано, что произвольный граф содержит совершенноепаросочетание тогда и только тогда, когда специально определенный вектор является базой расширенного полиматроида, описанного субмодулярной функцией, определенной на подмножествах множества вершин. На базе этого факта можно применить различные алгоритмы решения задачи о допустимых потоках на сетях для нахождения совершенного паросочетания в заданном графе.

 https://doi.org/10.1007/s10559-017-9977-8
 Scopus

Бібліографічний опис:
Шарифов Ф. А.  Совершенные паросочетания и полиматроиды. Кибернетика и системный анализ. 2017. Т. 53, № 5. С. 113-119. doi: https://doi.org/10.1007/s10559-017-9977-8 URL: http://jnas.nbuv.gov.ua/article/UJRN-0000754489

English  Cybernetics and Systems Analysis   /     Issue (2017, 53 (5))

Sharifov F.A.
Perfect matching and polymatroids

It is shown that any graph has a perfect matching if and only if a specially defined vector is the base of extended polymatroid associated with submodular function defined on subsets of vertex set. Based on this fact, different algorithms for testing flow feasibility can be used to find some perfect matching in a given graph. © 2017, Springer Science+Business Media, LLC.

Keywords: extended polymatroid, graph, perfect matching, Computer science, Cybernetics, graph, Perfect matchings, Polymatroids, Submodular functions, Vertex set, Flow graphs

Cite:
Sharifov F.A. (2017). Perfect matching and polymatroids. Cybernetics and Systems Analysis, 53 (5), 113-119. doi: https://doi.org/10.1007/s10559-017-9977-8 http://jnas.nbuv.gov.ua/article/UJRN-0000754489 [In Russian].

 

Інститут інформаційних технологій НБУВ

+38 (044) 525-36-24
libnas@nbuv.gov.ua
Голосіївський просп., 3, к. 209
м. Київ, 03039, Україна