Разрезы в неориентированных графах. I
Исследованы новые свойства разрезов в неориентированных графах, приведены различные модели для задачи максимального разреза на основе установленного соответствия между разрезами в заданном графе и специфическими базами расширенного полиматроида, ассоциированного с этим графом. Для модели, сформулиро...
Збережено в:
| Видавець: | Інститут кібернетики ім. В.М. Глушкова НАН України |
|---|---|
| Дата: | 2020 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/190421 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Цитувати: | Разрезы в неориентированных графах. I / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 4. — С. 46–55. — Бібліогр.: 20 назв. — рос. |
Репозиторії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-190421 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1904212023-06-06T16:04:08Z Разрезы в неориентированных графах. I Шарифов, Ф.А. Гуляницкий, Л.Ф. Системний аналіз Исследованы новые свойства разрезов в неориентированных графах, приведены различные модели для задачи максимального разреза на основе установленного соответствия между разрезами в заданном графе и специфическими базами расширенного полиматроида, ассоциированного с этим графом. Для модели, сформулированной как задача нахождения максимума выпуклой функции на компактном множестве - расширенном полиматроиде, доказано, что локальные и глобальные максимумы совпадают по значению целевой функции, т.е. для решения задачи максимального разреза достаточно найти базу расширенного полиматроида как локальный или глобальный максимум целевой функции. Досліджено нові властивості розрізів у неорієнтованих графах, наведено різні моделі для задачі максимального розрізу на основі встановленої відповідності між розрізами в заданому графі і специфічними базами розширеного поліматроїда, асоційованого з цим графом. Для моделі, сформульовано ї як задача знаходження максимуму опуклої функції на компактній множині (розширеному поліматроїді), доведено, що локальні і глобальні максимуми збігаються за значенням цільової функції, тобто для розв'язання задачі максимального розрізу достатньо знайти базу розширеного поліматроїда як локальний або глобальний максимум цільової функції. 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. 2020 Article Разрезы в неориентированных графах. I / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 4. — С. 46–55. — Бібліогр.: 20 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/190421 519.8 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системний аналіз Системний аналіз |
| spellingShingle |
Системний аналіз Системний аналіз Шарифов, Ф.А. Гуляницкий, Л.Ф. Разрезы в неориентированных графах. I Кибернетика и системный анализ |
| description |
Исследованы новые свойства разрезов в неориентированных графах, приведены различные модели для задачи максимального разреза на основе установленного соответствия между разрезами в заданном графе и специфическими базами расширенного полиматроида, ассоциированного с этим графом. Для модели, сформулированной как задача нахождения максимума выпуклой функции на компактном множестве - расширенном полиматроиде, доказано, что локальные и глобальные максимумы совпадают по значению целевой функции, т.е. для решения задачи максимального разреза достаточно найти базу расширенного полиматроида как локальный или глобальный максимум целевой функции. |
| format |
Article |
| author |
Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| author_facet |
Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| author_sort |
Шарифов, Ф.А. |
| title |
Разрезы в неориентированных графах. I |
| title_short |
Разрезы в неориентированных графах. I |
| title_full |
Разрезы в неориентированных графах. I |
| title_fullStr |
Разрезы в неориентированных графах. I |
| title_full_unstemmed |
Разрезы в неориентированных графах. I |
| title_sort |
разрезы в неориентированных графах. i |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2020 |
| topic_facet |
Системний аналіз |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/190421 |
| citation_txt |
Разрезы в неориентированных графах. I / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 4. — С. 46–55. — Бібліогр.: 20 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT šarifovfa razrezyvneorientirovannyhgrafahi AT gulânickijlf razrezyvneorientirovannyhgrafahi |
| first_indexed |
2023-10-18T23:12:55Z |
| last_indexed |
2023-10-18T23:12:55Z |
| _version_ |
1796157546363355136 |