English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и
лаборатории Проблем теоретической кибернетики
механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сайта Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Полнотекстовый поиск по серверу

Сотрудники :: Носов Валентин Александрович :: Публикации Носова В.А.

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

Носов В.А.
Кафедра Математической теории интеллектуальных систем

1. Введение

 

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

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

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

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

 

 

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

 

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

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

1. ai Î Хi , i = 1, ….., n

2. ai не сравнимо с a j (mod R) при i ¹ j.

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

 

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

Множество Хi1 È ..... È Хik , имеет не менее k классов эквивалентности относительно R для всех k = 1,....., n и всех 1 £ i1 < .....<ik £ n.

 

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

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

а) Семейство Х1,......Хn таково, что для любого k, 1 £ k < n и всех 1 £ i1 < ……< ik £ n множество Хi1 È ..... È Хik имеет не менее k + 1 классов эквивалентности по R.

По условию Х1 ¹ 0. Выберем произвольный элемент x1 Î Х1 ,и исключим элемент x1 и все эквивалентные с ним элементы из всех подмножеств Х2,......Хn. Получим семейство Х’2,......Х’n, состоящее из n – 1 подмножеств и удовлетворяющее условию теоремы. По предположению индукции существует трансверсаль семейства Х’2,......Х’n и отношения эквивалентности R. Пусть это будет набор x2.....xn. Тогда набор x1 , x2.....xn будет трансверсалью семейства Х1,......Хn и отношения эквивалентности R.

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

Не нарушая общности, считаем, что i1 = 1, i2 = 2, …… ik = k. Поскольку k £ n – 1, то по предположению индукции существует трансверсаль семейства Х1 ..... Хk и отношения эквивалентности R. Пусть это будет набор x1..... xk. Исключим теперь элементы x1..... xk ,а также все элементы, эквивалентные им, из множеств Хk+1 , ..... , Хn . Получим семейство множеств Х’ k+1 , ..... , Х’ n . Покажем, что для полученного семейства выполнены условия теоремы. Предположим противное, и пусть множество Х’k+t1 , È ..... È Х’k+ts имеет менее, чем s классов эквивалентности относительно R для некоторых индексов s ,1 £ s £ n – k, 1 £ t1 < …. < ts £ n – k. Тогда множество Х1 È ….. È Хk È Х’k+t1 È ….. È Х’k+ts , так же, как и множество Х1 È ….. È Хk È Х’k+t1 È ….. È Х’k+ts , имеет менее, чем k + s классов эквивалентности по отношению R , что противоречит условию теоремы. Значит по предположению индукции для множеств Х’k+1, ....., Х’n и отношения эквивалентности R существует трансверсаль. Объединяя ее с трансверсалью для множеств Х1, ..... , Хk и отношения R, получим требуемую трансверсаль. Теорема доказана.

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

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

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

 

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

 

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

Определим матрицу инциденций М семейства Х1,......Хn и отношения эквивалентности R. Строки матрицы М соответствуют множествам Х1,......Хn , а столбцы – классам эквивалентности множества Х = Х1 È...... È Хn по отношению R. Пусть это классы С1 ..... Сq. Множеству Хi и классу Сj ставим в соответствии число tij элементов множества Хi , лежащих в классе Сj (если таких элементов нет – ставим нуль). Справедлива следующая теорема.

 

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

 

Доказательство. Пусть t1i1 · ..... · tnin - произвольный элемент перманента матрицы инциденций М. Если t1i1 · ..... · tnin = 0 для некоторого набора i1 , ..... in , то значит tpip = 0 для некоторого p Î {1, …., n} и тогда нет элементов множества Хp в классе Сip , поэтому трансверсали x1 , ..... xn с условием

 

x1 Î X1 , x2 Î X2 , ………xn Î Xn

x1 Î Ci1 , x2 Î Ci2 ,………. xn Î Cin

 

не существует. Если t1i1 ...... tnin ¹ 0, то имеется t1i1 элементов Х1 в классе С1i1 , t2i2 элементов X2 в классе C2i2 и т.д. Таким образом, имеем t1i1 · ...... · tnin трансверсалей семейства множеств Х1,......Хn и отношения эквивалентности R. Значит, каждому члену перманента t1i1 · ...... · tnin соответствуют t1i1 · ...... · tnin трансверсалей. Обратно, пусть x1 , …… xn – трансверсаль семейства множеств Х1,......Хn и отношения эквивалентности R. Определим перестановку i1,… ,in , где x1 Î Ci1 , x2 Î Ci2 , ……. xn Î Сin. Тогда трансверсали x1 , …… xn соответствуют t1i1 · ...... · tnin трансверсалей y1 , ……yn , таких, что

 

х1 º y1 (mod R) ,……, xn º yn (mod R).

 

Эти t1i1 · ...... · tnin трансверсалей соответствуют члену перманента t1i1 · ...... · tninИтак, с одной стороны,

 

per M = å t1i1 · ...... · tnin ,

       (i1, ....., in)

 

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

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

 

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

 

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

mi (x) = 0, если x Ï Xi ,

mi (x) – вес элемента x Î Xi , 0 £ mi (x).

 

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

 

1.        mi (ai ) > 0 для всех i = 1, …., n,

2.        ai ¹ aj при i ¹ j.

 

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

 

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

|| my (x) || ³ k для Y = Xi1 È……È Xik

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

 

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

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

a = min (m1 (a1 ),..... , mn (an )).

 

Определим матрицу инциденций семейства нечетких множеств X1 ,…. Хn как матрицу A = (aij) размера n ´ m, где

 

aij = mi (xj), X = {x1 , ....., xm } ; i = 1 , ....., n; j = 1, ....., m.

 

Для матрицы A определим скелетную матрицу -A = (bij), где bij = 0 при aij = 0, b ij = 1 при ai > 0.

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

 

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

 

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

 

 

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

 

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

Определение. Набор элементов a1 , ....., an будем называть трансверсалью относительно отношения R , если выполнены условия:

1. mi (ai) > 0 для всех i = 1, ....., n,

2. ai aj (mod R) при i ¹ j.

 

Вопрос о существовании трансверсали семейства нечетких множеств относительно отношения R решает следующее утверждение.

 

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

функция my (x) для Y = Xi1 È ... È Xik отлична от нуля не менее, чем

на k классах Y/R для всех k = 1, ....., n, и всех 1 £ i1 < ..... < ik £ n.

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

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

Определим матрицу инциденций P семейства X1 ,…. Хn и отношения эквивалентности R . Строки матрицы P соответствуют множествам X1 ,…. Хn , то есть функциям m1 , ..... , mn, а столбцы – классам эквивалентности множества X = X1 È ... È Xn по отношению R . Пусть это классы C1 , ....., Cq. Множеству Xi и классу Cj ставим в соответствие число tij элементов множества Xi , лежащих в классе Cj и для которых выполнено mi (xj) > 0, xj Î Cj (если таких элементов нет – ставим нуль). Справедлива следующая теорема.

 

Теорема 7. Число трансверсалей семейства нечетких множеств X1 ,…. Хn и отношения эквивалентности R равно перманенту соответствующей матрицы P инциденций системы множеств и отношения R .

 

Доказательство аналогично доказательству теоремы 3.

Аналогично предыдущему можно рассмотреть вопрос об учете уровня системы различных представителей и определить число систем различных представителей уровня, не ниже заданной величины a Î R+ . Ясно, что данный вопрос также сводится к вычислению некоторых перманентов неотрицательных матриц.

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

В теории перманентов имеется большое число фактов, касающихся их эффективного вычисления или оценивания. Этому посвящена обширная литература (см. [1], [5], [6]). Однако, с алгоритмической точки зрения, задача вычисления перманента произвольной матрицы является NP-трудной [9].

 

5. Об автоморфизмах нечеткого множества

 

Пусть (X, m ) – произвольное нечеткое множество, на котором задана группа преобразований G . Пусть AG (m ) – группа автоморфизмов множества (X, m ) в группе G , т.е.

 

AG (m ) = {q Î G½m (qx) = m (x)} для всех x Î X

 

Автоморфизмы нечеткого множества сохраняют системы различных представителей произвольных семейств его подмножеств.

Определение. Собственная нетривиальная подгруппа H группы G называется плотно вложенной, если H имеет нетривиальное пересечение с каждой нетривиальной циклической подгруппой группы G .

 

Теорема 8. Группа автоморфизмов множества (X, m ) в группе G нетривиальна в том и только в том случае, если она нетривиальна в ее плотно вложенной подгруппе Н.

 

Действительно, пусть AG (m ) ¹ e . Это значит, что существует q Î G, q ¹ e такое, что qm = m . Рассмотрим циклическую группу < q > , (< q > ¹ e по условию). Очевидно, что < q > Ì AG (m ) . Поскольку H плотно вложена, то H Ç < q > ¹ e . Значит, найдется такое целое k , что qk Î H, qk ¹ e . Очевидно, что qk = m , и тогда имеем AH (m ) ¹ e . Обратное утверждение очевидно.

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

 

Теорема 9. Пусть G = < a, an = e> – циклическая группа порядка n . Тогда, если n свободно от квадратов простых числе, то G не имеет плотно вложенных подгрупп. Если n не свободно от квадратов, то группа

        n

H = < a p1,..., ps > порядка p1,..., ps , где n = pa11 ,..., pass - разложение n на

 

простые множители, будет плотно вложенной подгруппой группы G .

 

Если n свободно от квадратов простых числе, то G - прямое произведение циклических подгрупп простых порядков. Если H плотно вложена, то H содержит элементы простых порядков, а значит и группу, порожденную ими. Значит, G = H .

Если n не свободно от квадратов, то пусть b - элемент простого порядка p1 , т.е. bp1 = e . Тогда b = ak для некоторого k , k < n , т.е. выполнено akp1 = e или k × p1 º 0 (mod n). Отсюда kp1 = nq, q – целое. Следовательно, имеем

 

      n          n

b = (a p1 )q = (a p1,..., ps )q× p2 ...ps Î H,

 

т.е. элементы простых порядков входят в группу H. Любая нетривиальная подгруппа содержит циклическую подгруппу простого порядка и поэтому H имеет не пустое пересечение с любой циклической подгруппой, т.е. H – плотно вложена.

 

6. О свойствах нечеткого единичного куба

 

Нечетким единичным кубом размерности n будем называть пару (En , f ), где En – множество наборов длины n из элементов 0,1, а f – функция принадлежности элемента (x1 , ....., xn ) множеству En , т.е. f : En ® R+ . по существу, нечеткий единичный куб определяется псевдобулевой функций f (x1 , ....., xn ) .

Для задания нечеткого множества (En , f) могут быть использованы различные способы представления функции f .

Ниже будут использоваться представления псевдобулевых функций в виде действительных многочленов и системы весов. Напомним некоторые определения.

Представление псевдобулевой функции f (x1 , ....., xn ) действительным многочленом определим индуктивно.

При n = 1 функцию f (x) представляет многочлен

 

Pf (x) = (f (1) – f (0)) x + f (0).

 

Если для n – 1 представляющий многочлен определен, то для n функцию f (x1 , ....., xn ) представляет многочлен

 

Pf (x1 , ....., xn ) = (Pf (x1 , ....., xn-1) – Pf (x1 , ....., xn-1,0)) xn + Pf (x1 , ....., xn-1,0).

 

Определим вес псевдобулевой функции f (x1, ....., xn) как действительную сумму

 

|| f || = å f (x1, ....., xn)

(x1, ....., xn) Î En

 

Для произвольной псевдобулевой функции f (x1, ....., xn) образуем 2n - 1 функций следующим образом:

f × x1 , f × x2 , ......, f xn , f × x1 × x2 , ..... , f × x1 .... xn

 

Легко доказывается.

 

Теорема 10. Система 2n весов || f ||, || f × x1 || , ...., || f × x1 .... xn || однозначно определяет псевдобулевую функцию f .

 

Пусть (En , f) - нечеткий единичный куб. Пусть q : En ® En – некоторая биекция. Рассмотрим вопрос об условиях, когда биекция q является автоморфизмом множества (En , f). Ясно, что в этом случае q представляется семейством булевых функций q (q1 , ..... , qn ) .

 

Теорема 11. Биекция (q1 ,....., qn) является автоморфизмом нечеткого множества (En , f) тогда и только тогда, когда выполнены 2n - 1 условий

 

|| f × q1 ,....., qn || = || f x1 ..... xn ||

|| f × q1 ,....., qn-1 || = || f x1 ..... xn-1 ||

|| f qi1 ,....., qik || = || f xi1 ..... xik || ( * )

|| f qi || = || f xi || , i = 1,...,n

 

Доказательство заключается в непосредственной проверке эквивалентности условий ( * ) и условия q – автоморифизм поэлементно.

Так, первое равенство в ( * ) дает

 

f (1, ..... , . 1) = f (x1, ....., xn), где

q1 (x1, ....., xn) = 1,

 

qn (x1, ....., xn) = 1.

 

Из следующего равенства получаем

 

f (1, ....., 1,0) + f (1, .....1,1) = f (x) + f (y),

где

q1 (x1, ....., xn) = 1, q1 (y1, ....., yn) = 1,

qn (x1, ....., xn) = 1, qn (y1, ....., yn) = 0.

 

Продолжая таким образом, получаем

f (q-1 (x)) = f (x) "x Î En ,

 

т.е. – автоморифизм нечеткого множества.

 

Ясно, что справедливо и обратное утверждение.

 

Список литературы

[1] Минк Х. Перманенты. М., Мир, 1982.

[2] Холл М. Комбинаторика. М., 1970.

[3] Липский В. Комбинаторика для программистов. М., 1988.

[4] Сачков В.Н. Введение в комбинаторные методы дискретной математики. М., 1982.

[5] Носов В.А., Сачков В.Н., Тараканов В.Е. Комбинаторный анализ. Матричные проблемы, теория выбора. Итоги науки и техники. Сер. Теория вер., матем. статист., теорет. киберн., т. 18, 1981, с. 53-94.

[6] Носов В.А., Сачков В.Н., Тараканов В.Е. Комбинаторный анализ. Неотрицательные матрицы, алгоритмические проблемы. Итоги науки и техники. Сер. Теория вер., матем. Статист., теорет. киберн., т.21, 1983, с. 120-178.

[7] Нечеткие множества и теория возможностей. Сб. работ под ред. Ячера, М., 1986.

[8] Дюкова Л.Л. Условия существования системы различных множественных представителей. Матем. Заметки, 1982, 32, № 6, 789-798.

[9] Алексеев В.Б., Носов В.А. NP-полные задачи и их полиномиальные варианты. Обозрение промышленной и прикладной математики, 1997, т.4. вып. 2, 165-193.

[10] Гафуров Д.З. Система представителей семейства множеств. Вычисл. центр СО АН СССР, Препр., 1983, № 419, 12 с.

[11] Horak P. Extending partial systems of distinct represetatives. Discrete Math., 1991, 91, № 1, с. 95-98.

[12] Aigner M., Erdos P., Grieser D. On the representing number of intersecting families. “Arch. Math.”, 1987, 49, № 2, 114-118.

[13] Тараканов В.Е. О системах преставителей. В сб. “Вопросы кибернетики”, вып. 16, М., 1975, 110-124.

[14] Арлазаров В.Л., Бараев А.М., Гольфанд Я.Ф, Фараджев И.А. Построение с помощью ЭВМ всех латинских квадратов порядка 8. В сб. “Алгоритм. исслед. в комбинаторике”, М., 1978, 129-141.

Интеллектуальные системы,т.3,вып.1-2, 1998 г.

Наверх

   © 2001-2015 г. Кафедра Математической теории интеллектуальных систем, лаборатория Проблем теоретической кибернетики Написать вебмастеру   
XWare
 Полнотекстовый поиск
 
Только точная форма слов      Выводить по результатов на странице
Rambler's Top100 Рейтинг@Mail.ru