Acessibilidade - Reachability

Na teoria dos grafos , alcançabilidade se refere à habilidade de ir de um vértice a outro dentro de um gráfico. Um vértice pode alcançar um vértice (e é alcançável de ) se houver uma sequência de vértices adjacentes (ou seja, um caminho ) que começa com e termina com . ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle t}$ ${\ displaystyle s}$ ${\ displaystyle s}$ ${\ displaystyle t}$

Em um gráfico não direcionado, a acessibilidade entre todos os pares de vértices pode ser determinada identificando os componentes conectados do gráfico. Qualquer par de vértices em tal gráfico pode alcançar um ao outro se e somente se pertencerem ao mesmo componente conectado; portanto, em tal gráfico, a alcançabilidade é simétrica ( alcance se alcança ). Os componentes conectados de um gráfico não direcionado podem ser identificados em tempo linear. O restante deste artigo enfoca o problema mais difícil de determinar a alcançabilidade de pares em um gráfico direcionado (que, aliás, não precisa ser simétrico). ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle t}$ ${\ displaystyle s}$

Definição

Para um gráfico direcionado , com conjunto de vértices e conjunto de arestas , a relação de alcançabilidade de é o fechamento transitivo de , ou seja, o conjunto de todos os pares ordenados de vértices para os quais existe uma sequência de vértices tal que a aresta está dentro de tudo . ${\ displaystyle G = (V, E)}$ ${\ displaystyle V}$ ${\ displaystyle E}$ ${\ displaystyle G}$ ${\ displaystyle E}$ ${\ displaystyle (s, t)}$ ${\ displaystyle V}$ ${\ displaystyle v_ {0} = s, v_ {1}, v_ {2}, ..., v_ {k} = t}$ ${\ displaystyle (v_ {i-1}, v_ {i})}$ ${\ displaystyle E}$ ${\ displaystyle 1 \ leq i \ leq k}$

Se for acíclico , então sua relação de alcançabilidade é de ordem parcial ; qualquer ordem parcial pode ser definida desta forma, por exemplo como a relação de alcançabilidade de sua redução transitiva . Uma consequência digna de nota disso é que, uma vez que as ordens parciais são anti-simétricas, se podem alcançar , então sabemos que não podem alcançar . Intuitivamente, se pudéssemos viajar de para e de volta para , em seguida, iria conter um ciclo , contradizendo que é acíclico. Se for direcionado, mas não acíclico (ou seja, contém pelo menos um ciclo), então sua relação de alcançabilidade corresponderá a uma pré - ordem em vez de uma ordem parcial. ${\ displaystyle G}$ ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle t}$ ${\ displaystyle s}$ ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle s}$ ${\ displaystyle G}$ ${\ displaystyle G}$

Algoritmos

Os algoritmos para determinar a alcançabilidade se enquadram em duas classes: aqueles que requerem pré - processamento e aqueles que não.

Se você tiver apenas uma (ou algumas) consultas para fazer, pode ser mais eficiente renunciar ao uso de estruturas de dados mais complexas e calcular a acessibilidade do par desejado diretamente. Isso pode ser realizado em tempo linear usando algoritmos como pesquisa em largura ou pesquisa em profundidade de aprofundamento iterativo .

Se você for fazer muitas consultas, um método mais sofisticado pode ser usado; a escolha exata do método depende da natureza do gráfico que está sendo analisado. Em troca de tempo de pré-processamento e algum espaço de armazenamento extra, podemos criar uma estrutura de dados que pode então responder a consultas de acessibilidade em qualquer par de vértices em tão pouco tempo. Três algoritmos e estruturas de dados diferentes para três situações diferentes e cada vez mais especializadas são descritos a seguir. ${\ displaystyle O (1)}$

Algoritmo Floyd-Warshall

O algoritmo Floyd – Warshall pode ser usado para calcular o fechamento transitivo de qualquer gráfico direcionado, o que dá origem à relação de alcançabilidade como na definição acima.

O algoritmo requer tempo e espaço no pior caso. Este algoritmo não está apenas interessado na alcançabilidade, pois também calcula a distância de caminho mais curta entre todos os pares de vértices. Para gráficos contendo ciclos negativos, os caminhos mais curtos podem ser indefinidos, mas a acessibilidade entre os pares ainda pode ser observada. ${\ displaystyle O (| V | ^ {3})}$ ${\ displaystyle O (| V | ^ {2})}$

Algoritmo de Thorup

Para dígrafos planos , um método muito mais rápido está disponível, conforme descrito por Mikkel Thorup em 2004. Este método pode responder a consultas de alcançabilidade em um gráfico planar em tempo após gastar tempo de pré-processamento para criar uma estrutura de dados de tamanho. Este algoritmo também pode fornecer distâncias aproximadas do caminho mais curto, bem como informações de rota. ${\ displaystyle O (1)}$ ${\ displaystyle O (n \ log {n})}$ ${\ displaystyle O (n \ log {n})}$

A abordagem geral é associar a cada vértice um conjunto relativamente pequeno de chamados caminhos separadores, de modo que qualquer caminho de um vértice para qualquer outro vértice deve passar por pelo menos um dos separadores associados com ou . Segue um esboço das seções relacionadas à acessibilidade. ${\ displaystyle v}$ ${\ displaystyle w}$ ${\ displaystyle v}$ ${\ displaystyle w}$

Dado um gráfico , o algoritmo começa organizando os vértices em camadas a partir de um vértice arbitrário . As camadas são construídas em etapas alternadas, considerando primeiro todos os vértices alcançáveis da etapa anterior (começando com apenas ) e, em seguida, todos os vértices que alcançam a etapa anterior até que todos os vértices tenham sido atribuídos a uma camada. Pela construção das camadas, cada vértice aparece no máximo duas camadas, e cada caminho direcionado , ou dipath, em está contido em duas camadas adjacentes e . Seja a última camada criada, ou seja, o menor valor para tal . ${\ displaystyle G}$ ${\ displaystyle v_ {0}}$ ${\ displaystyle v_ {0}}$ ${\ displaystyle G}$ ${\ displaystyle L_ {i}}$ ${\ displaystyle L_ {i + 1}}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle \ bigcup _ {i = 0} ^ {k} L_ {i} = V}$

O gráfico é então reexpresso como uma série de dígrafos, onde cada e onde é a contração de todos os níveis anteriores em um único vértice. Porque cada dipath aparece em no máximo duas camadas consecutivas, e porque cada um é formado por duas camadas consecutivas, cada dipath aparece em sua totalidade em pelo menos um (e não mais do que 2 gráficos consecutivos) ${\ displaystyle G_ {0}, G_ {1}, \ ldots, G_ {k-1}}$ ${\ displaystyle G_ {i} = r_ {i} \ xícara L_ {i} \ xícara L_ {i + 1}}$ ${\ displaystyle r_ {i}}$ ${\ displaystyle L_ {0} \ ldots L_ {i-1}}$ ${\ displaystyle G_ {i}}$ ${\ displaystyle G}$ ${\ displaystyle G_ {i}}$

Para cada um deles são identificados três separadores que, ao serem removidos, quebram o gráfico em três componentes, cada um contendo no máximo os vértices do original. Como é construído a partir de duas camadas de dipaths opostos, cada separador pode consistir em até 2 dipaths, para um total de até 6 dipaths em todos os separadores. Deixe ser este conjunto de dipaths. A prova de que tais separadores sempre podem ser encontrados está relacionada ao Teorema do Separador Planar de Lipton e Tarjan, e esses separadores podem ser localizados no tempo linear. ${\ displaystyle G_ {i}}$ ${\ displaystyle 1/2}$ ${\ displaystyle G_ {i}}$ ${\ displaystyle S}$

Para cada um , a natureza direcionada de fornece uma indexação natural de seus vértices do início ao fim do caminho. Para cada vértice em , localizamos o primeiro vértice em alcançável por e o último vértice em que alcança até . Ou seja, estamos analisando o quão cedo podemos chegar e quão longe podemos ficar e ainda voltar . Essas informações são armazenadas com cada um . Em seguida, para qualquer par de vértices e , pode alcançar via if conecta a mais cedo do que conecta de . ${\ displaystyle Q \ in S}$ ${\ displaystyle Q}$ ${\ displaystyle v}$ ${\ displaystyle G_ {i}}$ ${\ displaystyle Q}$ ${\ displaystyle v}$ ${\ displaystyle Q}$ ${\ displaystyle v}$ ${\ displaystyle Q}$ ${\ displaystyle v}$ ${\ displaystyle Q}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ displaystyle u}$ ${\ displaystyle w}$ ${\ displaystyle u}$ ${\ displaystyle w}$ ${\ displaystyle Q}$ ${\ displaystyle u}$ ${\ displaystyle Q}$ ${\ displaystyle w}$ ${\ displaystyle Q}$

Cada vértice é rotulado como acima para cada etapa da recursão que se constrói . Como essa recursão tem profundidade logarítmica, um total de informações extras é armazenado por vértice. A partir deste ponto, uma consulta de tempo logarítmico para alcançabilidade é tão simples quanto olhar cada par de rótulos para um comum adequado . O artigo original então trabalha para diminuir o tempo de consulta para . ${\ displaystyle G_ {0} \ ldots, G_ {k}}$ ${\ displaystyle O (\ log {n})}$ ${\ displaystyle Q}$ ${\ displaystyle O (1)}$

Ao resumir a análise desse método, primeiro considere que a abordagem de estratificação particiona os vértices de modo que cada vértice seja considerado apenas vezes. A fase separadora do algoritmo divide o gráfico em componentes que são no máximo do tamanho do gráfico original, resultando em uma profundidade de recursão logarítmica. Em cada nível de recursão, apenas trabalho linear é necessário para identificar os separadores, bem como as conexões possíveis entre os vértices. O resultado geral é o tempo de pré - processamento com apenas informações adicionais armazenadas para cada vértice. ${\ displaystyle O (1)}$ ${\ displaystyle 1/2}$ ${\ displaystyle O (n \ log n)}$ ${\ displaystyle O (\ log {n})}$

Algoritmo de Kameda

Um dígrafo adequado para o método de Kameda com e adicionado.

{\ displaystyle s}

{\ displaystyle t}

O mesmo gráfico acima após a execução do algoritmo de Kameda, mostrando os rótulos DFS para cada vértice

Um método ainda mais rápido de pré-processamento, devido a T. Kameda em 1975, pode ser usado se o gráfico for planar , acíclico e também exibir as seguintes propriedades adicionais: todos os vértices 0- indegree e 0- outdegree aparecem no mesmo face (muitas vezes assumida como sendo a face externa), e é possível particionar o limite dessa face em duas partes, de modo que todos os vértices de grau 0 apareçam em uma parte e todos os vértices de grau zero apareçam na outra (ou seja, o dois tipos de vértices não se alternam).

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

O pré-processamento executa as seguintes etapas. Adicionamos um novo vértice que tem uma aresta para cada vértice de grau 0 e outro novo vértice com arestas de cada vértice de grau 0. Observe que as propriedades de nos permitem fazer isso enquanto mantemos a planaridade, ou seja, ainda não haverá cruzamentos de aresta após essas adições. Para cada vértice, armazenamos a lista de adjacências (arestas externas) na ordem da planaridade do grafo (por exemplo, no sentido horário em relação à incorporação do grafo). Em seguida, inicializamos um contador e iniciamos uma Traversal de profundidade a partir de . Durante essa travessia, a lista de adjacências de cada vértice é visitada da esquerda para a direita conforme necessário. Conforme os vértices são retirados da pilha do percurso, eles são rotulados com o valor e, em seguida , são decrementados. Observe que é sempre rotulado com o valor e sempre rotulado com . A travessia em profundidade é então repetida, mas desta vez a lista de adjacências de cada vértice é visitada da direita para a esquerda. ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle G}$ ${\ displaystyle i = n + 1}$ ${\ displaystyle s}$ ${\ displaystyle i}$ ${\ displaystyle i}$ ${\ displaystyle t}$ ${\ displaystyle n + 1}$ ${\ displaystyle s}$ ${\ displaystyle 0}$

Quando concluídos, e , e suas bordas incidentes, são removidos. Cada vértice restante armazena um rótulo bidimensional com valores de a . Dado dois vértices e , e seus rótulos e , dizemos que , se e somente se , e existe pelo menos um componente ou que é estritamente menor que ou , respectivamente. ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle 1}$ ${\ displaystyle n}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle L (u) = (a_ {1}, a_ {2})}$ ${\ displaystyle L (v) = (b_ {1}, b_ {2})}$ ${\ displaystyle L (u) <L (v)}$ ${\ displaystyle a_ {1} \ leq b_ {1}}$ ${\ displaystyle a_ {2} \ leq b_ {2}}$ ${\ displaystyle a_ {1}}$ ${\ displaystyle a_ {2}}$ ${\ displaystyle b_ {1}}$ ${\ displaystyle b_ {2}}$

O principal resultado desse método afirma que é alcançável a partir de se e somente se , o que é facilmente calculado no tempo. ${\ displaystyle v}$ ${\ displaystyle u}$ ${\ displaystyle L (u) <L (v)}$ ${\ displaystyle O (1)}$

Problemas relacionados

Um problema relacionado é resolver consultas de alcançabilidade com algum número de falhas de vértice. Por exemplo: "O vértice ainda pode alcançar o vértice mesmo que os vértices tenham falhado e não possam mais ser usados?" Um problema semelhante pode considerar falhas de borda em vez de falhas de vértice, ou uma mistura dos dois. A técnica de busca ampla funciona tão bem em tais consultas, mas construir um oráculo eficiente é mais desafiador. ${\ displaystyle k}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle s_ {1}, s_ {2}, ..., s_ {k}}$

Outro problema relacionado às consultas de alcançabilidade está em recalcular rapidamente as mudanças nos relacionamentos de alcançabilidade quando alguma parte do gráfico é alterada. Por exemplo, essa é uma preocupação relevante para a coleta de lixo que precisa equilibrar a recuperação de memória (para que ela possa ser realocada) com as questões de desempenho do aplicativo em execução.

Languages

In other projects