Relación de Alcance

La relación de alcance está conectada a una relación dada y muestra si un elemento es alcanzable desde otro a través de conexiones directas o indirectas en secuencia. Este concepto está estrechamente relacionado con el cierre transitivo.

Definición Formal

Sea R una relación en un conjunto A. La relación de alcance R* se define de modo que (a,b) ∈ R* si y solo si existe una cadena finita a = x₀, x₁, …, xₙ = b de elementos donde cada (x_i, x_{i+1}) ∈ R.

Esto incluye la cadena vacía para reflexividad: cada elemento se alcanza a sí mismo (n=0, R^0 = identidad).

Interpretación Gráfica

En términos de grafos, si representamos la relación R como un grafo dirigido (vértices = elementos de A, aristas = pares en R), entonces la relación de alcance R* consiste en todos los pares (a,b) donde hay un camino dirigido de a a b en el grafo.

Ejemplo: Sea A = {a,b,c}, R = {(a,b), (b,c)}. Entonces R* = {(a,a), (b,b), (c,c), (a,b), (b,c), (a,c)}, porque a alcanza b directamente, b alcanza c directamente, y a alcanza c vía b.

Propiedades

• La relación de alcance es siempre reflexiva.
• La relación de alcance es siempre transitiva.
• Si la relación original es simétrica, la relación de alcance también será simétrica.
• La relación de alcance corresponde al cierre reflexivo transitivo de la relación.

Resumen

La relación de alcance muestra si un elemento es alcanzable desde otro a través de cadenas de conexiones directas o indirectas. Este concepto es fundamental en la teoría de grafos, algoritmos y análisis de redes.

Ejercicio de Práctica