Совершенные паросочетания и полиматроиды
Показано, что произвольный граф содержит совершенное паросочетание тогда и только тогда, когда специально определенный вектор является базой расширенного полиматроида, описанного субмодулярной функцией, определенной на подмножествах множества вершин. На базе этого факта можно применять различные алг...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2017 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/144795 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Совершенные паросочетания и полиматроиды / Ф.А. Шарифов // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 113–119. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862643829499232256 |
|---|---|
| author | Шарифов, Ф.А. |
| author_facet | Шарифов, Ф.А. |
| citation_txt | Совершенные паросочетания и полиматроиды / Ф.А. Шарифов // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 113–119. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| 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.
|
| first_indexed | 2025-12-01T08:13:06Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-144795 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-01T08:13:06Z |
| publishDate | 2017 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
| spellingShingle | Совершенные паросочетания и полиматроиды Шарифов, Ф.А. Системний аналіз |
| title | Совершенные паросочетания и полиматроиды |
| title_alt | Досконалі парносполуки і поліматроїди Perfect matching and polymatroids |
| title_full | Совершенные паросочетания и полиматроиды |
| title_fullStr | Совершенные паросочетания и полиматроиды |
| title_full_unstemmed | Совершенные паросочетания и полиматроиды |
| title_short | Совершенные паросочетания и полиматроиды |
| title_sort | совершенные паросочетания и полиматроиды |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/144795 |
| work_keys_str_mv | AT šarifovfa soveršennyeparosočetaniâipolimatroidy AT šarifovfa doskonalíparnospolukiípolímatroídi AT šarifovfa perfectmatchingandpolymatroids |