Atingibilidade (teoria dos grafos)

Em teoria dos grafos, a atingibilidade se refere a capacidade de ir de um vértice para outro em um grafo. Dizemos que um vértice $s$ pode alcançar outro vértice $t$ (ou que $t$ é atingível a partir de $s$) se exite uma sequência de vértices adjacentes (ex.: um caminho) que começam com $s$ e terminam com $t$.

Em um grafo não-direcionado, é suficiente identificar apenas os componentes conexos, assim como qualquer par de vértices, em tal grafo, pode se alcançar se e somente se eles pertencem ao mesmo componente conexo. Os componentes conexos de um grafo podem ser identificados em tempo linear. Lembramos que este artigo foca em atingibilidade nas configurações de grafos orientados.

Definição

Para um grafo direcionado $G=(V,E)$, onde $V$ é o conjunto de vértices e $E$ o conjunto de arestas, a relação de atingibilidade de $G$ é o fecho transitivo de $E$, ou seja, o conjunto dos pares ordenados $(s,t)$ com vértices em $V$ para os quais existe uma sequência de vértices $v_{0}=s,v_{1},v_{2},...,v_{k}=t$ da mesma forma que a aresta $(v_{i-1},v_{i})$ está em $E$ para todo $1\leq i\leq k$.

Se $G$ é acíclico, então sua relação de atingibilidade é um conjunto parcialmente ordenado; qualquer conjunto parcialmente ordenado deve ser definido dessa forma, por exemplo, a relação de atingibilidade da sua redução transitiva. Uma consequência notável disso é que uma vez que conjuntos parcialmente ordenados são antessimétricos, se $s$ pode alcançar $t$, então sabemos que $t$ não pode alcançar $s$. Intuitivamente, se podemos ir de $s$ para $t$ voltar para $s$, então $G$ teria um ciclo, contradizendo que ele é acíclico. Se $G$ é direcionado mas não acíclico (ex.: contem pelo menos um ciclo), então sua relação de atingibilidade irá corresponder a um pré-ordem ao em vez de um ordem parcial.

Algoritmos

Algoritmos para determinar atingibilidade se dividem em duas classes: aquelas que requerem pré-processamento e aquelas que não requerem.

Se existem apenas uma (ou poucas) consultas a serem feitas, seria mais eficiente abdicar do uso de estruturas mais complexas de dados e computar a atingibilidade do par desejado diretamente. Isto pode ser realizado em tempo linear usando algoritmos tal como busca em largura ou o IDDS um algoritmo de busca em estado espaço.

Se várias consultas serão feitas, então um método mais sofisticado pode ser usado; a escolha exata do método depende da natureza do grafo que está sendo analisado. em troca de um tempo de pré-processamento e algum espaço de armazenamento extra, é possível criar uma estrutura de dados que podem então responder as consultas de atingibilidade em qualquer par de vértices em tempo tão curto quanto $O(1)$. Três diferentes algoritmos e estruturas de dados para três diferentes para três diferentes situações cada vez mais especializadas são mostradas abaixo.

Algoritmo de Floyd-Warshall

O Algoritmo de Floyd-Warshall pode ser usado para computar o feche transitivo de qualquer grafo direcionado, que da origem a relação de atingibilidade como mostra a definição abaixo.

O algoritmo requer tempo $O(|V|^{3})$ e espaço $O(|V|^{2})$ no pior caso. Este algoritmo não é unicamente interessado em atingibilidade como também computa o caminho mais curto entre todos pares de vértices. Para grafos contendo ciclos negativos, caminhos mais curtos talvez não possam ser definidos, mas a atingibilidade entre pares ainda pode ser notada.

Algoritmo de Thorup

Para um grafo planar, um método muito mais rápido está disponível, como descrito por Mikkel Thorup em 2004. Este método pode responder a consultas de atingibilidade no grafo planar em tempo $O(1)$ depois de gastar um tempo de processamento de $O(n\log {n})$ para criar uma estrutura de dados de tamanho $O(n\log {n})$. Este algoritmo pode também fornecer aproximações de distâncias de caminhos mais curtos assim como informações de percurso.

A abordagem global é associar a cada vértice um conjunto relativamente pequeno dos chamados "caminhos separadores" de tal forma que qualquer caminho saindo de um vértice $v$ para qualquer outro vértice $w$ deve ir para, no mínimo, um dos separadores associados a $v$ ou $w$. Um esbouço das seções relacionadas a atingibilidade é mostrado a seguir.

Dado um grafo $G$, o algoritmo começa organizando os vértices em camadas começando de um vértice arbitrário $v_{0}$. As camadas são construídas em passo alternados considerando primeiro todos os vértices atingíveis partindo do paço anterior (começando apenas com $v_{0}$) e depois todos os vértices que chegam ao paço anterior até que todos os vértices tenho sido associados a uma camada. Pela construção das camadas, todo vértice aparece no máximo em duas camadas, e cada caminho direcionado, ou dipath, em $G$ está contido em duas camadas adjacentes $L_{i}$ e $L_{i+1}$. Faça $k$ ser a ultima camada criada, ou seja, o menor valor para $k$ tal que $\bigcup _{i=0}^{k}=V$.

O grafo é expressado novamente como um série de digraphs $G_{0},G_{1},\ldots ,G_{k-1}$ onde cada $G_{i}=r_{i}\cup L_{i}\cup L_{i+1}$ e onde $r_{i}$ é a contração de todos os níveis $L_{0}\ldots L_{i-1}$ em um único vértice. Porque toda dipath aparece no máximo em duas camadas consecutivas, e porque cada $G_{i}$ é formado por duas camadas consecutivas, toda dipath em $G$ aparece em sua totalidade em pelo menos um $G_{i}$ (e não mais que 2 destes grafos consecutivos).

Para cada $G_{i}$, três separadores são identificados tal que, quando removidos, separam o grafos em três componentes onde cada componente contém no máximo $1/2$ vértices do original. Como $G_{i}$ é construído a partir de duas camadas de dipaths opostas, cada separador pode consistir de 2 dipaths, para um total maior que 6 dipaths todos os separadores. Faça $S$ ser esse conjunto de dipaths. A prova de que tal separador pode sempre ser achado está relacionada com o Teorema do Separador Planar de Lipon e Tarjan, e esses separadores podem ser localizados em tempo linear.

Para cada $Q\in S$, a natureza dirigida de $Q$ permite uma indexação natural dos seu vértices do início ao fim do caminho. Para cada vértice $v$ em $G_{i}$, nós localizamos o primeiro vértice em $Q$ atingível por $v$, e o ultimo vértice em $Q$ que alcança $v$. Isto é, estamos olhando o quão cedo em $Q$ nós podemos chegar de $v$, e quão longe nós podemos estar em $Q$ e ainda voltar para $v$. Essa informação é guardada com cada $v$. Então para qualquer par de vértices $u$ e $w$, $u$ pode alcançar $w$ através de $Q$ se $u$ se conecta a $Q$ mais cedo do que $w$ é conectado de $Q$.

Todos vértice é denominado como mostrado acima para cada paço da recursão que constrói $G_{0}\ldots ,G_{k}$. Como esta recursão tem profundidade logarítmica, um total de $O(\log {n})$ de informação extra é armazenado por vértice. A partir daqui, um uma consulta de atingibilidade em tempo logarítmico é tão simples quanto procurar em cada par de vértices para um $Q$ comum e adequado. O artigo original, em seguida, trabalha para ajustar o tempo de consulta a $O(1)$.

Em resumo, a analise desse método, primeiro considera que a abordagem de estratificação divide os vértices de uma forma que cada vértice é considerado apenas em tempo ↵. A fazer de separação do algoritmo divide o grafo em componentes ↵que são no máximo do tamanho do grafo original, resultando em uma ↵recursão de profundidade logarítmica. Em cada nível da recursão, é preciso apensa de um custo linear para ↵identificar os separadores assim como as possíveis conexões entre ↵vértices. O resultado global é um tempo de pré-processamento com apenas↵ com informações adicionais armazenadas para cada vértice.

Um digraph adequado para o métodos de Kameda com $s$ e $t$ adicionados.

Algoritmo de Kameda

O mesmo grafo mostrado acima depois de ser aplicado sobre ele o algoritmo de Kameda, mostrando o rótulo DFS para cada vértice.

Um método ainda mais rápido para pré-processamento, feito por T. Kameda em 1975, pode ser usado se o gralo é planar, acíclico e também exibe as seguintes propriedades adicionais: todo vértice 0-indegree e todo vértice 0-outdegree aparece na mesma face (normalmente é assumida para ser a face exterior), e isso possibilita dividir os limites da face em duas partes tais que todos vértice 0-indegree aparece em uma parte, e todo vértice 0-outdegree aparece em outra (ex.: os dois tipos de vértices não alternam).

Se $G$ apresenta essas propriedades, então podemos pré-processar o grafo em tempo $O(n)$ apenas, e armazenar apenas $O(\log {n})$ bits extras por vértice, respondendo a consultas de atingibilidade para qualquer par de vértices em tempo $O(1)$ com uma simples comparação.

O pré-processamento realiza os seguintes paços. Um novo vértice $s$ que tem uma aresta para cada vértice 0-indegree, e outro novo vértice $t$ com aresta para cada vértice 0-outdegree. Note que as propriedades de $G$ nos permite fazê-lo mantendo a planaridade, ou seja, ainda não haverá o cruzamento de arestas depois dessa adição. Para cada vértice é guardada a lista de adjacência a fim de manter a planaridade do grafo. Depois é inicializado um contador $i=n+1$ e começa uma Depth-First Traversal a partir de $s$. Durante essa traversal, a lista de adjacência de cada vértice é visitada da esquerda para a direita de acordo com a necessidade. A medida que os vértices são retirados da pilha transversal, eles são rotulados com o valor $i$, e $i$ é então decrementado. Note que $t$ é sempre rotulado com o valor $n+1$ e $s$ é sempre rotulado com $0$. O depth-first traversal é então repetido, mas dessa vez a lista adjacente de cada vértice é visitada da direita para esquerda.

Quando completado, $s$ e $t$, e as arestas conectadas a eles, não removidas. Cada vértice que sobra armazena um rotulo de 2 dimensões com valores de $1$ a $n$. Dados dois vértices $u$ e $v$, e seus rótulos $L(u)=(a_{1},a_{2})$ e $L(v)=(b_{1},b_{2})$, dizemos que $L(u)<L(v)$ se e somente se $a_{1}\leq b_{1}$, $a_{2}\leq b_{2}$, e existe pelo menos um componente $a_{1}$ ou $a_{2}$ que é estritamente menor que $b_{1}$ ou $b_{2}$, respectivamente.

Então o resultado principal desse método afirma que $v$ é atingível a partir de $u$ se e somente se $L(u)<L(v)$, que é facilmente calculado em tempo $O(1)$.

Problemas Relacionados

Um problema relacionado é resolver consultas de atingibilidade com um número $k$ de falhas de vértice. Por exemplo: "O vértice $u$ ainda consegue alcançar o vértice $v$ mesmo se o vértices $s_{1},s_{2},...,s_{k}$ tenham falhado e não podem mais ser usados?" Um problema similar pode considerar falha de aresta em vez de falha de vértice, ou uma mistura dos dois. A técnica de busca em largura funciona assim como tais consultas, mas construir um oráculo eficiente é mais desafiador.

Outro problema relacionado a consultas de atingibilidade está em recalcular rapidamente as mudanças para a relação de atingibilidade quando alguma porção do grafo é mudada. Por exemplo, este é um interesse relevante para Coletor de Lixo que precisa balancear a requisição de memória (de modo que ela possa ser realocada) com o interesse da performance da aplicação em execução.

Veja também

• Gammoid
• st-connectivity