Domknięcie przechodnie

Domknięcie przechodnie relacji dwuargumentowej $R$ na zbiorze $X$ jest to najmniejsza (w sensie inkluzji) relacja przechodnia $R^{+}$ na zbiorze $X,$ która zawiera $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_{1}Rx_{2}R\dots Rx_{n-1}Rx_{n}Ry),$

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żna 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^{+})$ nazywany jest 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ą liczbą 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. Jednym z algorytmów pozwalających na wyznaczenie domknięcia przechodniego jest algorytm Floyda-Warshalla.

Zobacz też

• domknięcie przechodnie zbioru