![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Обратным транзитивным замыканием некоторой вершины хi –T-(хi)является объединение этой вершины с обратными отображениями 1-го, 2-го и т. д. n -го порядка, т. е.
T-(хi) = хi Г-1(хi)
Г-2(хi)
...
Иначе, обратное транзитивное замыкание для некоторой вершины хi – T-(хi)– это множество вершин, из которых достижима вершина хi, т. е. T-(хi) = { xj | путь из xj в хi }.
Рассмотрим построение обратного транзитивного замыкания для графа на рис. 3.1.
Г-1(х1) = { х5 }, Г-2(х1) = { х2, х4 }, Г-3(х1) = { х1 }, Г-4 (х1) = { х5 }, T-(х1) = х1 { х5 }
{ х2, х4 }
{ х1 }
{ х5 } = {х1, х2, х4, х5}.
Дата публикования: 2014-11-04; Прочитано: 575 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!