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

Рис. 17.15

Замечание о сущности транзитивного расстояния. В зависи­мости от характера решаемой проблемы (min — max)-транзитив­ное замыкание матрицы расстояний может не иметь значения в прак­тических приложениях. Рассмотрим пример. Имеем следующие четы­ре сообщения:

Относительные обобщенные расстояния Хемминга для этих сооб­щений приведены на рис. 17.16, представляющем матрицу отношения несходства

Рис. 17.16

На рис. 17.17 подсчитано (min — mах)-замыкание т. е.

Рис. 17.17

Рис. 17.18

Теперь видно, что все эти сообщения являются транзитивно рав­ноотстоящими.

Такое понимание (min — mах)-транзитивного расстояния может показаться неприемлемым в числовых приложениях. Но относитель­ное обобщенное расстояние Хемминга транзитивно для обычной

(min—sum)-операции, т. е.

(17.19)

а так как δ (х, z) — это расстояние, то

(17.20)

К тем же выводам приводит рассмотрение относительного евклидо­ва расстояния.

Таким образом, каждое отношение задающее относительное обоб­щенное расстояние Хемминга (или относительное евклидово расстоя­ние), есть отношение, совпадающее со своим собственным обычным (min — sum)-транзитивным замыканием. Заметим, что правая часть (17.19) может принять значение больше 1, так как здесь производится обычное сложение, но это ничего не меняет, поскольку член слева по построению всегда принадлежит [0,1].

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

Обычное (min—sum)-различие. Декомпозиция на максималь­ные подотношения. Отношение (17.19) можно рассматривать как от­ношение различия, которое можно назвать обычным (min — sum)-различием. Как видно в примере на рис. 17.19, для расстояний d ≤k (k произвольное) не получаются обычные графы, подграфы которых устанавливают классы эквивалентности.

Рис. 17.19

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

Обратимся к рис. 17.19 и рассмотрим более подробно обычный сим­метричный граф, соответствующий d ≤ 0,42. На рис. 17.18 мы изоб­разили этот обычный граф и выделили три максимальных подотноше­ния или полных обычных графа, каждый из которых устанавливает отношение эквивалентности. Для каждого из этих подотношений рас­стояние каждого элемента до другого меньше или равно 0,42 и свойст­во (17.19) подтверждается. В общем случае такое разложение нельзя сделать без подходящего алгоритма; два таких алгоритма приводят­ся в приложении В.

Замечание. Обычное (min — sum)-pазличие недвойственно обыч­ному (max —∙ )-подобию. Двойственным к первому из этих отношений будет алгебраическое (min — sim)-различие [см. 16.23)].

Рассмотрим полностью разобранный пример, в котором появляются максимальные подотношения.

Пример. Разложим отношение различия, заданное рис. 17.13, а (см. декомпозицию на рис. 17.19).

Наконец, можно также использовать алгебраическую (а b = а-т + +b—ab) (min—sum)-транзитивность для того, чтобы получить разложение на максимальные подотношения.

Сравнивая рис. 17.14 и 17.19, можно увидеть преимущества и не­достатки использования (min — mах)-транзитивности, с одной сторо­ны, и (min — sum)-транзитивности — с другой. Первая дает классы эквивалентности, которые появляются последовательно в зависимости от величины α, интерпретация которой очень спорная. Вторая транзи­тивность дает только максимальные подотношения, в общем случае непересекающиеся; однако ее интерпретация бесспорна, особенно ког­да речь идет о приложениях в области классификации структур.

2.18. Некоторые свойства нечетких отношений

совершенного порядка

Теорема о декомпозиции для нечеткого отношения совершенного порядка. Пусть есть нечеткое отношение совершенного порядка в E×E. Отношение можно разложить в виде

(18.1)

где — отношения порядка в смысле теории обычных множеств и обозначает произведение всех элементовна величину α. Доказательство. Рефлексивность и транзитивность доказывается так же, как в (17.1). Покажем, что свойство совершенной антисимметрии (12.8) также выполняется.

1. Чтобы показать, что антисимметрично, сначала заметим, что поскольку рефлексивно, то определение

(8.2)

можно заменить

(8.3)

Антисимметричность будем доказывать методом от противного. Предположим, чтоТогда

и

и в силу антисимметрииТеперь, наоборот

предположим, что

и Положим γ=α≥β. Тогда

и из антисимметрии следует, что х = у. Значит, при сделанном предположении невозмож­но получить х ≠у.

Пример 1. На рис. 18.1 представлена декомпозиция нечеткого отношения совершенного порядка. Для большей наглядности результа­тов мы опустили нули. Под каждым расположили эскиз обычного антисимметричного графа.

Рис. 18.1

Пример 2. На рис. 28.2 показано, как происходит синтез отношения совершенного порядка.

Рис. 18.2

Расширение декомпозиционного свойства на случай приводимого предпорядка, классы подобия которого совершенно упорядочены.

Свойства (17.1) и (18.1) совпадают всегда, когда рассматривается при­водимый предпорядок, классы подобия которого устанавливают со­вершенный порядок.

Пример. На рис. 18.3 приводится пример такой декомпозиции.

Pис. 18.3

На рисунке для большей наглядности опущены нули. С другой стороны, выделены числовые элементы и классы подобия, свойства которых легко определить.

Пример синтеза см. на рис. 18.4. На рис. 18.5 показана блочно-тре-угольная форма предпорядка.

Pис. 18.4

Pис. 18.5

Совершенный полный порядок, индуцированный в совершенном частичном порядке посредством порядковой функции (случай, ког­да Е конечно). Вспоминая то, что мы изучали в § 2.14, обратимся опять к примеру на рис. 18.3 и найдем порядковую функцию для обычного графа, представляющего порядок классов; рассмотрим граф на рис. 18.6, в котором появляются три уровня No, N1, N2.

Pис. 18.6

Эти уровни на множестве классов {С1; С2, ..., С6} индуцируют (не единственный) полный порядок, такой, что при этом порядке матрица нечеткого отношения принимает блочно-треугольную форму.