Теорема Кёнига (комбинаторика)

Теорема Кёнига — одна из основных в комбинаторике. Она гласит:

Если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, которые могут быть выбраны так, чтобы никакие две из них не лежали на одной и той же линии (термин «линия» обозначает либо строку, либо столбец в матрице).

Теорема Кёнига представляет собой матричный аналог критерия Холла существования системы различных представителей у семейства подмножеств конечного множества. Сформулирована и доказана Д. Кёнигом в 1931 г.