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

для заданного семейства подмножеств множества S - множество при любом взаимно однозначном отображении , обладающем свойством. для любого (здесь I - произволь-вое множество индексов). Другое название Р. П. С. R- трансверсаль семейства F. Рассматриваются также частичные трансвер-сали семейства F - множества вида {p(i), }, где I0 - подмножество - взаимно однозначное отображение. Р. П. С. Применяются как в чисто комбинаторных математич. Исследованиях, так и в их приложениях к линейному программированию, математич. Экономике и кибернетике. В пределах комбинаторной математики Р. П. С. Играют существенную роль в той ее части, к-рая связана с задачами выбора и экстремальными задачами. Они используются, в частности, при изучении латинских прямоугольников, в задаче о назначениях, при исследовании матриц с неотрицательными элементами и с суммами элементов по строкам и столбцам, лежащими в заданных границах.

Критерий существования Р. П. С. Для конечного I дается теоремой Холла. Пусть на множестве Sзадано семейство из |I| = п элементов, пконечно. Для существования Р. П. С. Необходимо и достаточно, чтобы для каждого k-подмножества и каждого k, k= =1, 2, . ., п. Теорема Холла представляет собой утверждение, эквивалентное теореме Кёнига (см. Выбора теоремы).о матрицах из нулей и единиц. Этот фундаментальный критерий применим также к бесконечному I, когда все , конечны. Упомянутыми случаями, вообще говоря, исчерпывается, как показывают примеры, область применения критерия Холла, но он послужил отправной точкой для различных критериев в ряде других случаев (см. [3]), напр. А) когда существует такое подмножество , что I-I0 конечно, а Fi конечны при всех .

Б) когда I - счетное множество. Ввиду широкого использования Р. П. С. Представляют интерес алгоритмы, разработанные для их практич. Нахождения (см. [1]). Одной из основных задач о Р. П. С. Является задача о числе Р. П. С. Для конечных семейств, состоящих из конечных множеств. Она связана с вычислением перманента матрицы, состоящей из нулей и единиц. Для числа Р. П. С. Существуют оценки снизу. Пусть семейство Fсостоит из пподмножеств F1 ,. Fn и пусть они упорядочены по ' мощности. Тогда если Fудовлетворяет критерию Холла, то число Р. П. С. Не меньше, чем Вопросы, связанные с системами представителей, разрабатываются также в рамках теории магцроидов (иначе - пространств независимости, комбинаторных геометрий). Связь теории представителей с матроида-ми дается теоремой Эдмондса - Фалкерсона.

Для заданного семейства подмножеств конечного множества совокупность всех частичных трансверсалей есть совокупность независимых подмножеств нек-рого матроида. Матроид, полученный таким образом из семейства F, наз. Трансверсаль-ным матроидом для F. Многие матроиды могут быть представлены как трансверсальные для нек-рого семейства подмножеств. Понятие Р. П. С. Обобщается в различных направлениях, напр. А) р-т рансверсали для заданного семейства F={F1, . ., Fn} и целочисленного вектора суть множества , где , , _ . , ,- такие попарно различные подмножества S, что . Б) k-трансверсали для и целого числа суть подмножества для отображений со свойствами и Лит.:[1] Xолл М., Комбинаторика, пер. С англ., М., 1970. [2] Мirskу L., Transversal theory, N.

Y.- L., 1971. [3] Т а-p а к а н о в В. Е., в кн. Вопросы кибернетики, в. 18, М., 1975, с. 110-24. В.