Транзитивное замыкание - Большая Энциклопедия Нефти и Газа, статья, страница 1
При поносе важно, какая скорость у тебя, а не у твоего провайдера. Законы Мерфи (еще...)

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

Cтраница 1


Транзитивное замыкание А симметричного отношения А есть симметричное отношение.  [1]

Транзитивное замыкание исходного графа получается добавлением дуг между всеми вершинами, включенными в составную. В худшем случае алгоритм требует 0 ( п3) операций.  [2]

Транзитивное замыкание отношения управления называется руководством и обозначается символом гф. В силу леммы 4.7, если в графе управления нет контуров, то отношение руководства является строгим порядком.  [3]

Транзитивным замыканием графа О ( X, А) является граф 0 с ( Х, АО А), где А является минимально возможным множеством дуг, необходимых для того, чтобы граф 6 С был транзитивным. Так как путь от; к X ] в графе О должен соответствовать дуге ( х, X) в бг с, то совершенно очевидно, что матрица достижимостей К графа Сг почти полностью совпадает с матрицей смежности А графа С1с - надо только в матрице А поставить на главной диагонали единицы.  [4]

Транзитивным замыканием графа G ( X, А) является граф Gtc ( Х, A U А), где А является минимально возможным множеством дуг, необходимых для того, чтобы граф Gtc был транзитивным. Так как путь от xt к xj в графе G должен соответствовать дуге ( xi, Xj) в Gtc, то совершенно очевидно, что матрица достижимостей R графа G почти полностью совпадает с матрицей смежности А графа Gtc - надо только в матрице А поставить на главной диагонали единицы.  [5]

Определение транзитивного замыкания ( см. определение 2.3.9) предлагает итеративный алгоритм для его вычисления.  [6]

При транзитивном замыкании графа несравнимые вершины остаются несравнимыми, при редукции несравнимыми вершинам соответствуют несравнимые вершины.  [7]

8 Объединение эквивалснтпостей. [8]

Значит, транзитивное замыкание А отношения эквивалентности А является отношением эквивалентности.  [9]

По поводу транзитивного замыкания А заметим, что оно всегда совпадает с исходным порядком А в силу его транзитивности.  [10]

Матрицей смежности транзитивного замыкания G орграфа G служит матрица достижимости R ( G) графа G.  [11]

Что называется транзитивным замыканием графа.  [12]

Замечая, что транзитивное замыкание s ( p) определено однозначно, независимо от выбора порядка элементарных транзитивных расширений, получаем еще один факт.  [13]

Тогда матрица представляет транзитивное замыкание.  [14]

Доказательство получается применением транзитивного замыкания к обеим частям включения A s В.  [15]



Страницы:      1    2    3    4