Совершенные паросочетания и полиматроиды
Показано, что произвольный граф содержит совершенное паросочетание тогда и только тогда, когда специально определенный вектор является базой расширенного полиматроида, описанного субмодулярной функцией, определенной на подмножествах множества вершин. На базе этого факта можно применять различные алг...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2017 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/144795 |
| 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: | Совершенные паросочетания и полиматроиды / Ф.А. Шарифов // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 113–119. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-144795 |
|---|---|
| record_format |
dspace |
| spelling |
Шарифов, Ф.А. 2019-01-04T18:23:56Z 2019-01-04T18:23:56Z 2017 Совершенные паросочетания и полиматроиды / Ф.А. Шарифов // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 113–119. — Бібліогр.: 7 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/144795 519.8 Показано, что произвольный граф содержит совершенное паросочетание тогда и только тогда, когда специально определенный вектор является базой расширенного полиматроида, описанного субмодулярной функцией, определенной на подмножествах множества вершин. На базе этого факта можно применять различные алгоритмы решения задачи о допустимых потоках на сетях для нахождения совершенного паросочетания в заданном графе. Показано, що довільний граф містить досконалу парносполуку тоді і тільки тоді, коли спеціально визначений вектор є базою розширеного поліматроїда, описаного субмодулярною функцією, визначеною на підмножинах множин вершин. На базі цього факту можна застосовувати різні алгоритми розв’язання задачі про допустимі потоки в мережах для знаходження досконалої парносполуки у заданому графі. 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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Совершенные паросочетания и полиматроиды Досконалі парносполуки і поліматроїди Perfect matching and polymatroids 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 |
Шарифов, Ф.А. |
| topic |
Системний аналіз |
| topic_facet |
Системний аналіз |
| publishDate |
2017 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Досконалі парносполуки і поліматроїди Perfect matching and polymatroids |
| description |
Показано, что произвольный граф содержит совершенное паросочетание тогда и только тогда, когда специально определенный вектор является базой расширенного полиматроида, описанного субмодулярной функцией, определенной на подмножествах множества вершин. На базе этого факта можно применять различные алгоритмы решения задачи о допустимых потоках на сетях для нахождения совершенного паросочетания в заданном графе.
Показано, що довільний граф містить досконалу парносполуку тоді і тільки тоді, коли спеціально визначений вектор є базою розширеного поліматроїда, описаного субмодулярною функцією, визначеною на підмножинах множин вершин. На базі цього факту можна застосовувати різні алгоритми розв’язання задачі про допустимі потоки в мережах для знаходження досконалої парносполуки у заданому графі.
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.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/144795 |
| citation_txt |
Совершенные паросочетания и полиматроиды / Ф.А. Шарифов // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 113–119. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT šarifovfa soveršennyeparosočetaniâipolimatroidy AT šarifovfa doskonalíparnospolukiípolímatroídi AT šarifovfa perfectmatchingandpolymatroids |
| first_indexed |
2025-12-01T08:13:06Z |
| last_indexed |
2025-12-01T08:13:06Z |
| _version_ |
1850859693326467072 |