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

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]

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

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

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

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

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

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

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

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