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

По условию X110. Выберем произвольный элемент х1 Î Х1, и исключим элемент х1 и все эквивалентные с ним элементы из всех подмножеств Х2,......, Хп. Получим семейство Х'2,......Х'п, которое состоит из п - 1 подмножеств и удовлетворяющее условию теоремы. По предположению индукции существует трансверсаль семейства Х'2,......,Х'п и отношения эквивалентности R. Пусть это будет набор х2,....., хп. Тогда набор х1, х2,....., хп будет трансверсалью семейства Х1,......, Хп и отношения эквивалентности R.

б) Семейство множеств Х1,......,Хп такое, что существуют k, 1 k < п и набор 1 i1 < i2<...< ik п такие, что ножина Хі1 Ė..... Ė Xіk имеет точно k классов эквивалентности по R.

Не нарушая общности, считаем, что i1 = 1, i2 = 2, ....., ik = k. Поскольку k п - 1, то по предположению индукции существует трансверсаль семейства X1, ....., Хk и отношения эквивалентности R. Пусть это будет набор х1, ....., хk. Исключим теперь элементы х1, ....., хk, а также все элементы, эквивалентные им, из множеств Xk+1,...... , Хп. Получим

семейство множеств X'k+1,...... , X'п Покажем, что для полученного семейства выполнены условия теоремы.

Предположим противное, и пусть множество Х'k+t1Ė..... Ė X'k+ts имеет меньше, чем s классов эквивалентности относительно R для некоторых индексов s ,1 s п - k, 1 £t1 < .... <tsn-k. Тогда множество

X1 Ė..... Ė Х k Ė Х' k+t1Ė..... Ė X'k+ts ,

так же, как и множество

X1 Ė..... Ė Х k Ė Х' k+t1Ė..... Ė X'k+ts ,

имеет меньше, чем k + s классов эквивалентности относительно R, что противоречит условию теоремы. Значит по предположению индукции для множеств Х'k+1,.......,Х'п и отношения эквивалентности R существует трансверсаль. Объединяя ее с трансверсалью для множеств X1,.......,Хk и отношения R, получим необходимую трансверсаль. Теорема доказана.

Обобщим теперь приведенное высше определение трансверсаля семейства множеств и отношения эквивалентности.

Определение. Частной трансверсалью семейства множеств X1,......,Хп и отношения эквивалентности R назовем трансверсаль некоторого подсемейства множеств данного семейства и отношения R.

Сведением к предыдущей теореме может быть доказана следующая теорема.

Теорема 2. Семейство множеств X1,......,Хп и отношения эквивалентности R имеют частную трансверсаль мощности t тогда и только тогда, когда для любых k подмножеств из Х1,......,Хп их объединение содержит не менее k + t-n классов эквивалентности по R.

Рассмотрим теперь вопрос о числе трансверсалей семейства множеств X1,.....,.Хп и отношения эквивалентности R.

Определим матрицу инциденций М семейства X1,......,Хп и отношения эквивалентности R. Строки матрицы М соответствуют множествам X1,......,Хп, а столбцы - классам эквивалентности множества X=X1 Ė...... Ė Хп по отношению R. Пусть это классы С1,…..., Cq. Множеству Xі и классу Сj ставим в соответствие число tij элементов множества Xi, которые принадлежат классу Сj (если таких элементов нет - ставим нуль). Справедливая следующая теорема.

Теорема 3. Число трансверсалей семейства множеств X1,......,Хп и отношений эквивалентности R равно перманенту соответствующей матрицы инциденций М.

Доказательство. Пусть t1i1 ∙…∙ tпiп - произвольный элемент перманента матрицы инциденций М. Если t1i1 ∙…∙ tпiп = 0 для некоторого набора i1,....., in, то значит tpіp = 0 для некоторого р Î {1, ..... п} и тогда нет элементов множества Хр в классе Сір, поэтому трансверсали х1,.....,хп с условием

х1 Î X1 , х2 Î Х2, .........хn Î Xn

x1 Î Сі1 , х2 Î Cі2,..........xn Î Сіп

не существует. Если t1и1......tnіп 1 0, то существет t1и1 элементов X1 в классе С1и1, t2и2 элементов Х2 в классе С2и2 и т. д. Таким образом, имеем t1и1......tnіп трансверсалей семейства множеств X1,......,Хп и отношений эквивалентности R. Значит, каждому члену перманента t1и1......tnіп соответствует t1и1......tnіп трансверсалей. Обратно, пусть х1, ......,хп -

трансверсаль семейства множеств X1,......,Хп и отношения эквивалентности R. Определим перестановку i1,... ,in, где x1 Î Сі1, х2 Î Cі2,..........xn Î Сіп. Тогда трансверсали х1 , ......,хп отвечают t1и1......tnіп трансверсалей y1, ......,yn, таких, что

х1 ° y1 (mod R),......, xn °yn(mod R).

Эти t1и1......tnіп трансверсалей отвечают члену перманента t1и1......tnіп. Следовательно, с одной стороны,

per М = å t1и1......tnіп,

(i1.......in)

а с другой стороны - это число трансверсалей семейства множеств X1, ...,ХN и отношения эквивалентности R. Теорема доказана.

Замечание. Если R - отношение равенства, то теорема 1 превращается в известную теорему Хола, а теоремы 2 и 3 - в стандартные комбинаторные утверждения.

5.23. Системы различных представителей семейства нечетких множеств

Пусть X1,......Хп - семейство нечетких подмножеств конечного множества X. Для каждого і= 1......п нечеткое множество Xі, определяется весовой функцией mi : X® R+ , где R+ - множество неотрицательных действительных чисел, при этом полагаем

т i (х) = 0, если х Î Xi,

т i (х) - вес элемента х Î Xi , 0 т i (х).

Определение. Набор элементов (а1 , ....., ап ) множества X будем называть системой раздичных представителей семейства нечетких подмножеств X1,......,Хп, если выполнены условия:

1. ті(аі) > 0 для всех і = 1, ...., п,

2. аі 1 аj при і 1 j

Определим вес весовой функции т : X ® R+ как число элементов X, на которых функция т принимает ненулевое значение. Обозначим через ||т(х)|| вес функции т(х). Пусть Х1, Х2 - два нечеткие множества, которые определяются весовыми функциями т1(х) и т2(х) соответственно. Тогда множество X1 Ė Х2 имеет весовую функцию т(х) = max (m1 ( x), т2 (x)). Теперь можно указать условия, при которых существует система различных представителей для семейства нечетких множеств. Справедлива следующая теорема.

Теорема 4. Семейство нечетких множеств Х1, .... ,Хп имеет систему различных представителей в том и только в том случае, когда выполнены условия:

|| ту (х) ||1 k для Y = Хi1 Ė...... Ė Xik

для всех k = 1, ......, п и всех 1 ii, < ...< ik п.

Доказательство идейно повторяет доказательство теоремы 1.

Рассмотрим теперь вопрос о числе систем различных представителей для семейств нечетких множеств. Пусть X1, .... ,Хп - семейство нечетких множеств. Уровнем системы различных представителей (а1,.....,ап) семейства назовем число

а = min (m1 (a1),....., тп (ап)).

Определим матрицу инциденций семейства нечетких множеств Х1, ...., Хп как матрицу А = (aij) размера п × т, где

aij=mі(хj), Х={х1,....., хт}; i=1,....., n; j= 1,....., т.

Для матрицы А определим скелетную матрицу -А = (bij), где bij = 0 при

аij = 0, bij = 1 при аi > 0.

Для произвольного значения аÎR+ определим матрицу инциденций уровня а, где Аа = (сij), причем сij = 0 при аij < а, сij =аij при аij3а и, соответственно, определим скелетную матрицу инциденций уровня а : -Аа. Справедлива следующая теорема.

Теорема 5. Для произвольного уровня а Î R+ число систем различных представителей семейства нечетких множеств X1,.... Хп уровня, не меньшего, чем а, равно перманенту скелетной матрицы инциденций уровня а.

Доказательство проводится по той же схеме, что и доказательство теоремы 3.

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

Объединим теперь оба подхода для характеристики систем различных представителей. Пусть дано множество X, на котором заданы отношения эквивалентности R. Пусть имеется п нечетких подмножеств X1,.... Хп, которые определены весовыми функциями т1......тп , где ті: X® R+ .