Разрезы в неориентированных графах. I
Исследованы новые свойства разрезов в неориентированных графах, приведены различные модели для задачи максимального разреза на основе установленного соответствия между разрезами в заданном графе и специфическими базами расширенного полиматроида, ассоциированного с этим графом. Для модели, сформулиро...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2020 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/190421 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Разрезы в неориентированных графах. I / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 4. — С. 46–55. — Бібліогр.: 20 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862566373769609216 |
|---|---|
| author | Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| author_facet | Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| citation_txt | Разрезы в неориентированных графах. I / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 4. — С. 46–55. — Бібліогр.: 20 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Исследованы новые свойства разрезов в неориентированных графах, приведены различные модели для задачи максимального разреза на основе установленного соответствия между разрезами в заданном графе и специфическими базами расширенного полиматроида, ассоциированного с этим графом. Для модели, сформулированной как задача нахождения максимума выпуклой функции на компактном множестве - расширенном полиматроиде, доказано, что локальные и глобальные максимумы совпадают по значению целевой функции, т.е. для решения задачи максимального разреза достаточно найти базу расширенного полиматроида как локальный или глобальный максимум целевой функции.
Досліджено нові властивості розрізів у неорієнтованих графах, наведено різні моделі для задачі максимального розрізу на основі встановленої відповідності між розрізами в заданому графі і специфічними базами розширеного поліматроїда, асоційованого з цим графом. Для моделі, сформульовано ї як задача знаходження максимуму опуклої функції на компактній множині (розширеному поліматроїді), доведено, що локальні і глобальні максимуми збігаються за значенням цільової функції, тобто для розв'язання задачі максимального розрізу достатньо знайти базу розширеного поліматроїда як локальний або глобальний максимум цільової функції.
This part of the paper analyzes new properties of cuts in undirected graphs, presents various models for the maximum cut problem, based on the established correspondence between the cuts in this graph and the specific bases of the extended polymatroid associated with this graph. With respect to the model, formulated as the maximization of the convex function on the compact set (extended polymatroid), it was proved that the objective function has the same value at any local and global maximum, i.e., to solve the maximum cut problem, it needs to find a base of the extended polymatroid as a local or global maximum of the objective function.
|
| first_indexed | 2025-11-26T00:09:22Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-190421 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-11-26T00:09:22Z |
| publishDate | 2020 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шарифов, Ф.А. Гуляницкий, Л.Ф. 2023-06-06T13:04:07Z 2023-06-06T13:04:07Z 2020 Разрезы в неориентированных графах. I / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 4. — С. 46–55. — Бібліогр.: 20 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190421 519.8 Исследованы новые свойства разрезов в неориентированных графах, приведены различные модели для задачи максимального разреза на основе установленного соответствия между разрезами в заданном графе и специфическими базами расширенного полиматроида, ассоциированного с этим графом. Для модели, сформулированной как задача нахождения максимума выпуклой функции на компактном множестве - расширенном полиматроиде, доказано, что локальные и глобальные максимумы совпадают по значению целевой функции, т.е. для решения задачи максимального разреза достаточно найти базу расширенного полиматроида как локальный или глобальный максимум целевой функции. Досліджено нові властивості розрізів у неорієнтованих графах, наведено різні моделі для задачі максимального розрізу на основі встановленої відповідності між розрізами в заданому графі і специфічними базами розширеного поліматроїда, асоційованого з цим графом. Для моделі, сформульовано ї як задача знаходження максимуму опуклої функції на компактній множині (розширеному поліматроїді), доведено, що локальні і глобальні максимуми збігаються за значенням цільової функції, тобто для розв'язання задачі максимального розрізу достатньо знайти базу розширеного поліматроїда як локальний або глобальний максимум цільової функції. This part of the paper analyzes new properties of cuts in undirected graphs, presents various models for the maximum cut problem, based on the established correspondence between the cuts in this graph and the specific bases of the extended polymatroid associated with this graph. With respect to the model, formulated as the maximization of the convex function on the compact set (extended polymatroid), it was proved that the objective function has the same value at any local and global maximum, i.e., to solve the maximum cut problem, it needs to find a base of the extended polymatroid as a local or global maximum of the objective function. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Разрезы в неориентированных графах. I Розрізи в неорієнтованих графах. І Cuts in undirected graphs. Article published earlier |
| spellingShingle | Разрезы в неориентированных графах. I Шарифов, Ф.А. Гуляницкий, Л.Ф. Системний аналіз |
| title | Разрезы в неориентированных графах. I |
| title_alt | Розрізи в неорієнтованих графах. І Cuts in undirected graphs. |
| title_full | Разрезы в неориентированных графах. I |
| title_fullStr | Разрезы в неориентированных графах. I |
| title_full_unstemmed | Разрезы в неориентированных графах. I |
| title_short | Разрезы в неориентированных графах. I |
| title_sort | разрезы в неориентированных графах. i |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/190421 |
| work_keys_str_mv | AT šarifovfa razrezyvneorientirovannyhgrafahi AT gulânickiilf razrezyvneorientirovannyhgrafahi AT šarifovfa rozrízivneoríêntovanihgrafahí AT gulânickiilf rozrízivneoríêntovanihgrafahí AT šarifovfa cutsinundirectedgraphs AT gulânickiilf cutsinundirectedgraphs |