Парадигма развития науки. Методологическое обеспечение (стр. 27 )

Теперь (min —sum)-расстояния будут задаваться отношением , для которого

γ(х, у) = (х, у) = 1 - (х, у).

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

Рис. 76.

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

=

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

Рис. 77.

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

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

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

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

,

т. е.

(x, у) : d(x, у) ≤ γ(x, у).

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

(х, z)≥ [ (х, у) (у, z)].

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

(х, z)≥ [ (х, у) •(у, z)].

Но согласно свойству

a• b≤ a b, если a, b [0,1],

имеем

(х, у) (у, z) ≥ (х, у) •(у, z),

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

[ (х, у) (у, z)]≥ [ •(у, z)],

т. е.

•,

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

(max — min)-композицию.

Отсюда

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

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

1) (х, х) Е×Е: (х, х) = 0 (антирефлексивность),

2) (х, у) Е × Е: (x, у) = (у, х) (симметрия),

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

Рис. 78.

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

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

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

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

= ...

и

(х, z) = [ (х, у) (у, z)].

Тогда (min — тах)-транзитивное замыкание запишем в виде (можно обозначать = , если нет опасности спутать с (max— min)-операцией, и ...= )

=( ) ( ) ... (105)

и

(х, z) = [ (х, у) (у, z)].

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