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

(16.24)

На рис. 16.7 представлены (min — sum)-расстояния между различ­ными элементами. Так, γ (С, F) = 0,58; γ (D, В) = 0,4.

Рис. 16.7

Пример 2, Вернемся к примеру на рис. 16.5. (Мах — •)-композиция немедленно показывает, что

(16.25)

Отношениепредставлено на рис. 16.8.

Рис. 16.8

Очевидно, что

(16.26)

и, как следствие,

(16.27)

Замечание. Представляется, что γ (х, у) дает в практическом отно­шении лучшее расстояние, чем d (х у), это может оказаться очень важным для всего, что связано с проблемами сходства, и объясняет наш интерес к (min — sum)-расстоянию. Однако, как мы увидим на рис. 17.10, декомпозиция на обычные частичные графы дальше невозможна.

Теорема 1. Пусть — от­ношение сходства. Тогда всегда справедливо включение

(16.28)

т. е.

(16.29)

Доказательство. По условию (max — min)-транзитивности имеем

(16.30)

По условию (max — •)-транзитивности имеем

(16.31)

Но согласно (8.18)

(16.32)

откуда следует

(16.33)

т. е.

(16.34)

где, напоминаем, • обозначает (max—•)-композицию, а обозначает (max — min)-композицию. Отсюда

(16.35)

и, следовательно,

(16.36)

Отношение несходства. Отношение , такое, что

(16.37)

(16.38)

называется отношением несходства (рис. 16.9).

Pис. 16.9

Рассмотрим некоторые очевидные свойства. Если R — отношение сходства, то — отношение несходства и наоборот.

Теорема 2. Еслиесть (max — min) - транзитивное замыкание

отношения сходства то есть (min—max)-транзитивное замыка­ние соответствующего отношения несходства.

Доказательство. (Мах — min)-транзитивное замыкание выражается посредством (7.8) и (7.3); таким образом,

(16.39)

и

(16.40)

Тогда (min — тах)-транзшпивное замыкание запишем в виде

(16.41)

и

(16.42)

(Можно обозначатьесли нет опасности спутать с (max—

min)-операцией, и)

Пусть— отношение сходства, — отношение подобия, — отношение несходства и — отношение различия. Покажем, что

(16.43)

В (15.4)— (15.8) мы уже показали, что если .-тран-

зитивно, то и -транзитивно.

Покажем теперь, что

(16.44)

Для проверки этого поступим так же, как в (15.4) — (15.8):

(16.45)

(16.46)

Это доказывает (16.44). Теперь запишем

(16.47)

и, наконец, согласно (16.44)

Рассмотрим пример. Возьмем опять отношение сходства, представ­ленное на рис. 16.1, для которого соответствующее отношение подо­бия представлено на рис. 16.2, а матрица расстояний — на рис. 16.3. Мы встретимся с этими отношениями еще раз при расчетах, которыми

заканчивается нахождениена рис. 16.10, г—з.

Рис. 16.10

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

Теорема 3. Пустьесть (max — min)-транзитивное замыкание некоторого нечеткого отношения транзитивное замыкание Тогда

(16.48)

Это утверждение можно сформулировать и так: можно переста­вить порядок операций но при этом заменяется на(и на­оборот). С учетом этого читатель может искать другие интересные свойства, связанные с (max — min)- и (min — max)-транзитивными замыканиями, которые он может характеризовать как дуальные, не боясь упре­ков в использовании этого слова.

2.17. Некоторые свойства отношений подобия и сходства

Теорема декомпозиции для отношения подобия. Пусть—отно­шение подобия в Е × Е. Тогдаможно разложить так:

(17.1)

при

где— отношения эквивалентности в смысле обычной теории мно­жеств и обозначает, что все элементы обычного отношения

умножаются на α.

Доказательство. Во-первых,откуда следует, что при α [0,1]; следовательно, обладает свойством рефлексивности.

Во-вторых, положив получим, что

и в силу симметрии Следовательно, обладает свойством симметрии.

В-третьих, для всех α [0,1] предположим, что и

тогда следовательно, по транзитивности транзитивно.