gráf tranzitív lezártja

Magyar

Kiejtés

• IPA: [ ˈɡraːf ˈtrɒnzitiːv ˈlɛzaːrcɒ]

Főnév

gráf tranzitív lezártja

1. (matematika, gráfelmélet) Legyen ρ egy reláció az A halmazon, G = (A, ρ) a ρ reláció gráfja, ${\hat {\rho }}$ a ρ tranzitív lezártja. Ekkor
   • $(a,b)\in {\hat {\rho }}$ akkor és csak akkor, ha a G gráfban létezik séta a-ból b-be.
   • ${\hat {\rho }}$ tranzitív reláció A-n.
   • ${\hat {\rho }}$ a legszűkebb tranzitív reláció A-n, amely tartalmazza ρ-t. Azaz ha τ egy tranzitív reláció A-n, amelyre $\rho \subseteq \tau$, akkor ${\hat {\rho }}\subseteq \tau .$

   Ebből következik, hogy minden reláció kiterjeszthető tranzitív relációvá.

• angol: transitive closure of a graph (en)