Elérhetőségi reláció

Az elérhetőségi reláció egy adott relációhoz kapcsolódik, és azt mutatja meg, hogy egy elem elérhető-e egy másikból közvetlen vagy közvetett kapcsolatok sorozatán keresztül. Ez a fogalom szorosan összefügg a tranzitív lezárással.

Formális definíció

Legyen R egy reláció egy A halmazon. Az elérhetőségi reláció R* úgy van definiálva, hogy (a,b) ∈ R* akkor és csak akkor, ha létezik olyan véges láncolat a = x₀, x₁, …, xn = b elemekből, amelyben minden (xi, xi+1) ∈ R.

Ez magában foglalja az üres láncot a reflexivitás miatt: minden elem eléri önmagát (n=0, R^0 = identitás).

Gráfos értelmezés

Gráfos értelemben, ha az R relációt irányított gráfként ábrázoljuk (csúcsok = A elemei, élek = R párok), akkor az R* elérhetőségi reláció minden olyan (a,b) párt tartalmaz, ahol van irányított út a-tól b-ig a gráfban.

Példa: Legyen A = {a,b,c}, R = {(a,b), (b,c)}. Akkor R* = {(a,a), (b,b), (c,c), (a,b), (b,c), (a,c)}, mert a közvetlenül eléri b-t, b közvetlenül c-t, és a eléri c-t b-n keresztül.

Tulajdonságok

• Az elérhetőségi reláció mindig reflexív.
• Az elérhetőségi reláció mindig tranzitív.
• Ha az eredeti reláció szimmetrikus, az elérhetőségi reláció is szimmetrikus lesz.
• Az elérhetőségi reláció megfelel a reláció reflexív tranzitív lezárásának.

Összefoglalás

Az elérhetőségi reláció megmutatja, hogy egy elem közvetett vagy közvetlen kapcsolatok láncolatán keresztül elérhető-e egy másikból. Ez a fogalom alapvető a gráfelméletben, az algoritmusokban és a hálózatok vizsgálatában.

Gyakorló feladat