|
"
0
C
F
G
H
K
L
N
P
S
T
W
Z
А
Б
В
Г
Д
Е
Ж
З
И
Й
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Ш
Э
Ю
Я
КЁНИГА ТЕОРЕМАЗначение КЁНИГА ТЕОРЕМА в математической энциклопедии: если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, к-рые могут быть выбраны так, чтобы никакие две из них не лежали на одной и той же линии (термин "линия" обозначает либо строку, либо столбец в матрице). Сформулирована и доказана Д. Кёнигом [1]. К. т., одна из основных в комбинаторике, представляет собой матричный аналог критерия Холла существования системы различных представи- телей у семейства подмножеств конечного множества (см. Выбора теоремы). Распространена также формулировка К. т. в терминах графов: в графе двудольном число ребер в наибольшем паросочетании равно числу вершинного покрытия. К. т. часто используется в различных комбинаторных вопросах, связанных с проблемами выбора и экстремальными задачами. Известны ее обобщения на случай бесконечных матриц [3]. Лит.:[1] Кonig D., "Mat. lapok", 1931, v. 38, p. 116 - 19; [2] Xapapи Ф., Теория графов, пер. с англ., М., 1973; [3] Тараканов В. Е., в кн.: Вопросы кибернетики. Тр. Семинара по комбинаторной математике,. М., 1973, с. 185-99. В. Е. Тараканов. |
|
|
|