Анотація. Показано, що довільний граф містить досконалу парносполуку тоді і тільки тоді, коли спеціально визначений вектор є базою розширеного поліматроїда, описаного субмодулярною функцією, визначеною на підмножинах множин вершин. На базі цього факту можна застосовувати різні алгоритми розв’язання задачі про допустимі потоки в мережах для знаходження досконалої парносполуки у заданому графі.

Ключові слова: досконала парносполука, граф, розширений поліматроїд.