Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
18. Путь в конечном нечетком графе
Рассмотрим
в конечном графе
где
Такую
упорядоченную С
каждым путем
Теперь
рассмотрим все возможные пути, существующие между
Определим
сильнейший путь
Кроме того, длиной пути будем называть число, на единицу меньшее числа элементов, определяющих путь. Прежде чем привести примеры, рассмотрим несколько теорем. Теорема
1. Пусть
где
Доказательство.
Достаточно рассмотреть (18.4) и (18.3), с одной стороны, и композицию Теорема
2. Пусть
Доказательство.
Достаточно вспомнить определения Теорема
3. Пусть
где
Доказательство.
После удаления контуров остается путь, длина которого самое большое равна Теорема
4. Если
Доказательство. Утверждение теоремы следует непосредственно из теоремы 2 [см. (18.6)]. Пример.
Рассмотрим отношение
Рис. 18.1.
Рис. 18.2. Теперь
рассмотрим все остальные пути из
Тогда имеем
Если
мы найдем
С
другой стороны, между
Сравним с
Теперь
рассмотрим путь
Можно
было бы ожидать, что получим 0,3; но сильнейший путь длиной 5 между Понятие
пути, определенное посредством других операторов. (Мах-
В
частности, если
Используя свойство
легко
проверить, что транзитивность оператора
Очевидно, что обратная импликация не выполняется. Следовательно,
если мы доказали (max-min)-транзитивность отношения [согласно (16.9)], то не
нужно проверять (max- Для
некоторых приложений иногда полезно иметь в своем распоряжении другие, отличные
от
|
1 |
Оглавление
|