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

Когда граф содержит по крайней мере один контур, найдется стро­ка і, в которой невозможно добиться появления нового нуля. Этот факт дает автоматическое средство для выявления контуров в графе.

Чтобы получить порядковую функцию при обратном упорядочении уровней (справа налево), когда выделяются наибольшие элементы данного порядка, можно применить ту же самую процедуру к тран­спонированной булевой матрице (строки становятся столбцами и наобо­рот). Пересматривая пример на рис. 14.3 — 14.6, находим порядковую функцию, когда уровни упорядочены справа налево. Результат изобра­жен на рис. 14.12.

Рис. 14.12

Порядковая функция нечеткого отношения порядка. Отношение по­рядка — это обычное отношение; оно рефлексивно, антисимметрично, не имеет контуров; кроме того, оно транзитивно. Следовательно, для него можно определить порядковую функцию.

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

Рис. 14.13

Рис. 14.14

Рис. 14.15

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

Соответствующий ему обычный граф изображен на рис. 14.15, б. Переставляя элементы так, что порядковая функция, при­веденная на рис. 14.14, не меняется (на рис. 14.14,а и 14.15, б представ­лен один и тот же обычный граф), мы видим, как появляется треуголь­ная матрица. Пересматривая нечеткое отношение порядка в полном порядке его элементов, выбранном таким образом, чтобы не нарушалась порядковая функция, получаем нечеткое отношение порядка, которое будем называть треугольным. Известно, что при любых вычислениях важно знать, как привести матрицу к треугольной форме.

Полезность понятия порядковой функции для нечетких отношений предпорядка. В § 2.13 мы видели, что понятие класса подобия индуци­рует в нечетком отношении квазипорядка (полный или частичный) порядок классов подобия (если квазипорядок приводимый).

Очевидно, что соответствующий этому порядку обычный граф реф­лексивный и антисимметричный, а также и транзитивный. Если пред-порядок является порядком, он может быть приведен, как это мы толь-

ко что видели, к такому виду, что соответствующая ему матрица будет

иметь треугольную форму. Если предпорядок не является порядком, то его матрицу всегда можно привести блочно-треугольному виду.

Такая блочно-треугольная форма уже была представлена в примере на рис. 13.10, который мы воспроизводим здесь вместе с соответствующей булевой матрицей (рис. 14.16), чтобы показать, что она действительно блочно-треугольного вида.

Рис. 14.16

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

2.15. Отношения различия

Рассмотрим отношение подобия определенное в § 2.10. Для удобства напомним здесь три свойства подобия:

(15.1)

(15.2-15.3) Теперь с свяжем отношение такое, что

(15.4)

Зная, что отношение обладает свойствами (15.1) — (15.3), мож­но определить и свойства отношения Начнем со свойства (15.1). Имеем:

(15.5)

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

(15.6)

Таким образом, (15.5) можно перепи­сать в виде

(15.7)

или

(15.8)

Это свойство называется (min -max)- транзитивностью. В силу (15.2)

(15.9)

И, наконец, симметрия тоже сохраняется. Итак, мы имеем

(15.10) (15.11)

(15.12)

Нечеткое бинарное отношение, обладающее свойствами (15.10) — (15.12), называется отношением различия.

Пример 1. На рис. 15.1 представлено отношение различия (кроме того, отношениесовпадает с отношением подобия на рис. 10.1).

Рис. 15.1

В качестве упражнения проверим (15.10) для нескольких пар элементов.

Дуга (А, В).

(15.13)

Дуга (А, С).

и т. д.

Пример 2. Отношение, представленное на рис. 15.2, есть отношение различия, если

(15.14)

Рис. 15.2

Это отношение получается из отношения на рис. 10.3 заменой

Положим bi = 1 —ai, i = 1, 2, 3, ... (15.15)

Пример 3. Нечеткое отношение

(15.16)

есть отношение различия. Оно получается из (10.3) заменой

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

Если d (X, Y) — расстояние между X и Y, то для Х, Y, Z Е должны выполняться условия

(15.17)

(15.18) (15.19)

где * — операция, определенная на рас­стояниях d (X, Y). Вдобавок к этим трем условиям можно логически ввести четвер­тое: d (X, X) = 0. (15.20)

Проверим (15.17) — (15.20) для

действительно, поскольку , то (15.17) удовлетворяется по определению. Соотношение (15.18) удовлетворяется в силу (15.12). Соотноше­ние (15.19), где операция * есть (min — mах)-операция, удовлетворя­ется в силу (15.10). Наконец, (15.20) тоже истинно [см. (15.11)]. Таким образом, можно положить

(15.21)

и рассматривать как расстояние между х и у.

(В этом случае можно также назвать корасстоянием между

х и у.)

(Min— mах)-расстояниемежду двумя элементами в отношении по­добия. Пусть — отношение подобия. (Min—тах)-расстоянием между х и у, х, у Е, будем называть

(15.22)

Пример 1. Обратимся опять к примеру на рис. 10.1 (повторенном на рис. 15.3) — это отношение подобияНа рис. 15.4 представлено

отношение различия, соответствующее изображенному на рис. 15.3.

Рис. 15.3

Рис. 15.4

Таким образом, имеем

(15.23)