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

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

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

1. Введение

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

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

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

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

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

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

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

1. a_i Î Х_i , i = 1, ….., n

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

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

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

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

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

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

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

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

б) Семейство множеств Х₁,......Х_n таково, что существуют k, 1 £ k < n и набор 1 £ i₁ < i₂ <…< i_k £ n такие, что множество Х_i1 È ..... È Х_ik имеет точно k классов эквивалентности по R.

Не нарушая общности, считаем, что i₁ = 1, i₂ = 2, …… i_k = k. Поскольку k £ n – 1, то по предположению индукции существует трансверсаль семейства Х_{1 .....} Х_k и отношения эквивалентности R. Пусть это будет набор x_1..... x_k. Исключим теперь элементы x_1..... x_k ,а также все элементы, эквивалентные им, из множеств Х_{k+1 , .....} , Х_n . Получим семейство множеств Х’ _{k+1 , .....} , Х’ _{n .} Покажем, что для полученного семейства выполнены условия теоремы. Предположим противное, и пусть множество Х’_{k+t1 ,} È ..... È Х’_k+ts имеет менее, чем s классов эквивалентности относительно R для некоторых индексов s ,1 £ s £ n – k, 1 £ t₁ < …. < t_s £ n – k. Тогда множество Х₁ È ….. È Х_k È Х’_k+t1 È ….. È Х’_k+ts , так же, как и множество Х₁ È ….. È Х_k È Х’_k+t1 È ….. È Х’_k+ts , имеет менее, чем k + s классов эквивалентности по отношению R , что противоречит условию теоремы. Значит по предположению индукции для множеств Х’_k+1, ....., Х’_n и отношения эквивалентности R существует трансверсаль. Объединяя ее с трансверсалью для множеств Х_{1, ..... ,} Х_k и отношения R, получим требуемую трансверсаль. Теорема доказана.

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

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

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

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

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

Определим матрицу инциденций М семейства Х₁,......Х_n и отношения эквивалентности R. Строки матрицы М соответствуют множествам Х₁,......Х_n , а столбцы – классам эквивалентности множества Х = Х₁ È...... È Х_n по отношению R. Пусть это классы С_{1 .....} С_q. Множеству Х_i и классу С_j ставим в соответствии число t_ij элементов множества Х_i , лежащих в классе С_j (если таких элементов нет – ставим нуль). Справедлива следующая теорема.

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

Доказательство. Пусть t_{1i1 · ..... ·} t_nin - произвольный элемент перманента матрицы инциденций М. Если t_{1i1 · ..... ·} t_nin = 0 для некоторого набора i₁ , ..... i_n , то значит t_pip = 0 для некоторого p Î {1, …., n} и тогда нет элементов множества Х_p в классе С_ip , поэтому трансверсали x₁ , ..... x_n с условием

x₁ Î X₁ , x₂ Î X₂ , ………x_n Î X_n

x₁ Î C_i1 , x₂ Î C_i2 ,………. x_n Î C_in

не существует. Если t_{1i1 ......} t_nin ¹ 0, то имеется t_1i1 элементов Х₁ в классе С_1i1 , t_2i2 элементов X₂ в классе C_2i2 и т.д. Таким образом, имеем t_{1i1 · ...... ·} t_nin трансверсалей семейства множеств Х₁,......Х_n и отношения эквивалентности R. Значит, каждому члену перманента t_{1i1 · ...... ·} t_nin соответствуют t_{1i1 · ...... ·} t_nin трансверсалей. Обратно, пусть x₁ , …… x_n – трансверсаль семейства множеств Х₁,......Х_n и отношения эквивалентности R. Определим перестановку i₁,… ,i_n , где x₁ Î C_i1 , x₂ Î C_i2 , ……. x_n Î С_in. Тогда трансверсали x₁ , …… x_n соответствуют t_{1i1 · ...... ·} t_nin трансверсалей y_{1 ,} ……y_n , таких, что

х₁ º y₁ (mod R) ,……, x_n º y_n (mod R).

Эти t_{1i1 · ...... ·} t_nin трансверсалей соответствуют члену перманента t_{1i1 · ...... ·} t_nin – Итак, с одной стороны,

per M = å t_{1i1 · ...... ·} t_nin ,

       (i1, ....., in)

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

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

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

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

m_i (x) = 0, если x Ï X_i ,

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

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

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

2.        a_i ¹ a_j при i ¹ j.

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

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

|| m_y (x) || ³ k для Y = X_i1 È……È X_ik

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

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

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

a = min (m₁ (a₁ ),..... , m_n (a_n )).

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

a_ij = m_i (x_j), X = {x₁ , ....., x_m } ; i = 1 , ....., n; j = 1, ....., m.

Для матрицы A определим скелетную матрицу ^-A = (b_ij), где b_ij = 0 при a_ij = 0, b _ij = 1 при a_i > 0.

Для произвольного значения a Î R⁺ определим матрицу инциденций уровня a , где A_a = (c _ij) , причем c_ij = 0 при a_ij < a, c_ij = a_ij при a_ij ³ a и, соответственно, определим скелетную матрицу инциденций уровня a : ^-A_a . Справедлива следующая теорема.

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

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

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

Объединим теперь оба подхода для характеристики систем различных представителей. Пусть дано множество X, на котором задано отношение эквивалентности R. Пусть имеется n нечетких подмножеств X_{1 ,}…. Х_n , определенных весовыми функциями m₁ , .....m_n , где m_i : X ® R⁺. .

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

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

2. a_i a_j (mod R) при i ¹ j.

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

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

функция m_y (x) для Y = X_i1 È ... È X_ik отлична от нуля не менее, чем

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

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

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

Определим матрицу инциденций P семейства X_{1 ,}…. Х_n и отношения эквивалентности R . Строки матрицы P соответствуют множествам X_{1 ,}…. Х_n , то есть функциям m₁ , ..... , m_n, а столбцы – классам эквивалентности множества X = X₁ È ... È X_n по отношению R . Пусть это классы C₁ , ....., C_q. Множеству X_i и классу C_j ставим в соответствие число t_ij элементов множества X_i , лежащих в классе C_j и для которых выполнено m_i (x_j) > 0, x_j Î C_j (если таких элементов нет – ставим нуль). Справедлива следующая теорема.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        n

H = < a ^{p1,..., ps} > порядка p_1,..., p_s , где n = p^a1₁ ,..., p^as_s - разложение n на

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

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

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

      n          n

b = (a ^p₁ )^q = (a ^p₁,..., ^p_s )^{q× p2 ...ps} Î H,

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

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

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

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

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

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

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

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

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

P_f (x₁ , ....., x_n ) = (P_{f (}x₁ , ....., x_n-1) – P_f (x₁ , ....., x_n-1,0)) x_n + P_f (x₁ , ....., x_n-1,0).

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

|| f || = å f (x₁, ....., x_n)

(x₁, ....., x_n) Î E_n

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

f × x₁ , f × x₂ , ......, f x_n , f × x₁ × x₂ , ..... , f × x₁ .... x_n

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

Теорема 10. Система 2ⁿ весов || f ||, || f × x₁ || , ...., || f × x_{1 ....} x_n || однозначно определяет псевдобулевую функцию f .

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

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

|| f × q₁ ,....., q_n || = || f x₁ ..... x_n ||

|| f × q₁ ,....., q_n-1 || = || f x₁ ..... x_n-1 ||

|| f qi₁ ,....., q_ik || = || f x_i1 ..... x_ik || ( * )

|| f q_i || = || f x_i || , i = 1,...,n

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

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

f (1, ..... , . 1) = f (x₁, ....., x_n), где

q₁ (x₁, ....., x_n) = 1,

q_n (x₁, ....., x_n) = 1.

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

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

где

q₁ (x₁, ....., x_n) = 1, q₁ (y₁, ....., y_n) = 1,

q_n (x₁, ....., x_n) = 1, q_n (y₁, ....., y_n) = 0.

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

f (q^-1 (x)) = f (x) "_x Î E_n ,

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

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

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

[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 г.

Наверх