Domknięcie przechodnie
Z Wikipedii
Domknięcie przechodnie relacji dwuargumentowej R na zbiorze X jest to najmniejsza (w sensie inkluzji) relacja przechodnia R + na zbiorze X taka, że 
.
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 
. Wobec tego domknięcie przechodnie relacji można określić jako iloczyn wszystkich relacji przechodnich na X ją zawierających.
Spis treści |
[edytuj] Alternatywna definicja
Można też zdefiniować domknięcie przechodnie inaczej. Mianowicie, dla dowolnych elementów 
zachodzi:
, 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ć:
.
[edytuj] 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.
[edytuj] 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)}.
[edytuj] Algorytmy
Istnieją wydajne algorytmy odnajdywania domknięcia przechodniego; więcej można przeczytać o nich tutaj. Jednym z prostszych algorytmów pozwalających na wyznaczenie domknięcia przechodniego jest algorytm Floyda-Warshalla.
