С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
Мат. логика и множества
Войти
Регистрация
Восстановить пароль
 
jestero
11 / 11 / 2
Регистрация: 17.02.2014
Сообщений: 947
1

Что такое транзитивное замыкание?

06.03.2016, 07:46. Просмотров 344. Ответов 8
Метки нет (Все метки)

Можете привести парочку простых примеров, а то не очень понял что это такое и как применяется.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.03.2016, 07:46
Ответы с готовыми решениями:

Как задать транзитивное замыкание?
M=\begin{Bmatrix}1,3,5,7\end{Bmatrix} Отношение R=...

Алгоритмом Уоршелла построить транзитивное замыкание для отношения
Алгоритмом Уоршелла построить транзитивное замыкание для отношения a+b=10,...

чему равно обратное транзитивное замыкание от пустого множества?
чему равно обратное транзитивное замыкание от пустого множества?

Как построить транзитивное замыкание при помощи обхода в ширину
Здравствуйте! Не подскажите ли как построиь транзитивное замыкание при...

Транзитивное замыкание
Добрый вечер! Разбираю транзитивное замыкание и насколько я поняла,...

8
iifat
2366 / 1519 / 133
Регистрация: 05.06.2011
Сообщений: 4,220
06.03.2016, 07:51 2
Ну, «предок» — транзитивное замыкание «родитель»
1
jestero
11 / 11 / 2
Регистрация: 17.02.2014
Сообщений: 947
06.03.2016, 07:54  [ТС] 3
Цитата Сообщение от iifat Посмотреть сообщение
Ну, «предок» — транзитивное замыкание «родитель»
А что требуется в подобном задании вычислить?
0
8-BITOV
541 / 484 / 104
Регистрация: 05.05.2014
Сообщений: 1,108
06.03.2016, 10:56 4
Цитата Сообщение от jestero Посмотреть сообщение
А что требуется в подобном задании
Отношение не является транзитивным. Ему принадлежат пары (a,b) (b, c) но пара (a,c) не принадлежит. Построение транзитивного замыкания - это устранение таких безобразий путем включения (a,c) в замыкания. Другими словами (x,y) принадлежит Замыканию тогда и только тогда, когда существует путь x -> y
0
iifat
2366 / 1519 / 133
Регистрация: 05.06.2011
Сообщений: 4,220
06.03.2016, 13:39 5
Цитата Сообщение от jestero Посмотреть сообщение
А что требуется в подобном задании вычислить?
Ну вот представь себе, что стрелка означает «родитель». Построй «предок».
0
jestero
11 / 11 / 2
Регистрация: 17.02.2014
Сообщений: 947
06.03.2016, 15:20  [ТС] 6
То есть между стрелками нужно вставлять ещё какие то вершины графа?
0
8-BITOV
541 / 484 / 104
Регистрация: 05.05.2014
Сообщений: 1,108
06.03.2016, 20:02 7
Наоборот. Нужно новые стрелочки рисовать.
Давай попробуем разжевать. У тебя есть Папа. У Папы - его Мама. Тебе она - Бабушка. Но отношение "Родитель" на нее не распространяется. Однако, она - твой предок. И для замыкания надо провести стрелочку от Бабушки к тебе. И если пройти по всем цепочкам типа "Адам родил Сифа, Сиф родил Еноса, Енос родил Каиннана, Каиннан - Маделеила...", то замыкание будет в том, что все эти ребята - потомки Адама. И если родитель не транзитивен, то потомок - вполне.
2
iifat
2366 / 1519 / 133
Регистрация: 05.06.2011
Сообщений: 4,220
07.03.2016, 10:13 8
Цитата Сообщение от 8-BITOV Посмотреть сообщение
надо провести стрелочку от Бабушки к тебе
Не помню точно рисунок, но там, кажется, направления были от детей к родителям. Так что — от тебя к бабушке. Если, конечно, я правильно запомнил.
0
8-BITOV
541 / 484 / 104
Регистрация: 05.05.2014
Сообщений: 1,108
07.03.2016, 17:20 9
Цитата Сообщение от iifat Посмотреть сообщение
там, кажется, направления были от
Ну, это дело договорное. Если элемент (a,b) принадлежит отношению, то это можно записывать этот факт так a-->b или a<--b

Добавлено через 5 часов 23 минуты
Прошу прощения, сам запутался. Конечно, транзитивное расширение отношения родитель есть отношение предок
0
07.03.2016, 17:20
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.03.2016, 17:20

Рефлексивное, симметричное и не транзитивное отношение
Уже который час думаю над примером рефлексивного, симметричного и не...

Рефлексивное, транзитивное и не симметричное бинарное отношение
Помогите с примером рефлексивного, не симметричного и транзитивного бинарного...

Что такое Алеф-1
Начиналось все с безобидного школьного вопроса...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru