Разрезы в неориентированных графах. II
Предложены 2 алгоритма преобразования текущей базы полиматроида в новую для улучшения значения целевой функции. Установлена эквивалентность задачи максимального разреза на заданном графе и задачи нахождения минимального разреза, отделяющего источник и сток в сети, построенной относительно некоторой...
Gespeichert in:
| Datum: | 2020 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.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| id |
irk-123456789-190454 |
|---|---|
| record_format |
dspace |
| fulltext |
|
| spelling |
irk-123456789-1904542023-06-08T18:29:42Z Разрезы в неориентированных графах. II Шарифов, Ф.А. Гуляницкий, Л.Ф. Системний аналіз Предложены 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. 2020 Article Разрезы в неориентированных графах. II / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 70–79. — Бібліогр.: 8 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/190454 519.8 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системний аналіз Системний аналіз |
| spellingShingle |
Системний аналіз Системний аналіз Шарифов, Ф.А. Гуляницкий, Л.Ф. Разрезы в неориентированных графах. II Кибернетика и системный анализ |
| description |
Предложены 2 алгоритма преобразования текущей базы полиматроида в новую для улучшения значения целевой функции. Установлена эквивалентность задачи максимального разреза на заданном графе и задачи нахождения минимального разреза, отделяющего источник и сток в сети, построенной относительно некоторой базы расширенного полиматроида. Сформулированы необходимые и достаточные условия оптимальности решения задачи максимального разреза на неориентированных графах в терминах теории потоков. |
| format |
Article |
| author |
Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| author_facet |
Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| author_sort |
Шарифов, Ф.А. |
| title |
Разрезы в неориентированных графах. II |
| title_short |
Разрезы в неориентированных графах. II |
| title_full |
Разрезы в неориентированных графах. II |
| title_fullStr |
Разрезы в неориентированных графах. II |
| title_full_unstemmed |
Разрезы в неориентированных графах. II |
| title_sort |
разрезы в неориентированных графах. ii |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2020 |
| topic_facet |
Системний аналіз |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/190454 |
| citation_txt |
Разрезы в неориентированных графах. II / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 70–79. — Бібліогр.: 8 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT šarifovfa razrezyvneorientirovannyhgrafahii AT gulânickijlf razrezyvneorientirovannyhgrafahii |
| first_indexed |
2025-07-16T13:19:13Z |
| last_indexed |
2025-07-16T13:19:13Z |
| _version_ |
1837809746710626304 |