інтернет-адреса сторінки: http://jnas.nbuv.gov.ua/article/UJRN-0001129993
Кибернетика и системный анализ   А - 2019 /  Випуск (2020, Т. 56, № 4)
Шарифов Ф. А., Гуляницкий Л. Ф.
Разрезы в неориентированных графах. I Исследованы новые свойства разрезов в неориентированных графах, приведены различные модели для задачи максимального разреза на основе установленного соответствия между разрезами в заданном графе и специфическими базами расширенного полиматроида, ассоциированного с этим графом. Для модели, сформулированной как задача нахождения максимума выпуклой функции на компактном множестве - расширенном полиматроиде, доказано, что локальные и глобальные максимумы совпадают по значению целевой функции, т.е. для решения задачи максимального разреза достаточно найти базу расширенного полиматроида как локальный или глобальный максимум целевой функции. Предложены 2 алгоритма преобразования текущей базы полиматроида в новую для улучшения значения целевой функции. Установлена эквивалентность задачи максимального разреза на заданном графе и задачи нахождения минимального разреза, отделяющего источник и сток в сети, построенной относительно некоторой базы расширенного полиматроида. Сформулированы необходимые и достаточные условия оптимальности решения задачи максимального разреза на неориентированных графах в терминах теории потоков.
 https://doi.org/10.1007/s10559-020-00292-z
 Scopus
Бібліографічний опис:
Шарифов Ф. А., Гуляницкий Л. Ф. Разрезы в неориентированных графах. I. Кибернетика и системный анализ. 2020. Т. 56, № 4. С. 46–55. doi: https://doi.org/10.1007/s10559-020-00292-z URL: http://jnas.nbuv.gov.ua/article/UJRN-0001129993 |
 Cybernetics and Systems Analysis / Issue (2020, 56 (4))
Sharifov F.,
Hulianytskyi L.
Cuts in undirected graphs. I To improve the value of the objective function, two algorithms for transforming the current base into a new one are proposed. It is shown that the maximum cut problem on an undirected graph can be reduced to finding the base of the extended polynomial, for which the value of the minimum cut that separates the source and the sink is maximum. The necessary and sufficient conditions for optimality of the solution of the maximum cut problem on undirected graphs in terms of flow theory are formulated. © 2020, Springer Science+Business Media, LLC, part of Springer Nature. Keywords: convex function, cuts, graphs, polymatroid, special polyhedra, Computer science, Cybernetics, Flow theories, Maximum cut problems, Minimum cut, Objective functions, Optimality, Undirected graph, Flow graphs
Cite:
Sharifov F.,
Hulianytskyi L.
(2020). Cuts in undirected graphs. I. Cybernetics and Systems Analysis, 56 (4), 46–55. doi: https://doi.org/10.1007/s10559-020-00292-z http://jnas.nbuv.gov.ua/article/UJRN-0001129993 [In Russian]. |
PDF