Domknięcie przechodnie

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

Domknięcie przechodnie relacji dwuargumentowej na zbiorze jest to najmniejsza (w sensie inkluzji) relacja przechodnia na zbiorze która zawiera

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 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 ją zawierających.

Alternatywna definicja[edytuj | edytuj kod]

Można też zdefiniować domknięcie przechodnie inaczej. Mianowicie, dla dowolnych elementów zachodzi:

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

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

Stąd bierze się alternatywne oznaczenie relacji mianowicie [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 będzie grafem skierowanym. Graf skierowany nazywany jest domknięciem przechodnim grafu gdy jest zbiorem wszystkich takich par wierzchołków ze zbioru że w grafie istnieje droga z do

Przykłady[edytuj | edytuj kod]

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

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.

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

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