Задача нахождения непересекающихся и несовпадающих циклов на сети
Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения пото...
Збережено в:
| Дата: | 2003 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2003
|
| Назва видання: | Теорія оптимальних рішень |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84868 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 155-161. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84868 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-848682018-03-24T12:09:27Z Задача нахождения непересекающихся и несовпадающих циклов на сети Шарифов, Ф.А. Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения потока минимальной стоимости на сети представленой двудольным графом. Для последней задачи разработаны ряд строгих полиномиальных алгоритмов. В общем случае рассмотренная задача не имеет целочисленное решение. В работе приводятся основные этапы полиномиального алгоритма для решения задачи в общем случае. Разглянуто задачу знаходження циклів на мережі, що не перетинаються і не співпадають. Показано, що ця задача еквівалентна задачі знаходження двох паросполучень на двудольному графі. В окремих випадках розглянута задача є задачею знаходження потоку мінімальної вартості. Наведено, що ці властивості є основними для разробки поліноміального алгоритму вирішення задачі. We study a minimum cost node and arc-disjoint cycles problem on a directed graph. It is shown that the problem is equivalent to the minimum cost disjoint matchings problem on complete bipartite graph. In particular case, for which weights of arcs are special, then the considered problem is reduced to minimum cost flow problem. Some interesting properties of LP-relaxation problem are proved and it is noted that namely these properties are on bases for polynomial algorithm to solve the problem. 2003 Article Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 155-161. — Бібліогр.: 8 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84868 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения потока минимальной стоимости на сети представленой двудольным графом. Для последней задачи разработаны ряд строгих полиномиальных алгоритмов. В общем случае рассмотренная задача не имеет целочисленное решение. В работе приводятся основные этапы полиномиального алгоритма для решения задачи в общем случае. |
| format |
Article |
| author |
Шарифов, Ф.А. |
| spellingShingle |
Шарифов, Ф.А. Задача нахождения непересекающихся и несовпадающих циклов на сети Теорія оптимальних рішень |
| author_facet |
Шарифов, Ф.А. |
| author_sort |
Шарифов, Ф.А. |
| title |
Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_short |
Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_full |
Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_fullStr |
Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_full_unstemmed |
Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_sort |
задача нахождения непересекающихся и несовпадающих циклов на сети |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2003 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84868 |
| citation_txt |
Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 155-161. — Бібліогр.: 8 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT šarifovfa zadačanahoždeniâneperesekaûŝihsâinesovpadaûŝihciklovnaseti |
| first_indexed |
2023-10-18T19:29:51Z |
| last_indexed |
2023-10-18T19:29:51Z |
| _version_ |
1796147121709121536 |