Задача нахождения непересекающихся и несовпадающих циклов на сети
Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения пото...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2003 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2003
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84868 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 155-161. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84868 |
|---|---|
| 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 |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Задача нахождения непересекающихся и несовпадающих циклов на сети |
| spellingShingle |
Задача нахождения непересекающихся и несовпадающих циклов на сети Шарифов, Ф.А. |
| title_short |
Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_full |
Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_fullStr |
Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_full_unstemmed |
Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_sort |
задача нахождения непересекающихся и несовпадающих циклов на сети |
| author |
Шарифов, Ф.А. |
| author_facet |
Шарифов, Ф.А. |
| publishDate |
2003 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Задача знаходження не перетинаючих і не співпадаючих циклів на мережі Minimum cost node and arc disjoint cycles problem |
| 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.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84868 |
| citation_txt |
Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 155-161. — Бібліогр.: 8 назв. — рос. |
| 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 |
| first_indexed |
2025-12-07T15:31:06Z |
| last_indexed |
2025-12-07T15:31:06Z |
| _version_ |
1850864006681591808 |