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

и Е — конечное множество, чтобы уяснить, что отнюдь не всегда име­ет место благоприятный случай (7.13). Но мы пойдем дальше и на этом примере продемонстрируем очень интересное явление.

Рис. 7.4

На рис. 7.4 представлено отношениеи последовательно вычис­ленные Заметим, что последовательность вычислений не схо­дится: не существует фиксированного k, после которого

Благодаря (7.16) мы знаем, что можно остановиться при k = 3. А уже после этогополучить легко.

Однако если читатель внимательно рассмотрит все полученные от­ношения, то увидит, что при k > 3 мы имеем

(7.22) (7.23)

Таким образом, здесь появляется интересный для изучения цикли­ческий феномен. Из-за отсутствия места для изучения «циклических нечетких отношений» ограничимся этими замечаниями, но рекоменду­ем исследовать их тем читателям, которые заинтересуются ими.

Замечание. Возникает следующий интересный вопрос: всегда ли композиция и (или) двух транзитивных отношений

дает транзитивное отношение. Как показывают следующие примеры, это, к сожалению, не всегда так.

Пример. Пусть — отношение, приведенное ниже в (7.24) Проверяя свойство

можно убедиться, что это отношение действительно транзитивно:

(7.24)

Пусть— отношение, заданное (7.25). Проверяя свойстве убеждаемся, что это отношение также транзитивно:

(7.25)

Теперь подсчитаем

(7.26) и

(7.27)

Включениеочевидно, удовлетворяется.

Теперь подсчитаем

(7.28) и

(7.29)

Мы видим, что включениенe выпол-

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

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

2.8. Путь в конечном нечетком графе

Рассмотрим в конечном графе GE×E упорядоченную r-ку (т. е. упорядоченный набор из r элементов) с повторениями или без повторений (другими словами, r в зависимости от случая может быть меньше, равно или больше п = card E.)

(8.1)

где Е, k = 1, 2, ..., r, при условии

(8.2)

Такую упорядоченную r-ку будем называть путем из в в графе G (или в отношении ).

С каждым путем будем связывать величину, опре-

деляемую выражением

(8.3)

Теперь рассмотрим все возможные пути, существующие между xі и хj— двумя произвольными элементами Е. Пусть С (xі, хj) — обыч­ное множество всех таких путей:

Определим сильнейший путь С (xі, xj) из xі в xj как

(18.4)

(Напомним, что в данном параграфе все рассматриваемые множества были конечными.)

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

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

(8.5)

где l*k (х, у) — сильнейший путь длины k, существующий между х и у.

Доказательство. Достаточно рассмотреть (8.4) и (8.3), с одной стороны, и композицию — с другой, и

результат (8.5) следует немедленно. Фактически речь идет об одной и той же (max—min) операции, представленной двумя различными образами.

Теорема 2. Пусть — транзитивное замыкание

тогда имеем

(8.6)

Доказательство. Достаточно вспомнить определения и l* (х, у).

Теорема 3. Пусть п = card E, если k — длина пути из xi в xj и

k > п = card E, то некоторые элементы пути входят в него более одного раза; в этом пути имеется по крайней мере один контур (замкнутый путь). Если этот (или эти) контур (ы) удалить, то длина получившегося пути будет меньше или равна n; можно также устано­вить, что

(8.7)

где— величина сильнейшего пути, длина которого от

х до у меньше или равна п.

Доказательство. После удаления контуров остается путь, длина которого самое большое равна п; тогда соотношение (8.7) удов­летворяется.

Теорема 4. Если и п = card E, тогда

(8.8)

Доказательство. Утверждение теоремы следует непосред­ственно из теоремы 2 [см. (8.6)].

Пример. Рассмотрим отношение , заданное на рис. 8.1 и 8.2.

Рис. 8.1

Рис. 8.2

Результаты расчетов, представленные на рис. 8.2, будут использова­ны в наших дальнейших рассмотрениях. Пусть (В, С, A, D) — путь. Подсчитаем его величину:

(8.9)

Теперь рассмотрим все остальные пути из В в D, длина которых меньше или равна 3; существуют только три таких пути (В, D), (В, D, D), (В, D, D, D), для которых находим

(8.10)

Тогда имеем

(8.11)

Если мы найдем на рис. 8.2, ж, то увидим

(8. 12)

С другой стороны, между В и D существуют два пути длиной 3, это (В, С, A, D) и (В, D, D, D). Тогда получаем

(8.13)