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

Например, если — множество городов, и на них задано отношение , означающее, что если , то «существует автобусный маршрут из в «, то транзитивным замыканием этого отношения будет отношение «существует возможность добраться из в , передвигаясь на автобусах».

Существование и описание

Транзитивное замыкание существует для любого отношения. Для этого отметим, что пересечение любого множества транзитивных отношений транзитивно. Более того, обязательно существует транзитивное отношение, содержащее как подмножество (например, ).

Построение транзитивного замыкания

Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения как отношение такое, что тогда и только тогда, когда существуют такие, что , то есть существует путь из вершины в вершину по рёбрам графа отношения.

Для построения транзитивного замыкания отношения, заданного матрицей смежности, используется алгоритм Флойда — Уоршелла.

Свойства транзитивного замыкания

• Транзитивное замыкание рефлексивного отношения рефлексивно, так как транзитивное отношение содержит исходное отношение
• Транзитивное замыкание симметричного отношения симметрично. Действительно, пусть , значит существуют такие, что . Но из симметричности отношения следует , а, следовательно,
• Транзитивное замыкание не сохраняет антисимметричность, например, для отношения на множестве
• Транзитивное замыкание транзитивного отношения — оно само

Рефлексивно-транзитивное замыкание

Отношение , где

иногда называют рефлексивно-транзитивным замыканием, хотя часто под «транзитивным замыканием» подразумевается именно . Обычно различия между этими отношениями не являются значительными.

См. также

• Транзитивное отношение
• Алгоритм Флойда-Уоршалла (построение транзитивного замыкания отношения)
• Транзитивный остов

Источники информации

• Wikipedia | Transitive closure (англ.)

From Wikipedia, the free encyclopedia

This article is about the transitive closure of a binary relation. For the transitive closure of a set, see transitive set § Transitive closure.

In mathematics, the transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive. For finite sets, «smallest» can be taken in its usual sense, of having the fewest related pairs; for infinite sets it is the unique minimal transitive superset of R.

For example, if X is a set of airports and x R y means «there is a direct flight from airport x to airport y» (for x and y in X), then the transitive closure of R on X is the relation R⁺ such that x R⁺ y means «it is possible to fly from x to y in one or more flights». Informally, the transitive closure gives you the set of all places you can get to from any starting place.

More formally, the transitive closure of a binary relation R on a set X is the transitive relation R⁺ on set X such that R⁺ contains R and R⁺ is minimal; see Lidl & Pilz (1998, p. 337). If the binary relation itself is transitive, then the transitive closure is that same binary relation; otherwise, the transitive closure is a different relation.

Conversely, transitive reduction adduces a minimal relation S from a given relation R such that they have the same closure, that is, S⁺ = R⁺; however, many different S with this property may exist.

Both transitive closure and transitive reduction are also used in the closely related area of graph theory.

Transitive relations and examples[edit]

A relation R on a set X is transitive if, for all x, y, z in X, whenever x R y and y R z then x R z. Examples of transitive relations include the equality relation on any set, the «less than or equal» relation on any linearly ordered set, and the relation «x was born before y» on the set of all people. Symbolically, this can be denoted as: if x < y and y < z then x < z.

One example of a non-transitive relation is «city x can be reached via a direct flight from city y» on the set of all cities. Simply because there is a direct flight from one city to a second city, and a direct flight from the second city to the third, does not imply there is a direct flight from the first city to the third. The transitive closure of this relation is a different relation, namely «there is a sequence of direct flights that begins at city x and ends at city y«. Every relation can be extended in a similar way to a transitive relation.

An example of a non-transitive relation with a less meaningful transitive closure is «x is the day of the week after y«. The transitive closure of this relation is «some day x comes after a day y on the calendar», which is trivially true for all days of the week x and y (and thus equivalent to the Cartesian square, which is «x and y are both days of the week»).

Existence and description[edit]

For any relation R, the transitive closure of R always exists. To see this, note that the intersection of any family of transitive relations is again transitive. Furthermore, there exists at least one transitive relation containing R, namely the trivial one: X × X. The transitive closure of R is then given by the intersection of all transitive relations containing R.

For finite sets, we can construct the transitive closure step by step, starting from R and adding transitive edges.
This gives the intuition for a general construction. For any set X, we
can prove that transitive closure is given by the following expression

where is the i-th power of R, defined inductively by

and, for ,

where denotes composition of relations.

To show that the above definition of R⁺ is the least transitive relation containing R, we show that it contains R, that it is transitive, and that it is the smallest set with both of those characteristics.

• : contains all of the , so in particular contains .
• is transitive: If , then and for some by definition of . Since composition is associative, ; hence by definition of and .
• is minimal, that is, if is any transitive relation containing , then : Given any such , induction on can be used to show for all as follows: Base: by assumption. Step: If holds, and , then and for some , by definition of . Hence, by assumption and by induction hypothesis. Hence by transitivity of ; this completes the induction. Finally, for all implies by definition of .

Properties[edit]

The intersection of two transitive relations is transitive.

The union of two transitive relations need not be transitive. To preserve transitivity, one must take the transitive closure. This occurs, for example, when taking the union of two equivalence relations or two preorders. To obtain a new equivalence relation or preorder one must take the transitive closure (reflexivity and symmetry—in the case of equivalence relations—are automatic).

In graph theory[edit]

In computer science, the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node d in one or more hops? A binary relation tells you only that node a is connected to node b, and that node b is connected to node c, etc. After the transitive closure is constructed, as depicted in the following figure, in an O(1) operation one may determine that node d is reachable from node a. The data structure is typically stored as a Boolean matrix, so if matrix[1][4] = true, then it is the case that node 1 can reach node 4 through one or more hops.

The transitive closure of the adjacency relation of a directed acyclic graph (DAG) is the reachability relation of the DAG and a strict partial order.

The transitive closure of an undirected graph produces a cluster graph, a disjoint union of cliques. Constructing the transitive closure is an equivalent formulation of the problem of finding the components of the graph.^[1]

In logic and computational complexity[edit]

The transitive closure of a binary relation cannot, in general, be expressed in first-order logic (FO).
This means that one cannot write a formula using predicate symbols R and T that will be satisfied in
any model if and only if T is the transitive closure of R.
In finite model theory, first-order logic (FO) extended with a transitive closure operator is usually called transitive closure logic, and abbreviated FO(TC) or just TC. TC is a sub-type of fixpoint logics. The fact that FO(TC) is strictly more expressive than FO was discovered by Ronald Fagin in 1974; the result was then rediscovered by Alfred Aho and Jeffrey Ullman in 1979, who proposed to use fixpoint logic as a database query language.^[2] With more recent concepts of finite model theory, proof that FO(TC) is strictly more expressive than FO follows immediately from the fact that FO(TC) is not Gaifman-local.^[3]

In computational complexity theory, the complexity class NL corresponds precisely to the set of logical sentences expressible in TC. This is because the transitive closure property has a close relationship with the NL-complete problem STCON for finding directed paths in a graph. Similarly, the class L is first-order logic with the commutative, transitive closure. When transitive closure is added to second-order logic instead, we obtain PSPACE.

In database query languages[edit]

Since the 1980s Oracle Database has implemented a proprietary SQL extension CONNECT BY... START WITH that allows the computation of a transitive closure as part of a declarative query. The SQL 3 (1999) standard added a more general WITH RECURSIVE construct also allowing transitive closures to be computed inside the query processor; as of 2011 the latter is implemented in IBM Db2, Microsoft SQL Server, Oracle, PostgreSQL, and MySQL (v8.0+). SQLite released support for this in 2014.

Datalog also implements transitive closure computations.^[4]

MariaDB implements Recursive Common Table Expressions, which can be used to compute transitive closures. This feature was introduced in release 10.2.2 of April 2016.^[5]

Algorithms[edit]

Efficient algorithms for computing the transitive closure of the adjacency relation of a graph can be found in Nuutila (1995). Reducing the problem to multiplications of adjacency matrices achieves the least^{[citation needed]} time complexity, viz. that of matrix multiplication (Munro 1971, Fischer & Meyer 1971), which is as of December 2020. However, this approach is not practical since both the constant factors and the memory consumption for sparse graphs are high (Nuutila 1995, pp. 22–23, sect.2.3.3). The problem can also be solved by the Floyd–Warshall algorithm in , or by repeated breadth-first search or depth-first search starting from each node of the graph.

For directed graphs, Purdom’s algorithm solves the problem by first computing its condensation DAG and its transitive closure, then lifting it to the original graph. Its runtime is , where is the number of edges between its strongly connected components.^[6][7][8][9]

More recent research has explored efficient ways of computing transitive closure on distributed systems based on the MapReduce paradigm.^[10]

See also[edit]

• Ancestral relation
• Deductive closure
• Reflexive closure
• Symmetric closure
• Transitive reduction (a smallest relation having the transitive closure of R as its transitive closure)

References[edit]

• Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D. Ullman, Map-Reduce Extensions and Recursive Queries, EDBT 2011, March 22–24, 2011, Uppsala, Sweden, ISBN 978-1-4503-0528-0
• Aho, A. V.; Ullman, J. D. (1979). «Universality of data retrieval languages». Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of programming languages — POPL ’79. pp. 110–119. doi:10.1145/567752.567763.
• Benedikt, M.; Senellart, P. (2011). «Databases». In Blum, Edward K.; Aho, Alfred V. (eds.). Computer Science. The Hardware, Software and Heart of It. pp. 169–229. doi:10.1007/978-1-4614-1168-0_10. ISBN 978-1-4614-1167-3.
• Heinz-Dieter Ebbinghaus; Jörg Flum (1999). Finite Model Theory (2nd ed.). Springer. pp. 123–124, 151–161, 220–235. ISBN 978-3-540-28787-2.
• M.J. Fischer and A.R. Meyer (Oct 1971). «Boolean matrix multiplication and transitive closure» (PDF). In Raymond E. Miller and John E. Hopcroft (ed.). Proc. 12th Ann. Symp. on Switching and Automata Theory (SWAT). IEEE Computer Society. pp. 129–131. doi:10.1109/SWAT.1971.4.
• Erich Grädel; Phokion G. Kolaitis; Leonid Libkin; Maarten Marx; Joel Spencer; Moshe Y. Vardi; Yde Venema; Scott Weinstein (2007). Finite Model Theory and Its Applications. Springer. pp. 151–152. ISBN 978-3-540-68804-4.
• Keller, U., 2004, Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog (unpublished manuscript)* Libkin, Leonid (2004), Elements of Finite Model Theory, Springer, ISBN 978-3-540-21202-7
• Lidl, R.; Pilz, G. (1998), Applied abstract algebra, Undergraduate Texts in Mathematics (2nd ed.), Springer, ISBN 0-387-98290-6
• Munro, Ian (Jan 1971). «Efficient determination of the transitive closure of a directed graph». Information Processing Letters. 1 (2): 56–58. doi:10.1016/0020-0190(71)90006-8.
• Nuutila, Esko (1995). Efficient transitive closure computation in large digraphs. Finnish Academy of Technology. ISBN 951-666-451-2. OCLC 912471702.
• Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Database System Concepts (6th ed.). McGraw-Hill. ISBN 978-0-07-352332-3. Appendix C (online only)

External links[edit]

• «Transitive closure and reduction», The Stony Brook Algorithm Repository, Steven Skiena.

Транзитивное замыкание орграфа G является орграфом G’ с краем (i, j) соответствующий каждому направленному пути из i к j в G. Результирующий орграф G’ представление в виде матрицы смежности называется матрицей связности.

Например, рассмотрим следующий ориентированный graph:

Значение C[i][j] является 1 только если существует направленный путь из вершины i к вершине j. Обратите внимание, что все диагональные элементы в матрице связности равны 1 так как путь существует из каждой вершины в себя.

Потренируйтесь в этой проблеме

Способ 1

Как обсуждалось в предыдущем посте, мы можем использовать Алгоритм Флойда-Уоршалла найти транзитивное замыкание Graphа с V вершины в O(V³) время. Алгоритм возвращает кратчайшие пути между каждой из вершин Graph. Мы можем легко изменить алгоритм, чтобы он возвращал 1/0 в зависимости от того, существует путь между парой вершин или нет. Реализацию можно посмотреть здесь.

Способ 2: (обычно используется)

Алгоритм Уоршалла обычно используется для построения транзитивных замыканий. Он очень идентичен Алгоритм кратчайшего пути Флойда для всех пар. Основная идея алгоритма Уоршелла состоит в том, что путь существует между двумя парами вершин. i, j тогда и только тогда, когда существует ребро из i к jили любое из следующих условий верно:

Временная сложность этого алгоритма такая же, как у алгоритма Флойда–Уоршалла, т. е. O(V³), но это уменьшает объем памяти, сохраняя только один бит для каждого матричного элемента (например, мы можем использовать тип данных bool вместо int). Реализацию можно посмотреть здесь.

Способ 3: (для плотных graphs)

Мы знаем, что все пары вершин достижимы друг из друга в каждом компонент сильной связности Graphа. Мы также знаем, что сильносвязные компоненты графа можно вычислить за линейное время. Идея состоит в том, чтобы использовать этот факт для вычисления транзитивного замыкания графа. Далее, если (x, y) — ребро между двумя вершинами в разных компонентах сильной связности, каждая вершина в y's компонент достижим из каждой вершины в x's составная часть. Таким образом, задача сводится к нахождению транзитивного замыкания на Graph компонент сильной связности, который должен иметь значительно меньше ребер и вершин, чем данный граф.

Способ 4: (для разреженных graphs)

Мы знаем, что можем найти все вершины, достижимые из вершины v позвонив Поиск в глубину (DFS) на вершине v. Если мы сделаем то же самое для всех вершин, присутствующих в Graph, и сохраним информацию о пути в матрице, мы получим транзитивное замыкание Graph. Общая временная сложность также уменьшится до O(V × (V + E)), куда V а также E — общее количество вершин и ребер в Graph соответственно. Это равно O(V³) только если graph плотный (помните E = V2 для плотного Graph). Мы также можем использовать БФС вместо ДФС.

Алгоритм может быть реализован следующим образом на C++, Java и Python:

Транзитивное замыкание используется для ответа на запросы достижимости (можем ли мы добраться до x из y?) эффективно за постоянное время после предварительной обработки построения транзитивного замыкания.

Транзитивное сокращение

Транзитивное сокращение (также известное как минимальный эквивалентный орграф) уменьшает общее количество ребер, сохраняя при этом одинаковые свойства достижимости, т. е. транзитивное замыкание орграфа. G аналогично транзитивному замыканию транзитивной редукции G. Основное применение транзитивной редукции — минимизация пространства за счет исключения избыточных ребер из G которые не влияют на доступность.

 
Использованная литература:

1. Транзитивное замыкание и редукция
2. CS 440 Теория алгоритмов — динамическое программирование, часть II

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

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

Прямым транзитивным замыканием некоторой вершины х_i – T⁺( х_i ) является объединение самой вершины х_i с прямыми отображениями 1-го порядка, второго порядка и т. д., т. е.

.

Многозначные отображения находятся до тех пор, пока в них добавляются новые вершины.

Так, для графа на
рис.
3.1.

Г⁺¹ ( х₁ ) = { х₂, х₃ },
Г⁺²( х₁ ) = { х₃, х₅ },
Г⁺³( х₁ ) = { х₃, х₁ },
Г⁺⁴( х₁ ) = { х₂, х₃ }.

Отображение четвертого порядка содержит те же элементы, что и отображение 1-го порядка, следовательно, других элементов в последующих отображениях не появится. Транзитивное замыкание для вершины х₁ получается следующим образом:

.

Проанализировав множество вершин, входящих в T⁺( х_i ), можно сделать вывод: прямое транзитивное замыкание содержит вершины, в которые есть пути из вершины х_i. Таким образом, можно дать второе определение T⁺( х_i ).

Прямое транзитивное замыкание некоторой вершины х_i T⁺( х_i ) – это множество вершин, достижимых из вершины х_i, т. е. .

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

Обратным транзитивным замыканием некоторой вершины х_i –T^—( х_i ) является объединение этой вершины с обратными отображениями 1-го, 2-го и т. д. n -го порядка, т. е.

.

Иначе, обратное транзитивное замыкание для некоторой вершины х_i – T^—( х_i ) – это множество вершин, из которых достижима вершина .

Рассмотрим построение обратного транзитивного замыкания для графа на
рис.
3.1.

.

Нахождение транзитивных замыканий
по матрице смежности

Рассмотрим метод нахождения прямого транзитивного замыкания по матрице смежности, показанной на
рис.
3.3,а для вершины х₂ графа, изображенного на
рис.
3.3,б. На 1-м шаге итерации заносим 0 в столбец Т⁺ для элемента х₂ и просматриваем 2-ю строку матрицы. Находим, что элементы a₂₂=1 и a₂₅=1. Заносим 1 в 5-ю клетку Т⁺. 2-я клетка уже занята нулем, поэтому
1 не заносим. 2-й шаг начинается просмотром 5-й строки матрицы смежности, соответствующий вершине х₅ графа. Находим, что элементы a₅₁=1 и a₅₄=1, т. е. из вершины х₅ имеются дуги в вершины х₁ и х₄ или иначе из вершины х₂ имеются пути длиной 2 в вершины х₁ и х₄. Длину пути 2 заносим в 1-ю и 4-ю клетки столбца T⁺(х₂). На 3-м шаге анализируются 1-я и 4-я строки матрицы смежности А. Находим элементы a₁₂=1, a₁₃=1, a₄₃=1. В соответствующие свободные клетки заносим значения

Это возможно сделать только для вершины х₃, так как вторая клетка уже занята. Анализ 3-й строки матрицы на 4-м шаге показывает, что из вершины х₃ нет исходящих дуг, следовательно, процесс формирования прямого транзитивного замыкания завершен.

Таким образом, в столбце T⁺(х₂) стоят числа равные длине пути от вершины х₂ к соответствующим вершинам графа. Путь от х₂ к х₃ равный 3 показан штриховой линией на
рис.
3.3,б. В столбце T⁺( х₂ ) отмечены все вершины, достижимые из вершины х₂, следовательно, они входят в T⁺( х₂ ).

T⁺( х₂ ) = { х₁, х₂, х₃, х₄, х₅ }.

Во втором столбце показано построение прямого транзитивного замыкания вершины х₁ – T⁺( х₁ ).

T⁺( х₁ ) = { х₁, х₂, х₃, х₄, х₅ }.

Нахождение обратного транзитивного замыкания по матрице смежности показано на
рис.
3.1,в. Рассмотрим нахождение обратного транзитивного замыкания вершины х₃ – T^—( х₃ ), которое начинается с занесения 0 в 3-ю клетку строки T^—( х₃ ). На 1-м шаге алгоритма, помеченного стрелкой с цифрой 1, просматриваем 3-й столбец матрицы А. Определяем элементы равные 1, т. е. a₁₃=1 и a₄₃=1. Следовательно, в графе из вершин х₁ и х₄ есть дуги в вершину х₃. Заносим 1 в 1-ю и 4-ю клетки T^—(х₃). На втором шаге просматриваем 1-й и 4-й столбцы матрицы A. Находим a₅₁=1, a₆₁=1, a₅₄=1 и проставляем 2 (так как длина пути от этих вершин до вершины х₃ равна 2) в свободные клетки T^—(х₃), т. е. в 5-ю и 6-ю клетки. 3-й шаг заключается в просмотре 5-го и 6-го столбцов матрицы A. Элементы a₂₅=1, a₆₅=1, a₆₆=1 позволяют поставить 3 во 2-ю клетку строки T^—( х₃ ). 4-й шаг просмотра 2-го столбца дает элементы a₁₂ = 1 и a₂₂ = 1, уже вошедшие в T^—(х₃). Итак, сформировано обратное транзитивное замыкание для вершины х₃.

T^—( х₃ ) = { х₁, х₂, х₃, х₄, х₅, х₆ }.

Числа, стоящие в клетках T^—( х₃ ), показывают длину кратчайшего пути от соответствующих вершин до вершины х₃.

Во второй строке показано формирование обратного транзитивного замыкания вершины х₁.

T^—( х₁ ) = { х₁, х₂, х₅, х₆ }.

Замыканием
отношения R
относительно свойства P
называется такое множество R*,
что:

1. RR*.

2. R^*обладает свойствомP.

3. R^*является подмножеством любого другогоотношения,
содержащегоRи обладающего свойствомP.

Замыкание является
весьма общим математическим понятием.
Неформально говоря, замкнутость означает,
что многократное выполнение допустимых
шагов не выводит за определенные границы.

Пример

Пусть на множестве
A={1,2,3,4} задано отношениеR={(1,2),(3,4),(4,2)}. Видно, что отношениеRнесимметрично,
нерефлексивнои нетранзитивно.
ЗамыканиемRотносительно свойства
симметричности являетсяR^*={(1,2),(3,4),(4,2);(2,1),(4,3),(2,4)}.
ЗамыканиемRотносительно рефлексивности
являетсяR^*={(1,2),(3,4),(4,2);(1,1),(2,2),(3,3),(4,4)}.
ЗамыканиемRотносительно транзитивности
является множествоR^*={(1,2),(3,4),(4,2);(3,2)}.

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

Определение
4.1. Отношение называется транзитивным замыканием
отношения,
определенного на множествеM,
тогда и только тогда, когда существуют
такие,
что.

Пример

На множестве Nопределено отношение.
Тогда транзитивное замыкание этого
отношения для значений 1<2<…<6 будет
отношение 1<6. (Рисунок 4.1)

Рисунок 4.1

Транзитивным
замыканием отношения «быть сыном»
является отношение «быть прямым
потомком».

Транзитивным
замыканием отношения «иметь общую
стену» для жильцов одного дома является
отношение « жить на одном этаже».

Пример.ПустьRзадано наM,.R
транзитивно,
если для любых a,b,с
из аRb
и
bRс
следует
аRс.
В
матрице
такого отношения должно выполняться
следующее условие: если в i-й
строке стоит единица, например
в j-й
координате (столбце) строки, т.е.
,
товсем
единицам в j-й
строке (пусть этим единицам соответствуют
k-е
координаты
такие,
что
)
должны соответствовать единицы в i—й
строке в тех
же k-х
координатах,
т.е.

(и, может
быть, еще и в других
координатах). Это условие
иллюстрируется
на рисунке
4.2,
где кружком
выделена единица

,
для которой
производится проверка условия, а
стрелками показана
последовательность проверки данного
условия.

В
матрице транзитивного отношения это
условие должно выполняться
для любых

таких,
что
.
И
наоборот, если
в матрице R
имеется
хотя бы одна единица
,
для которой
данное условие не выполняется, то R
не
транзитивно.

Рисунок
4.2

Рефлексивное замыкание отношений

Пусть
тождественное отношение Е
состоит
из упорядоченных пар самого себя –
.
Тогда R*=RE
(R*
– рефлексивное замыкание, а R
– транзитивное замыкание).

Если
R
транзитивно и рефлексивно, то R*=R.

Пример.
Используя
R
– отношение на N
такое, что
получим.

Алгоритм Уоршалла.

Вход:отношение, заданное матрицей R.

Выход:транзитивное замыкание отношения,
заданное матрицей Т.

S
:= R

for
i from 1
to n do

for
j
from 1
to n do

for
k from 1
to n do

T[j,
k] := S[j, k] V S[j, i] & S[i, k]

end
for

end
for

S
:= T

end
for

Заметим,
что нас не интересует число путей любой
конкретной длины из вершины v_iв
вершину v_j. Эта информация, получаемая
в процессе вычисления степеней A, далее
игнорируется. Для того, чтобы сократить
объем вычислений, можно отказаться от
получения указанной информации и
использовать в вычислениях просто
реализуемые булевские матричные
операции, которые мы определим согласно.

Обозначим
булевскую сумму C двух матриц A и B размера
n*n как С=АВ, а булевское
произведение –D=AB.

Элементы
матриц C и D задаются соотношениями

Заметим,
что элемент d_ijлегко получается
путем просмотра i-й строки матрицы A
слева направо и одновременно j-го столбца
матрицы B сверху вниз. Если k-й элемент
в строке матрицы A и k-й элемент в столбце
матрицы B равны 1 для какого-нибудь k, то
d_ij=1. В противном случае d_ij=0.

Булевы
матрицы более экономичны в вычислительном
отношении, чем целочисленные. Действительно,
запоминание булевой матрицы требует
меньшего объема оперативной памяти ЭВМ
по сравнению с целочисленной матрицей
той же размерности. Кроме того, выполнение
на компьютере логических операций над
булевыми матрицами требует меньшего
объема вычислений, чем над целочисленными
матрицами тех же размерностей.

Матрица
смежностей, так же как и путевая матрица,
является булевской матрицей. Заметим,
что
.

Единственная
разница между A²и A⁽²⁾заключается в том, что A⁽²⁾является
булевской матрицей и элемент на
пересечении i-й строки и j-го столбца
A⁽²⁾равен 1 в том случае, когда
существует по крайней мере один путь
длины 2 из v_iв v_j. Аналогичное
положение имеет место для A³и A⁽³⁾и в общем случае для A^rи A^(r)при любом целом положительном r. Из этих
рассуждений ясно, что матрица достижимости
P задается выражением

Например,
если

то

Данный метод
получения матрицы достижимости
ориентированного графа называется
алгоритмом Уоршалла (Warshall S.A. A Theorem on
Boolean Matrices. — J.ACM, 1962, 9, pp.11-12).

Тема
5.
Функции и отображения. Инъекция,
сюръекция, биекция. Представление
функций в ЭВМ. Операции. Свойства бинарных
операций: ассоциативность, коммутативность,
дистрибутивность слева и справа. Способы
задания операций. Таблица Кэли.

Функции и отображения. Инъекция,
сюръекция, биекция.

Понятие
“функции” является одним из
основополагающих в математике, в данном
случае подразумевается прежде всего
функции, отображающие одно конечное
множество объектов в другое конечное
множество, мы избегаем использование
термина “отображение” и предпочитаем
слово “функция” в расчете на постоянное
сопоставление читателем математического
понятия функции с понятием функции в
языках программирования .

Определения
5.1.Говорят, что между множествамиАиВопределено соответствиеГ, если задано некоторое произвольное
подмножество декартового произведения
.

Определения
5.2.Отображением
множества А
на множество В
называется такое соответствие, которое
каждому элементу
сопоставляется по крайней мере один
элемент.
Тогда элементb
называется образом элемента а,
a
a
– прообразом элемента b,
или переменной, или аргументом.

Определения
5.3. Соответствие, при котором
каждомуаАсопоставляется один и только один
элементbB,
,называется функциональным соответствием,
илифункцией изАвВ, и
обозначается следующим образом
или
.

Если
b=f(a)
, тоаназываютаргументом, аb–значением функции.

Замечание.

Вообще
всякому отношению RизAв В
можно сопоставить (тотальную) функцию
(эта функция называетсяхарактеристической
функцией отношения), полагая

Пусть
,
тогда

Область
определения функции:.

Область
значения функции:.

Определения
5.4. Если,то
функция называетсятотальной, а
если,
то –частичной.

Определения
5.5. Суждением функциина множественазывается функция,
определяемая следующим образом:.

Для
тотальной функции
.

Определения
5.6. Функцияназывается функциейnаргументов, илиn-местнойфункцией.

Инъекция,
сюръекция и биекция.

Пусть
.
Тогда функция является:

Инъективной,
или инъекцией, если.

Сюръективной,
или сюръекцией, если.

Биективной,
или биекцией, если она инъективная и
сюръективная.

Замечание.

Биективную
функцию также называют взаимно
однозначной.

Рис.5.1.
иллюстрирует понятия отношения, функции,
инъекции, сюръекции и биекции.

Рисунок 5.1.

Теорема.

Если
– тотальная биекция (),
то отношение(обратная функция) является биекцией.

Доказательство.

Поскольку
– биекция, имеем

.

Покажем,
что
– функция.

Поскольку
.

Тогда
.

Покажем,
что
– инъекция. Пусть.

Тогда
.
Покажем от противного, что– сюръекция.

Пусть
.
Тогда.
Обозначим этот элемент.
Имеем:.

Индуцированная
функция.

Пусть
и пусть.
Тогда множество

называется образом
множества,
а множество–прообразоммножества.
Заметим, чтоFявляется отношением из множествав множество.

Теорема.

Если

–функция, то и– тоже функции

Замечание.

называется
индуцированной функцией, а
-переходам
к прообразам.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #