Я правильно понимаю, что если отношения представить в виде графа, то это самый короткий путь от вершины a до вершины b? В книжке Ахо, Ульмана некоторые термины написаны, но непонятно, что имеется в виду...

задан 29 Апр '16 9:33

Нет, не это имеется в виду. Если отношение задано графом со стрелками, то от вершины a до b либо можно добраться по стрелкам (за несколько шагов), либо нельзя. В первом случае упорядоченная пара (a,b) принадлежит транзитивному замыканию отношения, заданного графом. Количество шагов при этом не важно. Транзитивное замыкание -- это и есть наименьшее транзитивное отношение, которое содержит данное отношение.

Например, если было отношение на Z, состоящее из всех пар вида (i,i+1), то замыкание будет состоять из всех пар вида (i,j) при i<j.

(29 Апр '16 9:42) falcao

@falcao мне всё равно почему-то не понятно, что его делает наименьшим..

(29 Апр '16 10:02) pavel1076
1

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

(29 Апр '16 12:25) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×8

задан
29 Апр '16 9:33

показан
736 раз

обновлен
29 Апр '16 12:25

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru