Транзитивное замыкание — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 23 промежуточные версии 9 участников)
Строка 1: Строка 1:
−
{{В разработке}}
+
{{Определение
−
 
+
|definition=
−
'''Транзитивным замыканием''' <math>\mathrm{TrCl}(R)</math> отношения <math>R</math> на множестве <math>X</math> называется пересечение всех транзитивных отношений, содержащих <math>R</math> как подмножество (иначе, минимальное транзитивное отношение, содержащее <math>R</math> как подмножество). Например, если <math>V</math> - множество городов, и на них задано отношение <math>R</math>, означающее, что если <math>x R y</math>, то "существует автобусный маршрут из x в y", то транзитивным замыканием этого отношения будет отношение "существует возможность добраться из x в y, передвигаясь на автобусах".
+
'''Транзитивным замыканием''' (англ. ''transitive closure'') <tex>\mathrm{TrCl}(R)</tex> отношения <tex>R</tex> на множестве <tex>X</tex> называется пересечение всех транзитивных отношений, содержащих <tex>R</tex> как подмножество (иначе, минимальное [[транзитивное отношение]], содержащее <tex>R</tex> как подмножество).}}
 +
Например, если <tex>V</tex> {{---}} множество городов, и на них задано отношение <tex>R</tex>, означающее, что если <tex>x R y</tex>, то "существует автобусный маршрут из <tex> x</tex> в <tex> y</tex>", то транзитивным замыканием этого отношения будет отношение "существует возможность добраться из <tex> x</tex> в <tex> y</tex>, передвигаясь на автобусах".
  
 
== Существование и описание ==
 
== Существование и описание ==
−
Транзитивное замыкание существует для любого отношения. Для этого отметим, что пересечение любого множества транзитивных отношений транзитивно. Более того, обязательно существует транзитивное отношение, содержащее <math>R</math> как подмножество (например, <math>X \times X</math>).
+
Транзитивное замыкание существует для любого отношения. Для этого отметим, что пересечение любого множества транзитивных отношений транзитивно. Более того, обязательно существует транзитивное отношение, содержащее <tex>R</tex> как подмножество (например, <tex>X \times X</tex>).
  
−
Докажем, что <math>R^+</math> является транзитивным замыканием отношения <math>R</math>.
+
{{Теорема
−
:<math>R^+ = \bigcup\limits_{i \in \mathbb{N}} R^i</math>
+
|statement=
 +
Докажем, что <tex>R^+</tex> является транзитивным замыканием отношения <tex>R</tex>.
 +
:<tex>R^+ = \bigcup\limits_{i \in \mathbb{N}} R^i</tex>
  
−
* <math>R \subset R^+</math> по определению <math>R^+</math>
+
|proof=
−
* <math>R^+</math> транзитивно. Пусть <math>a R^+ b</math> и <math>b R^+ c</math>. Это значит, что существуют i, j такие, что <math>a R^i b</math> и <math>b R^j c</math>. Но тогда <math>a R^{i+j} b</math>, и, так как <math>R^{i+j} \subset R^+ \rightarrow a R^+ b</math>
+
* <tex>R \subset R^+</tex> по определению <tex>R^+</tex>
−
* <math>R^+</math> - минимальное отношение, удовлетворяющее представленным требованиям. Пусть <math>T</math> - транзитивное отношение, содержащее <math>R</math> в качестве подмножества. Покажем, что <math>R^+ \subset T</math>. <math>R \subset T \longleftrightarrow R^i \subset T</math> для любого натурального <math>i</math>. Докажем это по индукции. <math>R^1 = R \subset R^+</math>, как было показано выше. Пусть верно для любого <math>i \le k</math>. Пусть <math>a R^{k+1} c</math>. Но тогда существует <math>b: aR^kb</math> и <math>bRc</math>, но <math>R \subset T, R^k \subset T</math>, следовательно <math>aTb, bTc</math>. Из транзитивности <math>T</math> следует, что <math>aTc</math>, следовательно <math>R^{k+1} \subset T</math>, что и требовалось доказать
+
* <tex>R^+</tex> транзитивно. Пусть <tex>a R^+ b</tex> и <tex>b R^+ c</tex>. Это значит, что существуют <tex> i, j </tex> такие, что <tex>a R^i b</tex> и <tex>b R^j c</tex>. Но тогда <tex>a R^{i+j} c</tex>, и, так как <tex>R^{i+j} \subset R^+</tex>, то <tex>a R^+ c</tex>
 +
* <tex>R^+</tex> {{---}} минимальное отношение, удовлетворяющее представленным требованиям. Пусть <tex>T</tex> {{---}} транзитивное отношение, содержащее <tex>R</tex> в качестве подмножества. Покажем, что <tex>R^+ \subset T</tex>. <tex>R \subset T \Leftrightarrow R^i \subset T</tex> для любого натурального <tex>i</tex>. Докажем это по индукции. <tex>R^1 = R \subset R^+</tex>, как было показано выше. Пусть верно для любого <tex>i \leqslant k</tex>. Пусть <tex>a R^{k+1} c</tex>. Но тогда существует <tex>b: aR^kb</tex> и <tex>bRc</tex>, но <tex>R \subset T, R^k \subset T</tex>, следовательно <tex>aTb, bTc</tex>. Из транзитивности <tex>T</tex> следует, что <tex>aTc</tex>, следовательно <tex>R^{k+1} \subset T</tex>.
 +
}}
  
 
== Построение транзитивного замыкания ==
 
== Построение транзитивного замыкания ==
−
Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения <math>R</math> как отношение <math>T</math> такое, что <math>aTb</math> тогда и только тогда, когда существуют <math>x_1, x_2, ..., x_n</math> такие, что <math>aRx_1</math>, <math>x_1Rx_2</math>, <math>x_2Rx_3</math>, ..., <math>x_{n-1}Rx_n</math>, <math>x_nRb</math>, то есть существует путь из вершины <math>a</math> в вершину <math>b</math> по рёбрам графа отношения.
+
Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения <tex>R</tex> как отношение <tex>T</tex> такое, что <tex>aTb</tex> тогда и только тогда, когда существуют <tex>x_1, x_2, \ldots, x_n</tex> такие, что <tex>aRx_1, x_1Rx_2, x_2Rx_3, \ldots, x_{n-1}Rx_n, x_nRb</tex>, то есть существует путь из вершины <tex>a</tex> в вершину <tex>b</tex> по рёбрам графа отношения.
  
−
Из этого определения можно легко понять, если <math>R</math> - отношение на конечном множестве размера n, то транзитивным замыканием такого отношения будет отношение
+
{{Теорема
−
:<math>T = \bigcup\limits_{i = 1}^{n} R^i</math>.
+
|statement=
 +
Если <tex>R</tex> {{---}} отношение на конечном множестве размера n, то транзитивным замыканием такого отношения будет отношение
 +
:<tex>T = \bigcup\limits_{i = 1}^{n} R^i</tex>.
  
−
Действительно, если по рёбрам графа есть путь длины <math>l > n</math>, то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути. Длину пути можно уменьшать до того, как она не будет превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем <math>n</math> можно "выкинуть" из объединения.
+
|proof=
 +
Действительно, если по рёбрам графа есть путь длины <tex>l > n</tex>, то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути. Длину пути можно уменьшать до того, пока она не будет не превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем <tex>n</tex> можно "выкинуть" из объединения.
 +
}}
  
−
Для построения транзитивного отношения множества, заданного матрицей смежности, используется алгоритм Флойда-Уоршала.
+
Для построения транзитивного замыкания отношения, заданного матрицей смежности, используется [[алгоритм Флойда — Уоршелла]].
  
 
== Свойства транзитивного замыкания ==
 
== Свойства транзитивного замыкания ==
 
* Транзитивное замыкание рефлексивного отношения рефлексивно, так как транзитивное отношение содержит исходное отношение
 
* Транзитивное замыкание рефлексивного отношения рефлексивно, так как транзитивное отношение содержит исходное отношение
−
* Транзитивное замыкание симметричного отношения симметрично. Действительно, пусть <math>aTb</math>, значит существуют <math>x_1, x_2, ..., x_n</math> такие, что <math>aRx_1, x_1Rx_2, ..., x_nRb</math>. Но из симметричности отношения <math>R</math> следует <math>bRx_n, x_nRx_{n-1}, ..., x_1Ra</math>, а, следовательно, <math>bTa</math>
+
* Транзитивное замыкание симметричного отношения симметрично. Действительно, пусть <tex>aTb</tex>, значит существуют <tex>x_1, x_2, \ldots, x_n</tex> такие, что <tex>aRx_1, x_1Rx_2, \ldots, x_nRb</tex>. Но из симметричности отношения <tex>R</tex> следует <tex>bRx_n, x_nRx_{n-1}, \ldots, x_1Ra</tex>, а, следовательно, <tex>bTa</tex>
−
* Транзитивное замыкание не сохраняет антисимметричность, например, для отношения <math>\{(a, b), (b, c), (c, a)\}</math> на множестве <math>\{a, b, c\}</math>
+
* Транзитивное замыкание не сохраняет антисимметричность, например, для отношения <tex>\{(a, b), (b, c), (c, a)\}</tex> на множестве <tex>\{a, b, c\}</tex>
−
* Транзитивное замыкание транзитивного отношения - оно само
+
* Транзитивное замыкание транзитивного отношения {{---}} оно само
  
 
== Рефлексивно-транзитивное замыкание ==
 
== Рефлексивно-транзитивное замыкание ==
−
Отношение <math>R^* = R^+ \cup R^0</math>, где
+
Отношение <tex>R^* = R^+ \cup R^0</tex>, где
−
:<math>R^0 = \{(e, e) | e \in X\}</math>
+
:<tex>R^0 = \{(e, e) | e \in X\}</tex>
−
иногда называют рефлексивно-транзитивным замыканием, хотя часто под "транзитивным замыканием" подразумевается именно <math>R^*</math>. Обычно различия между этими отношениями не являются значительными.
+
иногда называют рефлексивно-транзитивным замыканием, хотя часто под "транзитивным замыканием" подразумевается именно <tex>R^*</tex>. Обычно различия между этими отношениями не являются значительными.
 +
 
 +
== См. также ==
 +
* [[Транзитивное_отношение|Транзитивное отношение]]
 +
* [[Алгоритм_Флойда_—_Уоршалла|Алгоритм Флойда-Уоршалла (построение транзитивного замыкания отношения)]]
 +
* [[Транзитивный_остов|Транзитивный остов]]
 +
 
 +
== Источники информации ==
 +
*[http://en.wikipedia.org/wiki/Transitive_closure Wikipedia | Transitive closure (англ.)]
 +
 
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория: Отношения ]]

Текущая версия на 19:25, 4 сентября 2022

Определение:
Транзитивным замыканием (англ. transitive closure) [math]\mathrm{TrCl}(R)[/math] отношения [math]R[/math] на множестве [math]X[/math] называется пересечение всех транзитивных отношений, содержащих [math]R[/math] как подмножество (иначе, минимальное транзитивное отношение, содержащее [math]R[/math] как подмножество).

Например, если [math]V[/math] — множество городов, и на них задано отношение [math]R[/math], означающее, что если [math]x R y[/math], то "существует автобусный маршрут из [math] x[/math] в [math] y[/math]", то транзитивным замыканием этого отношения будет отношение "существует возможность добраться из [math] x[/math] в [math] y[/math], передвигаясь на автобусах".

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

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

Теорема:
Докажем, что [math]R^+[/math] является транзитивным замыканием отношения [math]R[/math].
[math]R^+ = \bigcup\limits_{i \in \mathbb{N}} R^i[/math]
Доказательство:
[math]\triangleright[/math]
  • [math]R \subset R^+[/math] по определению [math]R^+[/math]
  • [math]R^+[/math] транзитивно. Пусть [math]a R^+ b[/math] и [math]b R^+ c[/math]. Это значит, что существуют [math] i, j [/math] такие, что [math]a R^i b[/math] и [math]b R^j c[/math]. Но тогда [math]a R^{i+j} c[/math], и, так как [math]R^{i+j} \subset R^+[/math], то [math]a R^+ c[/math]
  • [math]R^+[/math] — минимальное отношение, удовлетворяющее представленным требованиям. Пусть [math]T[/math] — транзитивное отношение, содержащее [math]R[/math] в качестве подмножества. Покажем, что [math]R^+ \subset T[/math]. [math]R \subset T \Leftrightarrow R^i \subset T[/math] для любого натурального [math]i[/math]. Докажем это по индукции. [math]R^1 = R \subset R^+[/math], как было показано выше. Пусть верно для любого [math]i \leqslant k[/math]. Пусть [math]a R^{k+1} c[/math]. Но тогда существует [math]b: aR^kb[/math] и [math]bRc[/math], но [math]R \subset T, R^k \subset T[/math], следовательно [math]aTb, bTc[/math]. Из транзитивности [math]T[/math] следует, что [math]aTc[/math], следовательно [math]R^{k+1} \subset T[/math].
[math]\triangleleft[/math]

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

Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения [math]R[/math] как отношение [math]T[/math] такое, что [math]aTb[/math] тогда и только тогда, когда существуют [math]x_1, x_2, \ldots, x_n[/math] такие, что [math]aRx_1, x_1Rx_2, x_2Rx_3, \ldots, x_{n-1}Rx_n, x_nRb[/math], то есть существует путь из вершины [math]a[/math] в вершину [math]b[/math] по рёбрам графа отношения.

Теорема:
Если [math]R[/math] — отношение на конечном множестве размера n, то транзитивным замыканием такого отношения будет отношение
[math]T = \bigcup\limits_{i = 1}^{n} R^i[/math].
Доказательство:
[math]\triangleright[/math]
Действительно, если по рёбрам графа есть путь длины [math]l \gt n[/math], то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути. Длину пути можно уменьшать до того, пока она не будет не превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем [math]n[/math] можно "выкинуть" из объединения.
[math]\triangleleft[/math]

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

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

  • Транзитивное замыкание рефлексивного отношения рефлексивно, так как транзитивное отношение содержит исходное отношение
  • Транзитивное замыкание симметричного отношения симметрично. Действительно, пусть [math]aTb[/math], значит существуют [math]x_1, x_2, \ldots, x_n[/math] такие, что [math]aRx_1, x_1Rx_2, \ldots, x_nRb[/math]. Но из симметричности отношения [math]R[/math] следует [math]bRx_n, x_nRx_{n-1}, \ldots, x_1Ra[/math], а, следовательно, [math]bTa[/math]
  • Транзитивное замыкание не сохраняет антисимметричность, например, для отношения [math]\{(a, b), (b, c), (c, a)\}[/math] на множестве [math]\{a, b, c\}[/math]
  • Транзитивное замыкание транзитивного отношения — оно само

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

Отношение [math]R^* = R^+ \cup R^0[/math], где

[math]R^0 = \{(e, e) | e \in X\}[/math]

иногда называют рефлексивно-транзитивным замыканием, хотя часто под "транзитивным замыканием" подразумевается именно [math]R^*[/math]. Обычно различия между этими отношениями не являются значительными.

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Транзитивное_замыкание&oldid=85115»