Совершенные паросочетания и полиматроиды
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Совершенные паросочетания и полиматроиды
|
|
| Creator |
Шарифов, Ф.А.
|
|
| Subject |
Системний аналіз
|
|
| 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. |
|
| Date |
2019-01-04T18:23:56Z
2019-01-04T18:23:56Z 2017 |
|
| Type |
Article
|
|
| Identifier |
Совершенные паросочетания и полиматроиды / Ф.А. Шарифов // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 113–119. — Бібліогр.: 7 назв. — рос.
0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/144795 519.8 |
|
| Language |
ru
|
|
| Relation |
Кибернетика и системный анализ
|
|
| Publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України
|
|