Задача нахождения непересекающихся и несовпадающих циклов на сети

Задача нахождения непересекающихся и несовпадающих циклов на сети

Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения пото...

Повний опис

Збережено в:
Бібліографічні деталі
Видавець:Інститут кібернетики ім. В.М. Глушкова НАН України
Дата:2003
Автор: Шарифов, Ф.А.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2003
Назва видання:Теорія оптимальних рішень
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/84868
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Цитувати:Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 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

Схожі ресурси