Accesibilidad
En la teoría de grafos , la accesibilidad se refiere a la capacidad de ir de un vértice a otro dentro de un gráfico. Un vértice puede llegar a otro vértice (y es accesible desde ) si existe una secuencia de vértices adyacentes (es decir, una caminata ) que comienza y termina en .
En un gráfico no dirigido, la accesibilidad entre todos los pares de vértices se puede determinar identificando los componentes conectados del gráfico. Cualquier par de vértices en tal gráfico pueden alcanzarse si y solo si pertenecen a la misma componente conexa; por lo tanto, en dicho gráfico, la alcanzabilidad es simétrica ( alcanza si y solo alcanza ). Los componentes conectados de un gráfico no dirigido se pueden identificar en tiempo lineal. El resto de este artículo se enfoca en el problema más difícil de determinar la accesibilidad por pares en un gráfico dirigido (que, dicho sea de paso, no necesita ser simétrico).
Para un grafo dirigido , con conjunto de vértices y conjunto de aristas , la relación de alcanzabilidad de es la clausura transitiva de , es decir, el conjunto de todos los pares ordenados de vértices en los que existe una secuencia de vértices tal que la arista está en todos _ [1]
