Domknięcie przechodnie

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Ujednoznacznienie Ten artykuł dotyczy operacji na relacji dwuargumentowej. Zobacz też: domknięcie przechodnie zbioru.

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 × X. Wobec tego domknięcie przechodnie relacji można określić jako iloczyn wszystkich relacji przechodnich na X ją zawierających.

Alternatywna definicja[edytuj | edytuj kod]

Można też zdefiniować domknięcie przechodnie inaczej. Mianowicie, dla dowolnych elementów x, yX 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ż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[1].

Domknięcie przechodnie grafu[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

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

Przypisy

  1. J. M. Howie, An Introduction to Semigroup Theory, Academic Press, 1976, str. 19.
  2. E. Nuutila, Efficient Transitive Closure Computation in Large Digraphs. Acta Polytechnica Scandinavica, Mathematics and Computing in Engineering Series No. 74, Helsinki 1995, 124 ss.

Zobacz też[edytuj | edytuj kod]