Различных представителей система

для заданного семейства подмножеств [img: http://localhost:8080/file/041861-76.jpg] множества S - множество [img: http://localhost:8080/file/041861-77.jpg] при любом взаимно однозначном отображении [img: http://localhost:8080/file/041861-78.jpg], обладающем свойством: [img: http://localhost:8080/file/041861-79.jpg] для любого [img: http://localhost:8080/file/041861-80.jpg] (здесь I - произволь-вое множество индексов). Другое название Р. п. с. R- трансверсаль семейства F. Рассматриваются также частичные трансвер-сали семейства F - множества вида {p(i), [img: http://localhost:8080/file/041861-81.jpg] }, где I0 - подмножество [img: http://localhost:8080/file/041861-82.jpg] - взаимно однозначное отображение. Р. п. с. применяются как в чисто комбинаторных математич. исследованиях, так и в их приложениях к линейному программированию, математич. экономике и кибернетике. В пределах комбинаторной математики Р. п. с. играют существенную роль в той ее части, к-рая связана с задачами выбора и экстремальными задачами. Они используются, в частности, при изучении латинских прямоугольников, в задаче о назначениях, при исследовании матриц с неотрицательными элементами и с суммами элементов по строкам и столбцам, лежащими в заданных границах. Критерий существования Р. п. с. для конечного I дается теоремой Холла: пусть на множестве Sзадано семейство [img: http://localhost:8080/file/041861-83.jpg] из |I| = п элементов, пконечно; для существования Р. п. с. необходимо и достаточно, чтобы [img: http://localhost:8080/file/041861-84.jpg] для каждого k-подмножества [img: http://localhost:8080/file/041861-85.jpg] и каждого k, k= =1, 2,..., п. Теорема Холла представляет собой утверждение, эквивалентное теореме Кёнига (см. Выбора теоремы).о матрицах из нулей и единиц. Этот фундаментальный критерий применим также к бесконечному I, когда все [img: http://localhost:8080/file/041861-86.jpg], конечны. Упомянутыми случаями, вообще говоря, исчерпывается, как показывают примеры, область применения критерия Холла, но он послужил отправной точкой для различных критериев в ряде других случаев (см. [3]), напр.: а) когда существует такое подмножество [img: http://localhost:8080/file/041861-87.jpg], что I-I0 конечно, а Fi конечны при всех [img: http://localhost:8080/file/041861-88.jpg]; б) когда I - счетное множество. Ввиду широкого использования Р. п. с. представляют интерес алгоритмы, разработанные для их практич. нахождения (см. [1]). Одной из основных задач о Р. п. с. является задача о числе Р. п. с. для конечных семейств, состоящих из конечных множеств; она связана с вычислением перманента матрицы, состоящей из нулей и единиц. Для числа Р. п. с. существуют оценки снизу. Пусть семейство Fсостоит из пподмножеств F1,... Fn и пусть они упорядочены по ' мощности: [img: http://localhost:8080/file/041861-89.jpg] [img: http://localhost:8080/file/041861-90.jpg]. Тогда если Fудовлетворяет критерию Холла, то число Р. п. с. не меньше, чем [img: http://localhost:8080/file/041861-91.jpg] Вопросы, связанные с системами представителей, разрабатываются также в рамках теории магцроидов (иначе - пространств независимости, комбинаторных геометрий). Связь теории представителей с матроида-ми дается теоремой Эдмондса - Фалкерсона: для заданного семейства подмножеств конечного множества совокупность всех частичных трансверсалей есть совокупность независимых подмножеств нек-рого матроида. Матроид, полученный таким образом из семейства F, наз. трансверсаль-ным матроидом для F. Многие матроиды могут быть представлены как трансверсальные для нек-рого семейства подмножеств. Понятие Р. п. с. обобщается в различных направлениях, напр.: а) р-т рансверсали для заданного семейства F={F1,..., Fn} и целочисленного вектора [img: http://localhost:8080/file/041861-92.jpg] суть множества [img: http://localhost:8080/file/041861-93.jpg], где [img: http://localhost:8080/file/041861-94.jpg],, _.,,- такие попарно различные подмножества S, что [img: http://localhost:8080/file/041861-95.jpg]; б) k-трансверсали для [img: http://localhost:8080/file/041861-96.jpg] и целого числа [img: http://localhost:8080/file/041861-97.jpg] суть подмножества [img: http://localhost:8080/file/041861-98.jpg] для отображений [img: http://localhost:8080/file/041861-99.jpg] со свойствами [img: http://localhost:8080/file/041861-100.jpg] и [img: http://localhost:8080/file/041861-101.jpg]