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

Сравним с

(8.14)

(Здесь оказывается, что l*3 (В, D) = l* (В, D), по это случайность: отношения на самом деле различны (см. рис. 18.2, г и ж).)

Теперь рассмотрим путь (С, А, В, D, A, D), который содержит контур (D, A, D); удалив его, находим

(8.15)

Можно было бы ожидать, что получим 0,3; но сильнейший путь длиной 5 между С и D — это не (С, А, В, D, A, D), а (С, А, В, D, D, D), кроме того, эти два пути после удаления контура сводятся к (С, А, В, D). Все это видно на рис. 8.1, б.

Понятие пути, определенное посредством других операторов. (Мах—*)-транзитивность. Величину, определяемую с помощью выра­жения (8.3), в рамках этого же определения можно распространить на другие, отличные от операции при том ограничении, что эти новые операции обладают свойством ассоциативности и монотонности. Если * — такой оператор, то

(8.16)

В частности, если * — оператор умножения, обозначаемый • и определенный в (2.35), то получим

(8.17)

Используя свойство

(8.18)

легко проверить, что транзитивность оператора влечет за собой транзитивность оператора •. Таким образом,

(8.19)

Очевидно, что обратная импликация не выполняется.

Следовательно, если мы доказали (max—min)-транзитивность от­ношения [согласно (6.9)], то не нужно проверять (max—•)-транзи­тивность.

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

2. 9. Нечеткие отношения предпорядка

Нечетким отношением предпорядка называется бинарное нечеткое отношение, обладающее свойствами транзитивности (см. (6.9)) и ре­флексивности (см. (6.7)).

Сначала рассмотрим важную теорему.

Теорема 1. Если —транзитивно и рефлексивно (т. е. предпорядок), то

(9.1)

Доказательство. Достаточно обратиться к определению транзитивности [(6.9) и (7.4)] и показать, что если

(9.2)

то

(9.3)

Поскольку

то согласно (3.2) имеем

(9.4)

Правая часть (9.4) содержит два равных члена

(9.5)

поскольку в силу рефлексивности

(9.6)

Напомним [(6.9)], что —транзитивное отношение, т. е.

(9.7)

и поэтомуне меньше, чем

Следовательно,— значение правой части (9.4), и мы

действительно имеем

(9.8)

Теорема 2. Если — предпорядок, то

(9.9)

Доказательство. Это следствие из теоремы 1. Достаточно рассмотреть (7.8) и (9.8) вместе.

Рис. 9.1

Пример 1. На рис. 9.1 изображен предпорядок

(9.10)

Его транзитивность можно проверить с помощью соотношения

(9.11)

Рефлексивность непосредственно следует из существования единиц на главной диагонали.

Наконец, можно проверить, что действительно

(9.12)

Пример 2. Рассмотрим граф GE×E, где Е — конечно, и предположим, что граф G рефлексивен. Тогда нечеткое бинарное от­ношение «в G существует путь из х в у», (где слово «путь» понимается в смысле § 2.8) есть предпорядок.

Пример 3. Нечеткое бинарное отношение где х, у N, с

функцией принадлежности

(9.13)

не предпорядок, таккак оно нетранзитивно [см. (6.12)].

Пример 4 (рис. 9.2).

(9.14)

Рис. 9.2

Это отношение на счетном бесконечном множестве Е есть предпорядок.

Нечеткий полупредпорядок. Транзитивное нечеткое отношение, не обладающее свойствами рефлексивности, называется полупредпo-рядком, или, что то же самое, нерефлексивным нечетким предпорядкоу.

Пример 1. Отношение, представленное на рис. 9.3, транзитивнo, но не рефлексивно; это отношение — полупредпорядок.

Рис. 9.3

Пример 2. Отношение на рис. 6.7 есть полупредпорядок.

Антирефлексивный нечеткий предпорядок. Частным случаем не­четкого полупредпорядка является отношение, у которого

(9.15)

В этом случае говорят, что нечеткий предпорядок антирефлексивен. Таким образом, отношение предпорядка на рис. 9.4 антирефлексивно.

Рис. 9.4

2.10. Отношение подобия

Отношение подобия, или нечетким отношением эквивалентности, называется нечеткое бинарное отношение, обладающее свойствами:

1) транзитивности [см. (6.9)]; 2) рефлексивности [см. (6.7)]; 3) сим­метричности [см. (6.6)]. Очевидно, что это предпорядок.

Сначала рассмотрим несколько примеров.

Пример 1. Рассмотрим отношение, представленное на рис. 10.1.

Рис.10.1

Можно непосредственно убедиться, что оно рефлексивно и симметрич­но. Для проверки транзитивности достаточно подсчитать Тогда согласно (9.9) должны иметь

(10.1)

Пример 2 (рис. 10.2). Если положить 0 ≤ а ≤ 1, то имеем отно­шение подобия.

Рис. 10.2

Пример 3 (рис. 10.3). Если положить

(10.2)

то это отношение подобия, определенное на бесконечном множест­ве Е.

Рис. 10.3

Пример 4. Нечеткое отношение где х, у R+, определяемое функцией принадлежности

(10.3)

есть отношение подобия.

Теорема 1. Пусть— отношение подобия. Пусть так-

же х, у, z — три элемента множества Е. Положим

(10.4)

Тогда

(10.5)

Другими словами, из этих трех величин а, b и с по крайней мере две величины равны друг другу, а третья больше двух остальных. Доказательство. Итак, по нашей гипотезе имеем

(10.6)

(10.7)

(10.8)

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

(20.9)

тогда соотношения (10.6) и (10.7) удовлетворяются, а (10.8) — нет, и если положить b = а, то уже удовлетворяются все три соотношения.

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

(10.10)

Тогда (10.6) и (10.8) удовлетворяются, а (10.7) — нет, и если по - ложить а = b, то удовлетворяются все три соотношения.