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

Если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, к-рые могут быть выбраны так, чтобы никакие две из них не лежали на одной и той же линии (термин "линия" обозначает либо строку, либо столбец в матрице). Сформулирована и доказана Д. Кёнигом [1]. К. т., одна из основных в комбинаторике, представляет собой матричный аналог критерия Холла существования системы различных представи- телей у семейства подмножеств конечного множества (см. Выбора теоремы). Распространена также формулировка К. т. в терминах графов: в графе двудольном число ребер в наибольшем паросочетании равно числу вершинного покрытия. К. т. часто используется в различных комбинаторных вопросах, связанных с проблемами выбора и экстремальными задачами. Известны ее обобщения на случай бесконечных матриц [3]. Лит.:[1] Кonig D., "Mat. lapok", 1931, v. 38, p. 116 — 19; [2] Xapapи Ф., Теория графов, пер. с англ., М., 1973; [3] Тараканов В. Е., в кн.: Вопросы кибернетики. Тр. Семинара по комбинаторной математике,. М., 1973, с. 185-99. В. Е. Тараканов.