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

Рис. 2.12. Отношение "быть эталоном” и эквивалентность

Отношение толерантности формализует Толерантность понятие сходства, близости.

Определение. Отношение hT; Mi называется отношением толерантности (толерант-

ностью), если оно рефлексивно и симметрично.

Примеры 2.21.

1. Отношение “близости”: будем считать, что два объекта "близки”, если расстояние между ними не превышает некоторого порога d. Пусть, например, x близок к y, а y близок к z (см. рисунок); при этом x и z могут быть и не близкими (транзитивность не выполняется).

dd

r r r

x y z

2. Пусть fMiji 2 Ig – некоторое семейство непустых подмножеств множества M. Если Mi \ Mj 6= ?; i 6= j, то отношение пересечения есть отношение толерантности. J

Пусть заданы отношения T; E µ M £ M.

Теорема 2.22 Если T – толерантность, E – эквивалентность

подмножества попарно толерантных элементов множества

M.

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

Классы толерантности: fa; b; c; dg, fb; d; eg; ffg. J

Классы толерантности образуют покрытие множества M. Действительно, каждый элемент x 2 M принадлежит некоторому классу толерантности (может быть – нескольким). Если элемент x 2 M нетолерантен никаким другим элементам, то он сам образует класс толерантности.

Пусть M – конечное множество мощности jMj = n. Обозначим некоторое разбиение M на k подмножеств как P (M) = fMiji 2 Ig, jP (M)j = k. Множество разбиений M на k

подмножеств обозначим как Pk(M).

Число Стирлинга второго рода S(n; k) определяется как число разбиений n-элементного множества на k подмножеств

Упрощение ЗНП.

1. Если в A существует такой элемент ai, который не входит ни в одно из подмножеств Aj

(9ai 2 A [ai 62Aj]; j = 1; : : : ; m),

то задача не имеет решения.

2. Если в A существует такой элемент ai, который принадлежит только одному подмножеству Ak и не принадлежит никакому другому подмножеству Aj

(9ai 2 A [ai 2 Ak & ai 62Aj]; j 6= k),

то подмножество Ak должно быть в любом решении, и задачу можно свести к задаче с меньшей размерностью, положив

A= A n faig и A = A n fAkg.

За м е ч а н и е. В случае 1. в матрице ktijk сумма по i-й строке равна 0, а в случае 2. – 1 (единице). I

3.Пусть Vi = fjjai 2 Ajg;

если существуют p; q 2 f1; : : : ; ng, такие, что Vq µ Vp, то aq можно удалить из A, так как любое подмножество, которое покрывает aq, покрывает и ap, т.е. ap доминирует над aq

4. Если для некоторого подсемейства A00 ½ A выполняются

Предположим, что все эти упрощения выполнены, если они возможны, и исходная ЗНП переформулирована в неприводимой форме.