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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение транзитивного замыкания)
Строка 14: Строка 14:
  
 
== Построение транзитивного замыкания ==
 
== Построение транзитивного замыкания ==
Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения <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>x2_Rx_3</math>, ..., <math>x_{n-1}Rx_n</math>, <math>x_nRb</math>, то есть существует путь из вершины <math>a</math> в вершину <math>b</math> на графе отношения.
+
Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения <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> по рёбрам графа отношения.

Версия 22:11, 28 сентября 2010

Эта статья находится в разработке!

Транзитивным замыканием [math]\mathrm{TrCl}(R)[/math] отношения [math]R[/math] на множестве [math]X[/math] называется пересечение всех транзитивных отношений, содержащих [math]R[/math] как подмножество (иначе, минимальное транзитивное отношение, содержащее [math]R[/math] в качестве подмножества). Например, если [math]V[/math] - множество городов, и на них задано отношение [math]R[/math], означающее, что если x R y, то "существует автобусный маршрут из x в y", то транзитивным замыканием этого отношения будет отношение "существует возможность добраться из x в y, передвигаясь на автобусах".

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

Транзитивное замыкание существует для любого отношения. Для этого отметим, что пересечение любого множества транзитивных отношений транзитивно. Более того, обязательно существует транзитивное отношение, содержащее [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]R \subset R^+[/math] по определению [math]R^+[/math]
  • [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]
  • [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], что и требовалось доказать

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

Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения [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] по рёбрам графа отношения.