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

Ключевые слова: совершенное паросочетание, граф, расширенный полиматроид.