Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Изучим алгоритм 5.5 для двух интересных случаев. Первый случай — замкнутое полукольцо описанное в примере 5.9. В легко выполнить сложение и умножение, а также и операцию поскольку Действительно, так как 1 служит единичным элементом относительно строку 5 алгоритма 5.5 можно заменить на
Чтобы вычислить рефлексивно-транзитивное замыкание графа, зададим функцию разметки
Стоимость с равна 1 тогда и только тогда, когда из а в и идет путь длины или больше. Это легко проверить с помощью аксиом замкнутого полукольца
Пример 5.12. Рассмотрим граф на рис. 5.18, временно игнорируя числа на ребрах. Функция разметки задается таблицей
Рис. 5.18. Граф.
Строка 1 алгоритма 5.5 дает Строка 2 дает для так что получаем для таблицу
Теперь полагаем и выполняем цикл в строках 4 и 5, где вместо строки 5 стоит (5.4). Например, Таблицы значений приведены на рис. 5.19.
описанное в примере 5.9. В 
легко выполнить сложение и умножение, а также и операцию 
поскольку 
Действительно, так как 1 служит единичным элементом относительно 
строку 5 алгоритма 5.5 можно заменить на
равна 1 тогда и только тогда, когда из а в и идет путь длины 
или больше. Это легко проверить с помощью аксиом замкнутого полукольца 
задается таблицей
Строка 2 дает 
для так что получаем для 
таблицу
и выполняем цикл в строках 4 и 5, где вместо строки 5 стоит (5.4). Например, 
Таблицы значений 
приведены на рис. 5.19.
