Задача нахождения непересекающихся и несовпадающих циклов на сети
Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения пото...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2003 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2003
|
| Онлайн доступ: | https://nasplib.isofts.kiev.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| _version_ | 1862670730313859072 |
|---|---|
| author | Шарифов, Ф.А. |
| author_facet | Шарифов, Ф.А. |
| citation_txt | Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 155-161. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения потока минимальной стоимости на сети представленой двудольным графом. Для последней задачи разработаны ряд строгих полиномиальных алгоритмов. В общем случае рассмотренная задача не имеет целочисленное решение. В работе приводятся основные этапы полиномиального алгоритма для решения задачи в общем случае.
Разглянуто задачу знаходження циклів на мережі, що не перетинаються і не співпадають. Показано, що ця задача еквівалентна задачі знаходження двох паросполучень на двудольному графі. В окремих випадках розглянута задача є задачею знаходження потоку мінімальної вартості. Наведено, що ці властивості є основними для разробки поліноміального алгоритму вирішення задачі.
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.
|
| first_indexed | 2025-12-07T15:31:06Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-84868 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T15:31:06Z |
| publishDate | 2003 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шарифов, Ф.А. 2015-07-16T15:18:55Z 2015-07-16T15:18:55Z 2003 Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 155-161. — Бібліогр.: 8 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84868 519.8 Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения потока минимальной стоимости на сети представленой двудольным графом. Для последней задачи разработаны ряд строгих полиномиальных алгоритмов. В общем случае рассмотренная задача не имеет целочисленное решение. В работе приводятся основные этапы полиномиального алгоритма для решения задачи в общем случае. Разглянуто задачу знаходження циклів на мережі, що не перетинаються і не співпадають. Показано, що ця задача еквівалентна задачі знаходження двох паросполучень на двудольному графі. В окремих випадках розглянута задача є задачею знаходження потоку мінімальної вартості. Наведено, що ці властивості є основними для разробки поліноміального алгоритму вирішення задачі. 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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Задача нахождения непересекающихся и несовпадающих циклов на сети Задача знаходження не перетинаючих і не співпадаючих циклів на мережі Minimum cost node and arc disjoint cycles problem Article published earlier |
| spellingShingle | Задача нахождения непересекающихся и несовпадающих циклов на сети Шарифов, Ф.А. |
| title | Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_alt | Задача знаходження не перетинаючих і не співпадаючих циклів на мережі Minimum cost node and arc disjoint cycles problem |
| title_full | Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_fullStr | Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_full_unstemmed | Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_short | Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_sort | задача нахождения непересекающихся и несовпадающих циклов на сети |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84868 |
| work_keys_str_mv | AT šarifovfa zadačanahoždeniâneperesekaûŝihsâinesovpadaûŝihciklovnaseti AT šarifovfa zadačaznahodžennâneperetinaûčihínespívpadaûčihciklívnamereží AT šarifovfa minimumcostnodeandarcdisjointcyclesproblem |