Domknięcie przechodnie

Ten artykuł dotyczy operacji na relacji dwuargumentowej. Zobacz też: domknięcie przechodnie zbioru.

Domknięcie przechodnie relacji dwuargumentowej ${\displaystyle R}$ na zbiorze ${\displaystyle X}$ jest to najmniejsza (w sensie inkluzji) relacja przechodnia ${\displaystyle R^{+}}$ na zbiorze ${\displaystyle X,}$ która zawiera ${\displaystyle 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 ${\displaystyle X}$ istnieje co najmniej jedna relacja przechodnia ją zawierająca – mianowicie ${\displaystyle X\times X.}$ Wobec tego domknięcie przechodnie relacji można określić jako iloczyn wszystkich relacji przechodnich na ${\displaystyle X}$ ją zawierających.

Alternatywna definicja

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

${\displaystyle 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 ${\displaystyle x,y}$ są w relacji ${\displaystyle R^{+}}$ będącej domknięciem przechodnim ${\displaystyle R,}$ o ile istnieje taki skończony ciąg elementów zbioru ${\displaystyle X,}$ że ${\displaystyle x}$ jest w relacji ${\displaystyle R}$ z pierwszym elementem tego ciągu, pierwszy element ciągu jest w relacji ${\displaystyle R}$ z drugim, drugi z trzecim itd., zaś ostatni element ciągu jest w relacji ${\displaystyle R}$ z ${\displaystyle y.}$

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

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

Stąd bierze się alternatywne oznaczenie relacji ${\displaystyle R^{+},}$ mianowicie ${\displaystyle R^{\infty }}$^[1].

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 ${\displaystyle G=(V,A)}$ będzie grafem skierowanym. Graf skierowany ${\displaystyle G^{+}=(V,A^{+})}$ nazywany jest domknięciem przechodnim grafu ${\displaystyle G,}$ gdy ${\displaystyle A^{+}}$ jest zbiorem wszystkich takich par ${\displaystyle (a,b)}$ wierzchołków ze zbioru ${\displaystyle V,}$ że w grafie ${\displaystyle G}$ istnieje droga z ${\displaystyle a}$ do ${\displaystyle b.}$

Przykłady

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

Algorytmy

Istnieją wydajne algorytmy odnajdywania domknięcia przechodniego^[2]. Jednym z algorytmów pozwalających na wyznaczenie domknięcia przechodniego jest algorytm Floyda-Warshalla.

Zobacz też

• domknięcie przechodnie zbioru

Przypisy