Выбора теоремы

- группа теорем комбинаторики, связанных с выбором элементов из множества, тем или иным способом соответствующих семейству подмножеств этого множества. В. т. обычно используются в качестве теорем существования при решении различных комбинаторных задач. Ниже формулируются век-рые наиболее важные из В. т. и указываются примеры их применения. 1) Пусть [img: http://localhost:8080/file/010321-1.jpg] - некоторое семейство подмножеств данного множества [img: http://localhost:8080/file/010321-2.jpg]. Набор [img: http://localhost:8080/file/010321-3.jpg] различных элементов множества Тназ. системой различных представителей (с. р. п.) семейства S, если [img: http://localhost:8080/file/010321-4.jpg] [img: http://localhost:8080/file/010321-5.jpg] элемент [img: http://localhost:8080/file/010321-6.jpg] наз. представителем множества [img: http://localhost:8080/file/010321-7.jpg]. Напр., если [img: http://localhost:8080/file/010321-8.jpg] и Sсостоит из [img: http://localhost:8080/file/010321-9.jpg] то [img: http://localhost:8080/file/010321-10.jpg] есть с. р. п. для- S, где элемент 5 представляет множество [img: http://localhost:8080/file/010321-11.jpg], элемент 2 - множество [img: http://localhost:8080/file/010321-12.jpg] и т. д. Если же Sсоставить из множеств [img: http://localhost:8080/file/010321-13.jpg] [img: http://localhost:8080/file/010321-14.jpg] то для Sне существует с. р. п., так как [img: http://localhost:8080/file/010321-15.jpg] вместе содержат только три элемента. Теорема о системе различных представителей. Семейство [img: http://localhost:8080/file/010321-16.jpg] тогда и только тогда имеет с. р. п., когда объединение каждых kмножеств из Sсодержит по крайней мере kразличных элементов, k=1, 2,..., п. Эта теорема доказана Ф. Холлом [3] (см. также [1], [2]). С ее помощью доказывается теорема о системе общих представителей, также относящаяся к В. т. Пусть [img: http://localhost:8080/file/010321-17.jpg] суть два разбиения множества Т, в к-рых ни одно из составляющих не пусто. Множество [img: http://localhost:8080/file/010321-18.jpg] наз. системой общих представителей (с. о. п.) разбиений (1) и (2), если Rявляется с. р. п. как для семейства [img: http://localhost:8080/file/010321-19.jpg] так и для семейства [img: http://localhost:8080/file/010321-20.jpg] Напр., если [img: http://localhost:8080/file/010321-21.jpg] [img: http://localhost:8080/file/010321-22.jpg] и [img: http://localhost:8080/file/010321-23.jpg] [img: http://localhost:8080/file/010321-24.jpg] Теорема о системе общих представителей. Разбиения (1) и (2) имеют с. о. п. тогда и только тогда, когда объединение каждых kмножеств из семейства Асодержит не более kмножеств из семейства [img: http://localhost:8080/file/010321-25.jpg] (см. [1], [2]). 2) Пусть задана прямоугольная матрица. Линией в матрице наз. как строку, так и столбец этой матрицы. Теорема Кен и г а. Если элементы прямоугольной матрицы - нули и единицы, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, к-рые могут быть выбраны таким образом, чтобы среди них не нашлось двух, расположенных на одной и той же линии. Эта теорема сформулирована и доказана Д. Кёнигом ([4], с. 240; см. также [1], [2]). Она эквивалентна теореме Холла о с. р. п. Используется, напр., при доказательстве того, что нек-рые матрицы являются линейными комбинациями перестановочных матриц (перестановочная матрица - такая прямоугольная матрица Рразмера [img: http://localhost:8080/file/010321-26.jpg], состоящая из нулей и единиц, что [img: http://localhost:8080/file/010321-27.jpg], где Р' - транспонированная матрица Р, а I - единичная матрица порядка т; напр., перестановочная квадратная матрица порядка mсостоит из mединиц, расположенных так, что никакие две из них не лежат на одной линии). Иными словами, если дана матрица Аразмера [img: http://localhost:8080/file/010321-28.jpg], [img: http://localhost:8080/file/010321-29.jpg], элементами к-рой являются неотрицательные действительные числа, причем сумма элементов каждой строки в Аравна т', а сумма элементов каждого столбца равна п', то [img: http://localhost:8080/file/010321-30.jpg] где каждое Pi есть перестановочная матрица, а коэффициенты с i - неотрицательные действительные числа (ем. [1], [2]). В частности, если квадратная матрица Апорядка п, состоящая из нулей и единиц, такова, что суммы элементов по любой строке или любому столбцу равны целому положительному числу k, то [img: http://localhost:8080/file/010321-31.jpg] где все [img: http://localhost:8080/file/010321-32.jpg] - перестановочные матрицы порядка п.3) Пусть Т - конечное множество и [img: http://localhost:8080/file/010321-33.jpg] - множество всех его подмножеств, содержащих точно г элементов. Пусть [img: http://localhost:8080/file/010321-34.jpg] - произвольное упорядоченное разбиение Р r (Т).(на lсоставляющих А 1, А 2,..., Al). Пусть q1,q2,...,ql - такие целые числа, что [img: http://localhost:8080/file/010321-35.jpg] Если существует такое подмножество, содержащее qi элементов множества Т, что все его подмножества, содержащие точно rэлементов, содержатся именно в Ai, то оно наз. (qi, А i)-подмножеством множества Т. Теорема Рамсе я. Пусть заданы целые числа [img: http://localhost:8080/file/010321-36.jpg] удовлетворяющие условию (4). Тогда существует натуральное число [img: http://localhost:8080/file/010321-37.jpg] обладающее тем свойством, что для любого Целого числа [img: http://localhost:8080/file/010321-38.jpg] [img: http://localhost:8080/file/010321-39.jpg] справедливо следующее: если даны множество Т, состоящее из пэлементов, и произвольное упорядоченное разбиение (3) множества [img: http://localhost:8080/file/010321-40.jpg] на lсоставляющих [img: http://localhost:8080/file/010321-41.jpg] то Тсодержит [img: http://localhost:8080/file/010321-42.jpg] - подмножество для некоторого [img: http://localhost:8080/file/010321-43.jpg] Эта теорема доказана Ф. Рамсеем ([5]; см. также [1], [2]). Примером приложения теоремы Рамсея служит следующий результат (см. [6], [1], [2]): для любого заданного целого числа [img: http://localhost:8080/file/010321-44.jpg] существует такое целое число [img: http://localhost:8080/file/010321-45.jpg], что среди [img: http://localhost:8080/file/010321-46.jpg] точек плоскости, расположенных так, что никакие три из них не лежат на одной прямой, найдутся mточек, образующих выпуклый m-угольник.