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