Domknięcie przechodnie

Domknięcie przechodnie relacji dwuargumentowej $R$ na zbiorze $X$ jest to najmniejsza (w sensie inkluzji) relacja przechodnia $R^+$ na zbiorze $X$ taka, że $R\subseteq R^+$.

Dla każdej relacji istnieje jej domknięcie przechodnie. Dla dowodu wystarczy zauważyć, że iloczyn dowolnej rodziny relacji przechodnich jest relacją przechodnią. Ponadto, dla każdej relacji na zbiorze $X$ istnieje co najmniej jedna relacja przechodnia ją zawierająca - mianowicie $X\times X$. Wobec tego domknięcie przechodnie relacji można określić jako iloczyn wszystkich relacji przechodnich na $X$ ją zawierających.

Alternatywna definicja

Można też zdefiniować domknięcie przechodnie inaczej. Mianowicie, dla dowolnych elementów $x,y\in X$ zachodzi:

$xR^+y\iff \exists_{n\in \mathbb{N}} \exists_{x_1,x_2,\dots ,x_n\in X}( xRx_1Rx_2R\dots Rx_{n-1}Rx_nRy)$

, to znaczy elementy $x,y$ są w relacji $R^+$ będącej domknięciem przechodnim $R$, o ile istnieje taki skończony ciąg elementów zbioru $X$, że $x$ jest w relacji $R$ z pierwszym elementem tego ciągu, pierwszy element ciągu jest w relacji $R$ z drugim, drugi z trzecim itd., zaś ostatni element ciągu jest w relacji $R$ z $y$.

Formalnie, wykorzystując działanie składania relacji, możemy również napisać:

$R^+=R^1\cup R^2\cup R^3\cup \dots=\bigcup_{n=1}^{\infty}R^n$.

Stąd bierze się alternatywne oznaczenie relacji $R^+,$ mianowicie $R^\infty.$

Domknięcie przechodnie grafu

W teorii grafów można rozpatrywać pojęcie domknięcia przechodniego grafu. Definiuje się je analogicznie do domknięcia przechodniego relacji, ponieważ każdą relację dwuargumentową można przedstawić w postaci grafu skierowanego.

Niech $G=(V,A)$ będzie grafem skierowanym. Graf skierowany $G^+=(V,A^+)$ nazywamy domknięciem przechodnim grafu $G$, gdy $A^+$ jest zbiorem wszystkich takich par $(a,b)$ wierzchołków ze zbioru $V$, że w grafie $G$ istnieje droga z $a$ do $b$.

Przykłady

• Niech X oznacza zbiór wszystkich członków pewnej populacji. Jeśli przez R rozumiemy relację bycia rodzicem, to domknięciem przechodnim R jest relacja bycia przodkiem.
• Niech X oznacza pewien zbiór lotnisk. Określmy relację R na X następująco: aRb dla lotnisk a, b ze zbioru X, o ile istnieje bezpośrednie połączenie z a do b. Przechodnim domknięciem tej relacji jest relacja S określona następująco: aSb, o ile można dolecieć z a do b bezpośrednio, lub z pewną ilością przesiadek.
• Niech X={1,2,3,4}, R={(1,2),(2,4),(4,3)}. Wtedy domknięciem przechodnim R jest relacja: {(1,2),(1,4),(1,3),(2,4),(2,3),(4,3)}.

Algorytmy

Istnieją wydajne algorytmy odnajdywania domknięcia przechodniego; więcej można przeczytać o nich tutaj. Jednym z algorytmów pozwalających na wyznaczenie domknięcia przechodniego jest algorytm Floyda-Warshalla.

Zobacz też

• domknięcie przechodnie zbioru