Онлайн-калькулятор призвания

Математическая энциклопедия » Что такое «Различных Представителей Система»?

Значение слова, определение и толкование термина

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

Razlichnykh Predstaviteley Sistema

для заданного семейства подмножеств [Различных Представителей Система. Фото 1] множества S - множество [Различных Представителей Система. Фото 2] при любом взаимно однозначном отображении [Различных Представителей Система. Фото 3], обладающем свойством: [Различных Представителей Система. Фото 4] для любого [Различных Представителей Система. Фото 5] (здесь I - произволь-вое множество индексов). Другое название Р. п. с. R- трансверсаль семейства F. Рассматриваются также частичные трансвер-сали семейства F - множества вида {p(i), [Различных Представителей Система. Фото 6] }, где I0 - подмножество [Различных Представителей Система. Фото 7] - взаимно однозначное отображение.

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

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

Ввиду широкого использования Р. п. с. представляют интерес алгоритмы, разработанные для их практич. нахождения (см. [1]).

Одной из основных задач о Р. п. с. является задача о числе Р. п. с. для конечных семейств, состоящих из конечных множеств; она связана с вычислением перманента матрицы, состоящей из нулей и единиц. Для числа Р. п. с. существуют оценки снизу. Пусть семейство Fсостоит из пподмножеств F1 ,... Fn и пусть они упорядочены по ' мощности: [Различных Представителей Система. Фото 14][Различных Представителей Система. Фото 15]. Тогда если Fудовлетворяет критерию Холла, то число Р. п. с. не меньше, чем

[Различных Представителей Система. Фото 16]

Вопросы, связанные с системами представителей, разрабатываются также в рамках теории магцроидов (иначе - пространств независимости, комбинаторных геометрий). Связь теории представителей с матроида-ми дается теоремой Эдмондса - Фалкерсона: для заданного семейства подмножеств конечного множества совокупность всех частичных трансверсалей есть совокупность независимых подмножеств нек-рого матроида. Матроид, полученный таким образом из семейства F, наз. трансверсаль-ным матроидом для F. Многие матроиды могут быть представлены как трансверсальные для нек-рого семейства подмножеств.

Понятие Р. п. с. обобщается в различных направлениях, напр.: а) р-т рансверсали для заданного семейства F={F1, . . ., Fn} и целочисленного вектора [Различных Представителей Система. Фото 17] суть множества [Различных Представителей Система. Фото 18] , где [Различных Представителей Система. Фото 19] , , _ . , ,- такие попарно различные подмножества S, что [Различных Представителей Система. Фото 20]; б) k-трансверсали для [Различных Представителей Система. Фото 21] и целого числа [Различных Представителей Система. Фото 22] суть подмножества [Различных Представителей Система. Фото 23] для отображений [Различных Представителей Система. Фото 24] со свойствами [Различных Представителей Система. Фото 25] и [Различных Представителей Система. Фото 26]

Лит.:[1] Xолл М., Комбинаторика, пер. с англ., М., 1970; [2] Мirskу L., Transversal theory, N. Y.- L., 1971; [3] Т а-p а к а н о в В. Е., в кн.: Вопросы кибернетики, в. 18, М., 1975, с. 110-24. В. <Е. <Тараканов.

  • ВКонтакте

  • Facebook

  • Мой мир@mail.ru

  • Twitter

  • Одноклассники

  • Google+

См. также

  • ИОННО-ЭЛЕКТРОННАЯ ЭМИССИЯ        испускание эл-нов поверхностью тв. тела в вакуум при бомбардировке поверхности ионами. Коэфф. И.-э.

  • объём, занимаемый единицей массы в-ва; величина, обратная плотности. Единица СИ - м3/кг.