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