Domknięcie przechodnie grafu W teorii grafów można rozpatrywać pojęcie domknięcia przechodniego grafu [dostęp 2026-02-04].. 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 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ą liczbą przesiadek. Niech Wtedy domknięciem przechodnim jest relacja:
Algorytmy Istnieją wydajne algorytmy odnajdywania domknięcia