Кёнига теорема

если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, к-рые могут быть выбраны так, чтобы никакие две из них не лежали на одной и той же линии (термин "линия" обозначает либо строку, либо столбец в матрице). Сформулирована и доказана Д. Кёнигом [1]. К. т., одна из основных в комбинаторике, представляет собой матричный аналог критерия Холла существования системы различных представи- телей у семейства подмножеств конечного множества (см. Выбора теоремы). Распространена также формулировка К. т. в терминах графов: в графе двудольном число ребер в наибольшем паросочетании равно числу вершинного покрытия. К. т. часто используется в различных комбинаторных вопросах, связанных с проблемами выбора и экстремальными задачами. Известны ее обобщения на случай бесконечных матриц [3].