КЁНИГА ТЕОРЕМА

КЁНИГА ТЕОРЕМА

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

телей у семейства подмножеств конечного множества (см. Выбора теоремы). Распространена также формулировка К. т. в терминах графов: в графе двудольном число ребер в наибольшем паросочетании равно числу вершинного покрытия.

К. т. часто используется в различных комбинаторных вопросах, связанных с проблемами выбора и экстремальными задачами. Известны ее обобщения на случай бесконечных матриц [3].

Лит.:[1] Кonig D., "Mat. lapok", 1931, v. 38, p. 116 - 19; [2] Xapapи Ф., Теория графов, пер. с англ., М., 1973; [3] Тараканов В. Е., в кн.: Вопросы кибернетики. Тр. Семинара по комбинаторной математике,. М., 1973, с. 185-99.

В. Е. Тараканов.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Поможем сделать НИР

Смотреть что такое "КЁНИГА ТЕОРЕМА" в других словарях:

  • Теорема Кёнига (комбинаторика) — У этого термина существуют и другие значения, см. Теорема Кёнига. Теорема Кёнига одна из основных в комбинаторике. Она гласит: Если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно… …   Википедия

  • Теорема Кёнига (механика) — У этого термина существуют и другие значения, см. Теорема Кёнига. Теорема Кёнига позволяет выразить полную кинетическую энергию системы через энергию движения центра масс и энергию движения относительно центра масс. Содержание 1 Формулировка 2… …   Википедия

  • Теорема Хелли — Теорема Хелли  классический результат комбинаторной геометрии и выпуклого анализа. Предположим, что есть конечное семейство выпуклых подмножеств евклидова пространства , такое что пересечение любых из них непусто. Тогда пересечение всех… …   Википедия

  • Теорема Кёнига — Несколько утверждений носят фамилию Кёниг (все  различных учёных): Теорема Кёнига (механика) Теорема Кёнига (комбинаторика) Теорема Кёнига (теория множеств) …   Википедия

  • Гамма-алгоритм — Гамма алгоритм  алгоритм плоской укладки графа и проверки его на планарность. Содержание 1 Определения 2 Алгоритм 3 Реализация …   Википедия

  • КАРДИНАЛЬНОЕ ЧИСЛО — трансфинитное число, мощность по Кантору, кардинал множества A, такое свойство этого множества, к рое присуще любому множеству В, равномощному А. При этом два множества Аи Вназ. равномощными, если существует взаимно однозначная функция f : с… …   Математическая энциклопедия

  • Правило резолюций — В математической логике и автоматическом доказательстве теорем, правило резолюций  это правило вывода, восходящее к методу доказательства теорем через поиск противоречий; используется в логике высказываний и логике предикатов первого порядка …   Википедия

  • Энергия вращательного движения — Кинетическая энергия вращательного движения  энергия тела, связанная с его вращением. Основные кинематические характеристики вращательного движения тела  его угловая скорость ( ) и угловое ускорение. Основные динамические характеристики …   Википедия

  • ИНТУИЦИОНИЗМ — (от позднелат. intuitio, от лат. intueor пристально смотрю) направление в обосновании математики и логики, согласно которому конечным критерием приемлемости методов и результатов этих наук является наглядно содержательная интуиция. Вся математика …   Философская энциклопедия

  • РАЗЛИЧНЫХ ПРЕДСТАВИТЕЛЕЙ СИСТЕМА — для заданного семейства подмножеств множества S множество при любом взаимно однозначном отображении , обладающем свойством: для любого (здесь I произволь вое множество индексов). Другое название Р. п. с. R трансверсаль семейства F.… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»