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  pode chegar a outro vértice  (ou que  é atinxíbel desde ) se hai unha secuencia de vértices adxacentes (por exemplo, un camiño) que comezan por  e terminan con .

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 , onde  é o conxunto de vértices e  o conxunto de arestas, a relación de atinxibilidade de  é o peche transitivo de , é dicir, o conxunto de pares ordenados  con vértices en  para os que existe unha secuencia de vértices  do mesmo xeito que a aresta  está en  para todo .

 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  e  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  de fallas de vértices. Por exemplo: "O vértice  aínda consegue chegar ao vértice  aínda que os vértices  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)

Categoría:Teoría de grafos