|
Я правильно понимаю, что если отношения представить в виде графа, то это самый короткий путь от вершины a до вершины b? В книжке Ахо, Ульмана некоторые термины написаны, но непонятно, что имеется в виду... задан 29 Апр '16 9:33 
pavel1076 |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
29 Апр '16 9:33
показан
832 раза
обновлен
29 Апр '16 12:25
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Нет, не это имеется в виду. Если отношение задано графом со стрелками, то от вершины a до b либо можно добраться по стрелкам (за несколько шагов), либо нельзя. В первом случае упорядоченная пара (a,b) принадлежит транзитивному замыканию отношения, заданного графом. Количество шагов при этом не важно. Транзитивное замыкание -- это и есть наименьшее транзитивное отношение, которое содержит данное отношение.
Например, если было отношение на Z, состоящее из всех пар вида (i,i+1), то замыкание будет состоять из всех пар вида (i,j) при i<j.
@falcao мне всё равно почему-то не понятно, что его делает наименьшим..
@pavel1076: у нас есть какое-то отношение p. Это множество упорядоченных пар. Оно содержится хотя бы в одном транзитивном отношении -- например, в полном. Для всех транзитивных отношений, содержащих p, рассмотрим их пересечение. Оно является транзитивным, и при этом оно содержится в любом транзитивном отношении, содержащим данное. Поэтому оно будет наименьшим относительно включения подмножеств.