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

Рассмотрим в конечном графе  упорядоченную -ку (т. е. упорядоченный набор из  элементов) с повторениями или без повторений

,               (18.1)

где , , при условии

, .                (18.2)

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

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

.                        (18.3)

Теперь рассмотрим все возможные пути, существующие между  и  - двумя произвольными элементами . Пусть  - обычное множество всех таких путей:

.

Определим сильнейший путь  из  в  как

.             (18.4)

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

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

Теорема 1. Пусть , тогда имеем

,                    (18.5)

где  - сильнейший путь длины , существующий между  и .

Доказательство. Достаточно рассмотреть (18.4) и (18.3), с одной стороны, и композицию  - с другой, и результат (18.5) следует немедленно. Фактически речь идет об одной и той же (maх-min) операции, представленной двумя различными образами.

Теорема 2. Пусть  и  - транзитивное замыкание ; тогда имеем

.                      (18.6)

Доказательство. Достаточно вспомнить определения  и .

Теорема 3. Пусть , если  - длина пути из  в  и , то некоторые элементы пути входят в него более одного раза; в этом пути имеется по крайней мере один контур (замкнутый путь). Если этот (или эти) контур (ы) удалить, то длина получившегося пути будет меньше или равна ; можно также установить, что

,            (18.7)

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

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

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

.                      (18.8)

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

Пример. Рассмотрим отношение , заданное на рис. 18.1 и 18.2. Результаты расчетов, представленные на рис. 18.2, будут использованы в наших дальнейших рассмотрениях. Пусть  - путь. Подсчитаем его величину:

.              (18.9)

Рис. 18.1.

Рис. 18.2.

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

         (18.10)

Тогда имеем

              (18.11)

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

 (теорема II - (18.6)).                     (18.12)

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

.             (18.13)

Сравним с

 (теорема I - (18.5)).                                (18.14)

Теперь рассмотрим путь , который содержит контур ; удалив его, находим

              (18.15)

Можно было бы ожидать, что получим 0,3; но сильнейший путь длиной 5 между  и  - это не , а , кроме того, эти два пути после удаления контура сводятся к . Все это видно на рис. 18.1, б.

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

.              (18.16)

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

.         (18.17)

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

, если ,                      (18.18)

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

.                 (18.19)

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

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

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