Разрезы в неориентированных графах. II
Предложены 2 алгоритма преобразования текущей базы полиматроида в новую для улучшения значения целевой функции. Установлена эквивалентность задачи максимального разреза на заданном графе и задачи нахождения минимального разреза, отделяющего источник и сток в сети, построенной относительно некоторой...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2020 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/190454 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Разрезы в неориентированных графах. II / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 70–79. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862582985371418624 |
|---|---|
| author | Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| author_facet | Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| citation_txt | Разрезы в неориентированных графах. II / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 70–79. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Предложены 2 алгоритма преобразования текущей базы полиматроида в новую для улучшения значения целевой функции. Установлена эквивалентность задачи максимального разреза на заданном графе и задачи нахождения минимального разреза, отделяющего источник и сток в сети, построенной относительно некоторой базы расширенного полиматроида. Сформулированы необходимые и достаточные условия оптимальности решения задачи максимального разреза на неориентированных графах в терминах теории потоков.
Запропоновано два алгоритми перетворення поточної бази поліматроїда до нової з метою поліпшення значення цільової функції. Встановлено еквівалентність задачі максимального розрізу на заданому графі і задачі знаходження мінімального розрізу, що відокремлює джерело і стік в мережі, побудованої відносно деякої бази розширеного поліматроїда. Сформульовано необхідні та достатні умови оптимальності розв'язування задачі максимального розрізу на неорієнтованих графах в термінах теорії потоків.
To improve the value of the objective function, two algorithms are proposed for transforming the current base into a new one. 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 non-oriented graphs in terms of flow theory are formulated.
|
| first_indexed | 2025-11-26T23:56:51Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-190454 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-11-26T23:56:51Z |
| publishDate | 2020 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шарифов, Ф.А. Гуляницкий, Л.Ф. 2023-06-08T15:29:42Z 2023-06-08T15:29:42Z 2020 Разрезы в неориентированных графах. II / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 70–79. — Бібліогр.: 8 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190454 519.8 Предложены 2 алгоритма преобразования текущей базы полиматроида в новую для улучшения значения целевой функции. Установлена эквивалентность задачи максимального разреза на заданном графе и задачи нахождения минимального разреза, отделяющего источник и сток в сети, построенной относительно некоторой базы расширенного полиматроида. Сформулированы необходимые и достаточные условия оптимальности решения задачи максимального разреза на неориентированных графах в терминах теории потоков. Запропоновано два алгоритми перетворення поточної бази поліматроїда до нової з метою поліпшення значення цільової функції. Встановлено еквівалентність задачі максимального розрізу на заданому графі і задачі знаходження мінімального розрізу, що відокремлює джерело і стік в мережі, побудованої відносно деякої бази розширеного поліматроїда. Сформульовано необхідні та достатні умови оптимальності розв'язування задачі максимального розрізу на неорієнтованих графах в термінах теорії потоків. To improve the value of the objective function, two algorithms are proposed for transforming the current base into a new one. 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 non-oriented graphs in terms of flow theory are formulated. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Разрезы в неориентированных графах. II Розрізи в неорієнтованих графах. IІ Cuts in undirected graphs. II Article published earlier |
| spellingShingle | Разрезы в неориентированных графах. II Шарифов, Ф.А. Гуляницкий, Л.Ф. Системний аналіз |
| title | Разрезы в неориентированных графах. II |
| title_alt | Розрізи в неорієнтованих графах. IІ Cuts in undirected graphs. II |
| title_full | Разрезы в неориентированных графах. II |
| title_fullStr | Разрезы в неориентированных графах. II |
| title_full_unstemmed | Разрезы в неориентированных графах. II |
| title_short | Разрезы в неориентированных графах. II |
| title_sort | разрезы в неориентированных графах. ii |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/190454 |
| work_keys_str_mv | AT šarifovfa razrezyvneorientirovannyhgrafahii AT gulânickiilf razrezyvneorientirovannyhgrafahii AT šarifovfa rozrízivneoríêntovanihgrafahií AT gulânickiilf rozrízivneoríêntovanihgrafahií AT šarifovfa cutsinundirectedgraphsii AT gulânickiilf cutsinundirectedgraphsii |