Математическая энциклопедия - выбора теоремы

группа теорем комбинаторики, связанных с выбором элементов из множества, тем или иным способом соответствующих семейству подмножеств этого множества. В. т. обычно используются в качестве теорем существования при решении различных комбинаторных задач. Ниже формулируются век-рые наиболее важные из В. т. и указываются примеры их применения.

1) Пусть некоторое семейство подмножеств данного множества .

Набор различных элементов множества Тназ. системой различных представителей (с. р. п.) семейства S, если элемент наз. представителем множества . Напр., если и Sсостоит из то есть с. р. п. дляS, где элемент 5 представляет множество , элемент 2 множество и т. д. Если же Sсоставить из множеств то для Sне существует с. р. п., так как вместе содержат только три элемента.

Теорема о системе различных представителей. Семейство тогда и только тогда имеет с. р. п., когда объединение каждых kмножеств из Sсодержит по крайней мере kразличных элементов, k=1, 2, ..., п.

Эта теорема доказана Ф. Холлом [3] (см. также [1], [2]). С ее помощью доказывается теорема о системе общих представителей, также относящаяся к В. т. Пусть

суть два разбиения множества Т, в к-рых ни одно из составляющих не пусто. Множество наз. системой общих представителей (с. о. п.) разбиений (1) и (2), если Rявляется с. р. п. как для семейства так и для семейства Напр., если и

Теорема о системе общих представителей. Разбиения (1) и (2) имеют с. о. п. тогда и только тогда, когда объединение каждых kмножеств из семейства Асодержит не более kмножеств из семейства (см. [1], [2]).

2) Пусть задана прямоугольная матрица. Линией в матрице наз. как строку, так и столбец этой матрицы.

Теорема Кен и г а. Если элементы прямоугольной матрицы нули и единицы, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, к-рые могут быть выбраны таким образом, чтобы среди них не нашлось двух, расположенных на одной и той же линии.

Эта теорема сформулирована и доказана Д. Кёнигом ([4], с. 240; см. также [1], [2]). Она эквивалентна теореме Холла о с. р. п. Используется, напр., при доказательстве того, что нек-рые матрицы являются линейными комбинациями перестановочных матриц (перестановочная матрица такая прямоугольная матрица Рразмера , состоящая из нулей и единиц, что , где Р' - транспонированная матрица Р, а I единичная матрица порядка т; напр., перестановочная квадратная матрица порядка mсостоит из mединиц, расположенных так, что никакие две из них не лежат на одной линии). Иными словами, если дана матрица Аразмера , , элементами к-рой являются неотрицательные действительные числа, причем сумма элементов каждой строки в Аравна т' , а сумма элементов каждого столбца равна п', то где каждое Pi есть перестановочная матрица, а коэффициенты с i неотрицательные действительные числа (ем. [1], [2]). В частности, если квадратная матрица Апорядка п, состоящая из нулей и единиц, такова, что суммы элементов по любой строке или любому столбцу равны целому положительному числу k, то