Atinxibilidade (teoría de grafos)

Na teoría de grafos, a **atinxilidade** ou **accesibilidade** ou  **alcanzabilidade** refírese á capacidade de pasar dun vértice a outro nun grafo. Dicimos que un vértice s pode chegar a outro vértice t (ou que t é atinxíbel desde s) se hai unha secuencia de vértices adxacentes (por exemplo, un camiño) que comezan por s e terminan con t.

Nun grafo non orientado, abonda con identificar só as compoñentes conexas, xa que calquera par de vértices deste gráfo pódese alcanzar se e só se pertencen á mesma compoñente conexa. As compoñentes conexas dun grafo pódense identificar en tempo linear. Lembrámos que este artigo céntrase na atinxibilidade na configuración de grafos orientados.

## Definición 
Para un grafo orientado G = (V, E), onde V é o conxunto de vértices e E o conxunto de arestas, a relación de atinxibilidade de G é o peche transitivo de E, é dicir, o conxunto de pares ordenados (s,t) con vértices en V para os que existe unha secuencia de vértices v_0 = s, v_1, v_2, ..., v_k = t do mesmo xeito que a aresta (v_{i-1},v_i) está en E para todo 1 \leq i \leq k.

## Algoritmos 
Os algoritmos para determinar a atinxibilidade divídense en dúas clases: os que requiren preprocesamento e os que non.

### Algoritmo de Floyd-Warshall 
O algoritmo de Floyd-Warshall  pódese usar para calcular o peche transitivo de calquera grafo orientado.

Este algoritmo non está unicamente interesadona atinxibilidade senón que tamén computa o camiño mais curto entre tódolos pares de vértices.

### Algoritmo de Thorup 
miniatura|208x208px| Un *digrafo* axeitado para os métodos de Kameda con s e t engadidos.
Para un grafo plano, un método moito máis rápido está dispoñíbel, como o descrito por Mikkel Thorup en 2004.

O enfoque global consiste en asociar a cada vértice un conxunto relativamente pequeno de chamados "camiños separadores" de tal xeito que calquera camiño que deixe un vértice  a calquera outro vértice  debe ir polo menos a un dos separadores asociados con   ou .

### Algoritmo de Kameda 
miniatura|210x210px| O mesmo grafo que se mostra arriba despois de aplicar o algoritmo de Kameda, que mostra a etiqueta DFS para cada vértice.

Un método aínda máis rápido para o preprocesamento, debido a T. Kameda en 1975
pode usarse se o grafo é plano, acíclico e tamén presenta as seguintes propiedades adicionais: todos os vértices con grao 0 de entrada e todos os de grao 0 de saída aparecen na mesma cara (compoñente conexo disxunto que a miúdo asúmese que é a cara exterior), e é posíbel particionar a fronteira desa cara nas partes de entrada e de saída.

## Problemas relacionados 
Un problema relacionado é a resolución de consultas de atinxibilidade cun número k de fallas de vértices. Por exemplo: "O vértice u aínda consegue chegar ao vértice v aínda que os vértices s_1, s_2, ..., s_k fallaron e xa non se poden usar?" Un problema similar pode considerar a falla de aresta en lugar de falla de vértice, ou unha mestura dos dous. A busca en amplitude funciona igual que esas consultas, mais construír un oráculo eficiente é máis difícil.

Outro problema relacionado coas consultas de atinxibilidade é recalcular rapidamente as mudanzas na relación de atinxibilidade cando muda algunha parte do grafo. Por exemplo, este é un interese relevante para o recolector de lixo que precisa equilibrar a solicitude de memoria (para que poida ser reasignada) co interese de rendemento da aplicación en execución.
## Notas 
## Véxase tamén 
### Outros artigos 
* Árbore (teoría de grafos)