Математическая энциклопедия - различных представителей система
Связанные словари
Различных представителей система
для заданного семейства подмножеств множества 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. В.
Вопрос-ответ:
Похожие слова
Самые популярные термины
1 | 548 | |
2 | 475 | |
3 | 471 | |
4 | 464 | |
5 | 448 | |
6 | 432 | |
7 | 430 | |
8 | 425 | |
9 | 417 | |
10 | 416 | |
11 | 415 | |
12 | 405 | |
13 | 397 | |
14 | 371 | |
15 | 368 | |
16 | 362 | |
17 | 357 | |
18 | 356 | |
19 | 356 | |
20 | 355 |