Cтраница 3
Теорема 1.5. Для любого отношения А транзитивное замыкание А равно пересечению Г В всех транзитивных отношений В, содержащих А. [31]
В QBE можно непосредственно ссылаться на транзитивное замыкание некоторых отношений, снабжая те или иные компоненты строк запроса постфиксами вида ( nL), где п либо положительная целая константа, либо переменная. Если п - константа, то значение этой константы определяет число уровней, на которое следует подняться или опуститься при поиске по дереву. [32]
Итак, мы доказали, что транзитивное замыкание отношения А есть объединение всех степеней этого отношения. [33]
Таким образом, построение матрицы смежностей транзитивного замыкания графа ( М, N) формально просто. Более интересной и общей является задача нахождения наилучших путей. [34]
В вычислительном отношении представляет интерес построение транзитивного замыкания графа, его редукция, нахождение максимального набора несравнимых вершин графа. [35]
Смысл этой леммы в том, что транзитивное замыкание А отношения толерантности А есть минимальная эквивалентность, включающая эту толерантность. [36]
Также не обязаны быть асимметричными произведение и транзитивное замыкание асимметричных отношений. [37]
Выполняя подходящим образом умножение матриц, строим транзитивные замыкания объединенных подграфов. [38]
В некоторых случаях, кроме такого рода свободных транзитивных замыканий, рассматривают ограниченные транзитивные замыкания, когда при движении по путям появляются непроходимые вершины, которые не могут принадлежать путям, соединяющим вершины, связанные транзитивным замыканием такого рода. [39]
Вопрос о том, как быстро можно вычислить транзитивное замыкание графа, изучался в связи с алгоритмом перемножения л X -матриц, требующим о ( и3) операций. [40]
Более эффективный и наиболее распространенный алгоритм Мунро строит вначале транзитивное замыкание графа Герца, но существенно использует метод Штрассена быстрого перемножения матриц. [41]
Во многих разделах теории программирования возникает задача построения транзитивного замыкания данного бинарного отношения; В. В. Мартынюк [42] предлагает способ решения, требующий не больше времени, чем возведение в квадрат матрицы смежности графа данного бинарного отношения. [42]
Лемма 4.7. Каково бы ни было отношение В, транзитивное замыкание В тогда и только тогда является строгим порядком, когда в графе отношения В нет контуров. [43]
Анализ нашего примера с рис. 3.2 показывает, что ограниченное обратное транзитивное замыкание может содержать в себе задающие операторы, которые, не будучи проходимыми, являются тем не менее достижимыми. Аналогично, во множестве Е ( d) задающие операторы тоже могут оказаться достижимыми. Из-за этого задающие операторы могут попасть и в пересечение. [44]
Там же описан метод построения информационного графа с помощью транзитивного замыкания относительно множества вершин. [45]