Дискретно-непрерывная математика (стр. 59 )

Только что была доказана теорема Кенига-Эгервари с помощью теоремы Холла, а доказательство теоремы Холла с помощью теоремы Кенига-Эгервари значительно проще. Следовательно, эти две теоремы в некотором смысле эквивалентны.

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

Сформулируем необходимое и достаточное условие для того, чтобы два семейства и имели общую трансверсаль; заметим, что эта теорема сводится к теореме Холла, если положить для

Теорема Пусть — непустое конечное множество, а и — два семейства его непустых подмножеств. Тогда и имеют общую трансверсаль в том и только в том случае, если для всех подмножеств и множества

Набросок доказательства. Рассмотрим семейство подмножеств множества (считаем, что и не пересекаются), где множеством индексов также является и где , если , и , если Нетрудно проверить, что и имеют общую трансверсаль тогда и только тогда, если семейство имеет трансверсаль. Применяя затем теорему Холла к семейству , получим нужный результат.

Условия, при которых существует общая трансверсаль для трех семейств непустых подмножеств некоторого множества, пока что не известны, и задача нахождения таких условий кажется очень трудной. Многие попытки решения этой задачи используют теорию матроидов; и действительно, некоторые задачи теории трансверсалей становятся почти тривиальными, если рассматривать их с точки зрения теории матроидов.

5.22. Системы различных представителей семейств множеств, которые принадлежат различным классам по отношению эквивалентности

Одной из тенденций, которые сложились при обработке больших объемов информации, является разбиения множества обрабатываемых данных на классы толерантности по некоторому рефлексивному и симметричному отношению. Часто таким отношением служит «отношение соседства» на некоторой метрике. Следующим шагом является выделения системы представителей для классов толерантности и формирование системы «эталонных представителей». Реализация данного подхода приводит к необходимости решения комбинаторных задач, связанных с определением существования системы различных представителей для семейства множеств, и определение числа систем различных представителей, которые удовлетворяют различным ограничениям. Среди ограничений такого рода обычно используются ограничения на разграничение представителей. Разграничение представителей может вводиться как принадлежность различным классам по некоторому отношению эквивалентности, или через значение весовой функции.

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

Для случая обычных систем множеств сформулированные вопросы рассматриваются в теории систем представителей (теории трансверсалей), которая, как мы видели, представляет важную часть современной комбинаторики. Основу представляют уже упоминавшиеся классические результаты Холла, Фробениуса, Кенига и др. по существованию и перечислению систем различных представителей.

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

Пусть дано множество X, на котором заданы отношения эквивалентности R. Пусть есть семейство подмножеств Х1,......, Хп множества X.

Определение. Систему элементов а1,....., ап будем называть трансверсалью семейства X1,......, Хп и отношения R, если выполнены условия:

1. аі Î Хі, i = 1, ....., п,

2. аі не сравнимо с aj (mod R) при i 1 j.

Вопрос существования трансверсали семейства Х1,......, Хп и отношения R решается следующим утверждением.

Теорема 1. Для семейства множеств Х1,......, Хп и отношения эквивалентности R существует трансверсаль в том и только в том случае, когда выполнены условия:

Множество Хі1 Ė..... Ė Xіk, имеет не менее k классов эквивалентности относительно R для всех k = 1,......, п и всех 1 i1 <.....<iіk n.

Доказательство. Если для семейства Х1,......, Хп и отношения эквивалентности R существует трансверсаль, то тогда для каждого k = 1, ...., п и любых 1 i1 <......< iіk n число классов множества Хі1 Ė..... Ė Xіk по отношению R будет не меньше, чем k. Поэтому условия теоремы необходимы.

Пусть теперь условия теоремы выполнены. Докажем достаточность индукцией по п. При п = 1 утверждение очевидно. Пусть утверждение справедливо для любого семейства из п -1 подмножеств. Пусть дано семейство из п подмножеств X1,......Хп. Возможны два случая.

а) Семейство X1,......, Хп такое, что для каждого k, 1 k < п и всех

1 i1 < ......< ik n множество Хі1 Ė..... Ė Xіk имеет не меньше k + 1 классов эквивалентности по R.