Совершенные паросочетания и полиматроиды

Совершенные паросочетания и полиматроиды

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

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2017
Автор: Шарифов, Ф.А.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2017
Назва видання:Кибернетика и системный анализ
Теми:
Системний аналіз
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/144795
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Совершенные паросочетания и полиматроиды / Ф.А. Шарифов // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 113–119. — Бібліогр.: 7 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-144795
record_format dspace
spelling irk-123456789-1447952019-01-05T01:23:11Z Совершенные паросочетания и полиматроиды Шарифов, Ф.А. Системний аналіз Показано, что произвольный граф содержит совершенное паросочетание тогда и только тогда, когда специально определенный вектор является базой расширенного полиматроида, описанного субмодулярной функцией, определенной на подмножествах множества вершин. На базе этого факта можно применять различные алгоритмы решения задачи о допустимых потоках на сетях для нахождения совершенного паросочетания в заданном графе. Показано, що довільний граф містить досконалу парносполуку тоді і тільки тоді, коли спеціально визначений вектор є базою розширеного поліматроїда, описаного субмодулярною функцією, визначеною на підмножинах множин вершин. На базі цього факту можна застосовувати різні алгоритми розв’язання задачі про допустимі потоки в мережах для знаходження досконалої парносполуки у заданому графі. It is shown that any graph has a perfect matching if and only if a specially defined vector is the base of the extended polymatroid associated with the submodular function defined on subsets of the vertex set. Based on this fact, different algorithms for testing flow feasibility can be used to find some perfect matching in a given graph. 2017 Article Совершенные паросочетания и полиматроиды / Ф.А. Шарифов // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 113–119. — Бібліогр.: 7 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/144795 519.8 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Системний аналіз
Системний аналіз
spellingShingle Системний аналіз
Системний аналіз
Шарифов, Ф.А.
Совершенные паросочетания и полиматроиды
Кибернетика и системный анализ
description Показано, что произвольный граф содержит совершенное паросочетание тогда и только тогда, когда специально определенный вектор является базой расширенного полиматроида, описанного субмодулярной функцией, определенной на подмножествах множества вершин. На базе этого факта можно применять различные алгоритмы решения задачи о допустимых потоках на сетях для нахождения совершенного паросочетания в заданном графе.
format Article
author Шарифов, Ф.А.
author_facet Шарифов, Ф.А.
author_sort Шарифов, Ф.А.
title Совершенные паросочетания и полиматроиды
title_short Совершенные паросочетания и полиматроиды
title_full Совершенные паросочетания и полиматроиды
title_fullStr Совершенные паросочетания и полиматроиды
title_full_unstemmed Совершенные паросочетания и полиматроиды
title_sort совершенные паросочетания и полиматроиды
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2017
topic_facet Системний аналіз
url http://dspace.nbuv.gov.ua/handle/123456789/144795
citation_txt Совершенные паросочетания и полиматроиды / Ф.А. Шарифов // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 113–119. — Бібліогр.: 7 назв. — рос.
series Кибернетика и системный анализ
work_keys_str_mv AT šarifovfa soveršennyeparosočetaniâipolimatroidy
first_indexed 2023-05-20T17:20:29Z
last_indexed 2023-05-20T17:20:29Z
_version_ 1796153075525746688

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