Теорема Кёнига
Материал из Википедии — свободной энциклопедии
Теорема Кёнига — одна из основных в комбинаторике. Она гласит:
- Если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, которые могут быть выбраны так, чтобы никакие две из них не лежали на одной и той же линии (термин «линия» обозначает либо строку, либо столбец в матрице).
Теорема Кёнига представляет собой матричный аналог критерия Холла существования системы различных представителей у семейства подмножеств конечного множества. Сформулирована и доказана Д. Кёнигом (D. Konig) в 1931 г.
