Conectividade dinâmica - Dynamic connectivity

Na teoria da computação e dos gráficos , uma estrutura de conectividade dinâmica é uma estrutura de dados que mantém dinamicamente informações sobre os componentes conectados de um gráfico.

O conjunto V de vértices do gráfico é fixo, mas o conjunto E de arestas pode mudar. Os três casos, em ordem de dificuldade, são:

• As bordas são adicionadas apenas ao gráfico (isso pode ser chamado de conectividade incremental );
• As bordas são excluídas apenas do gráfico (isso pode ser chamado de conectividade decremental );
• As bordas podem ser adicionadas ou excluídas (isso pode ser chamado de conectividade totalmente dinâmica ).

Após cada adição / exclusão de uma aresta, a estrutura de conectividade dinâmica deve se adaptar de forma que possa dar respostas rápidas às perguntas da forma "há um caminho entre x e y ?" (equivalentemente: "fazer vértices x e y pertencem ao mesmo componente conectado?").

Conectividade incremental

Se as bordas só podem ser adicionadas, o problema de conectividade dinâmica pode ser resolvido por uma estrutura de dados Disjoint-set . Cada conjunto representa um componente conectado; existe um caminho entre x e y se e somente se eles pertencem ao mesmo conjunto. O tempo amortizado por operação é , onde n é o número de vértices e α é a função de Ackermann inversa . ${\ displaystyle \ Theta (\ alpha (n))}$

Conectividade decremental

O caso em que as bordas só podem ser excluídas foi resolvido por Shimon Even e Yossi Shiloach .

A estrutura utiliza uma tabela que especifica, para cada vértice, o nome do componente ao qual pertence. Portanto, uma consulta de conectividade leva um tempo constante. O desafio é atualizar a tabela quando uma borda é excluída.

Gráficos acíclicos (florestas)

Quando a aresta u - v é excluída em uma floresta , a árvore que contém essa aresta é dividida em duas árvores: uma delas contém u e a outra contém v . A tabela é atualizada da seguinte maneira.

• Faça a varredura da árvore começando em u (usando qualquer algoritmo de varredura de árvore, como DFS ).
• Faça a varredura da árvore começando em v .
• Faça os dois procedimentos acima em paralelo, ou seja, usando dois processos paralelos ou intercalando suas etapas (faça uma etapa da primeira varredura, depois uma etapa da segunda varredura, depois uma etapa da primeira varredura, etc.).
• Suponha que a primeira varredura que termina seja a varredura de u (portanto, sabemos que a árvore que contém u é a menor). Atribua um novo nome de componente a cada nó na subárvore de u .

Como sempre renomeamos o subcomponente menor, o tempo amortizado para uma operação de exclusão é . ${\ displaystyle O (\ log (n))}$

Gráficos gerais

Quando uma aresta é excluída em um gráfico geral, não sabemos se seu componente permanece um único componente (conectado por outras arestas) ou dividido em dois componentes. Portanto, usamos dois processos que funcionam em paralelo (ou de forma intercalada). O processo A verifica se a exclusão da borda quebra um componente e, se isso acontecer, ambos os processos param. O processo B verifica se a exclusão da borda não interrompe o componente ao qual pertence e, se não, novamente ambos os processos param.

Processo A

é semelhante ao caso do gráfico acíclico: há dois subprocessos que fazem a varredura de ambas as extremidades da borda excluída. Se um dos subprocessos termina antes de chegar à outra extremidade, isso significa que o componente é dividido em dois subcomponentes e o nome do subcomponente menor é atualizado, como antes. Portanto, o tempo amortizado para uma operação de exclusão é novamente . ${\ displaystyle O (\ log (n))}$

Processo B

usa uma estrutura em largura (BFS), que é inicializada da seguinte maneira. Um vértice r é escolhido e o BFS começa a partir dele. O único vértice no nível 0 é r . Todos os vértices de distância i da raiz estão no nível i . Se G não estiver conectado, uma nova varredura é iniciada em algum vértice não varrido v , v é colocado no nível 1 e uma aresta artificial conecta v à raiz r ; todos os vértices da distância i de v estão agora no nível i +1, etc. Arestas artificiais são introduzidas a fim de manter todos os componentes conectados em uma estrutura BFS e são usadas apenas para este propósito. Claramente, as bordas artificiais são usadas apenas no processo B.

A estrutura possui as seguintes propriedades. Um vértice v no nível i , i > 0, tem apenas três tipos de arestas: arestas posteriores que o conectam ao nível i -1 (há pelo menos uma dessas arestas, que pode ser artificial), arestas locais que o conectam a outro arestas no nível i (há zero ou mais dessas arestas), ou arestas dianteiras que o conectam às arestas no nível i +1 (há zero ou mais dessas arestas). Portanto, para cada vértice v , mantemos três conjuntos de arestas (anterior, local e posterior).

Quando uma aresta u - v é excluída, há duas opções: u e v estão no mesmo nível ou estão em níveis cujo número difere por 1.

Caso 1

tanto u e v estão no mesmo nível. Neste caso, a exclusão da borda não pode alterar os componentes. A borda é simplesmente suprimida a partir dos conjuntos de arestas locais de u e v , e interrompe o processo B (e, portanto, o processo A é interrompida também). Nossa estrutura BFS ainda é válida.

Caso 2

u e v estão em níveis diferentes. Sem perda de generalidade, suponha que u esteja no nível i −1 ev está no nível i ; portanto, a borda deve ser removida da frente ( u ) e de trás ( v ).

Caso 2.1

Se o novo verso ( v ) não estiver vazio, então os componentes não mudaram: há outras arestas que conectam v para trás. O processo B é interrompido (e o processo A também é interrompido).

Caso 2.2

Se o novo reverso ( v ) está vazio, então v não está mais conectado ao nível i −1 e, portanto, sua distância da raiz não é mais i ; deve ser pelo menos i +1. Além disso, pode haver outros vértices, conectados av , cuja distância da raiz aumenta como resultado da exclusão. Para calcular as distâncias atualizadas, usamos uma fila Q, que inicialmente contém apenas o vértice v .

Enquanto Q não estiver vazio:

1. w  : = desenfileirar (Q)
2. Remova w de seu nível (digamos, j ) e coloque-o no próximo nível ( j +1).
3. Atualize os vizinhos locais:
   • Para cada aresta w - x em local ( w ), remova-a de local ( x ) e coloque-a em frente ( x ).
   • para trás ( w ): = local ( w )
4. Atualize os vizinhos avançados:
   • Para cada aresta w - x na frente ( w ), remova-a de trás ( x ) e coloque-a no local ( x ); se o novo backward ( x ) estiver vazio, enfileire x em Q.
   • local ( w ): = para a frente ( w )
   • para a frente ( w ): = conjunto vazio
5. Se o novo backward ( w ) estiver vazio, enfileire w novamente em Q.

Se a exclusão da borda não quebrar nenhum componente e estivermos no caso 2.2, então o procedimento será interrompido. Nesse caso, é fácil ver que a estrutura do BFS é mantida corretamente. Se sua exclusão quebrar um componente, o procedimento não será interrompido por si só. No entanto, o processo A, reconhecendo a quebra, será interrompido e ambos os processos serão interrompidos. Nesse caso, todas as alterações feitas na estrutura do BFS são ignoradas e voltamos à estrutura do BFS que tínhamos antes da exclusão, exceto que a borda excluída agora é substituída por uma borda artificial. Claramente, neste caso v agora é a raiz de uma árvore que inclui o novo componente, e talvez componentes adicionais, por meio de algumas outras arestas artificiais. Além disso, não existem arestas que ligam os descendentes de v com quaisquer vértices, que não são v descendentes 's, exceto a borda artificial . ${\ displaystyle uv}$

sempre que uma borda é processada no procedimento, um de seus pontos de extremidade cai um nível. Como o nível mais baixo que um vértice pode atingir em execuções que são encerradas pelo processo B é , o custo por aresta é limitado por . Portanto, o tempo amortizado por operação de exclusão é . ${\ displaystyle | V | -1}$${\ displaystyle 2 | V |}$${\ displaystyle O (n)}$

Conectividade totalmente dinâmica

Gráficos acíclicos (florestas)

Uma floresta pode ser representada usando uma coleção de árvores cortadas por link ou árvores de passeio de Euler . Então, o problema de conectividade dinâmica pode ser resolvido facilmente, pois para cada dois nós x, y, x é conectado ay se e somente se FindRoot (x) = FindRoot (y). O tempo de atualização amortizado e o tempo de consulta são ambos O (log ( n )).

Gráficos gerais

Um gráfico geral pode ser representado por sua floresta abrangente - uma floresta que contém uma árvore para cada componente conectado do gráfico. Chamamos isso de floresta geradora F . O próprio F pode ser representado por uma floresta de árvores de excursão Euler .

As operações de consulta e de inserção são implementados usando as operações correspondentes nas árvores ET representando F . A operação é desafiando Eliminar, e em particular, a eliminação de uma borda que está contido em uma das árvores de expansão de F . Isso divide a árvore geradora em duas árvores, mas é possível que haja outra borda que as conecte. O desafio é encontrar rapidamente essa borda de substituição, se houver. Isso requer uma estrutura de dados mais complexa. Várias dessas estruturas são descritas abaixo.

A estrutura de nível

Cada aresta do gráfico é atribuída a um nível . Seja L = lg n . O nível de cada aresta inserida no gráfico é inicializado em L e pode diminuir para 0 durante as operações de exclusão.

Para cada i entre 0 e L , defina Gi como o subgráfico que consiste em arestas que estão no nível i ou menos, e Fi uma floresta abrangente de Gi . Nossa floresta F de antes agora é chamada de FL . Manteremos uma sequência decrescente de florestas FL ⊇ ... ⊇ F 0.

Operações

As operações de consulta e inserção usam apenas o maior FL da floresta . Os subgráficos menores são consultados apenas durante uma operação Delete e, em particular, excluindo uma aresta que está contida em uma das árvores geradoras de FL .

Quando tal aresta e = x - y é excluída, ela é primeiro removida de FL e de todas as florestas abrangentes menores às quais pertence, ou seja, de cada Fi com nível i ≥ ( e ). Em seguida, procuramos uma borda de substituição.

Comece com a menor floresta abrangente que continha e , a saber, Fi com i = nível ( e ). A aresta e pertence a uma determinada árvore T ⊆ Fi . Após a exclusão de e , a árvore T é dividida em duas árvores menores: Tx que contém o nó x e Ty que contém o nó y . Uma aresta de Gi é uma aresta de substituição, se e somente se conecta um nó em Tx com um nó em Ty . Suponha que o wlog Tx seja a árvore menor (ou seja, contém no máximo metade dos nós de T ; podemos dizer o tamanho de cada subárvore por uma anotação adicionada às árvores de Euler).

Fazemos um loop sobre todas as arestas ε com nível i e pelo menos um nó em Tx :

• Se o outro nó de ε está em Ty , então uma aresta de substituição é encontrada! Adicione esta borda a Fi e a todos os que contêm florestas até FL e finalize. As florestas abrangentes são fixas. Observe que para pagar por esta pesquisa, diminuímos o nível das arestas visitadas durante a pesquisa.
• Se o outro nó de ε está em Tx , então esta não é uma aresta de substituição, e para 'penalizá-la' por desperdiçar nosso tempo, diminuímos seu nível em 1.

Análise

O nível de cada borda será diminuído no máximo lg n vezes. Por quê? Porque a cada diminuição, ele cai em uma árvore cujo tamanho é no máximo metade do tamanho de sua árvore no nível anterior. Portanto, em cada nível i , o número de nós em cada componente conectado é no máximo 2 ⁱ . Portanto, o nível de uma aresta é sempre pelo menos 0.

Cada borda cujo nível é diminuído leva tempo para ser encontrada (usando as operações da árvore ET). No total, cada aresta inserida leva algum tempo até que seja excluída, portanto, o tempo amortizado para exclusão é . A parte restante da exclusão também leva tempo, já que temos que excluir a borda da maioria dos níveis, e a exclusão de cada nível leva (novamente usando as operações ET). ${\ displaystyle O (\ lg n)}$${\ displaystyle O (\ lg ^ {2} n)}$${\ displaystyle O (\ lg ^ {2} n)}$${\ displaystyle O (\ lg ^ {2} n)}$${\ displaystyle O (\ lg n)}$${\ displaystyle O (\ lg n)}$

No total, o tempo amortizado por atualização é . O tempo por consulta pode ser melhorado para . ${\ displaystyle O (\ lg ^ {2} n)}$${\ displaystyle O (\ lg n / \ lg \ lg n)}$

No entanto, o pior caso por atualização pode ser . A questão de saber se o pior caso de tempo pode ser melhorado era uma questão em aberto, até que foi resolvida afirmativamente pela estrutura de Cutset. ${\ displaystyle O (n)}$

A estrutura Cutset

Dado um gráfico G (V, E) e um subconjunto T⊆V, defina o conjunto de cortes (T) como o conjunto de arestas que conectam T com V \ T. A estrutura do cutset é uma estrutura de dados que, sem manter o gráfico inteiro na memória, pode encontrar rapidamente uma aresta no cutset, se tal aresta existir.

Comece dando um número para cada vértice. Suponha que haja n vértices; então, cada vértice pode ser representado por um número com lg ( n ) bits. A seguir, dê um número para cada aresta, que é uma concatenação dos números de seus vértices - um número com 2 lg ( n ) bits.

Para cada vértice v , calcule e mantenha xor ( v ), que é o xor dos números de todas as arestas adjacentes a ele.

Agora, para cada T⊆V subconjunto, é possível calcular XOR (t) = a XOR dos valores de todos os vértices em T. Considere uma aresta de e = u - v , que é uma borda interna de T (ou seja, tanto u e v estão em T). O número de e é incluído duas vezes em xor (T) - uma vez para u e uma vez para v . Como o xor de cada número consigo mesmo é 0, e desaparece e não afeta xor (T). Portanto, xor (T) é na verdade o xor de todas as arestas no conjunto de cortes (T). Existem várias opções:

• Se xor (T) = 0, então podemos responder com segurança que o cutset (T) está vazio.
• Se xor (T) é o número de uma aresta real e , então provavelmente e é a única aresta no conjunto de corte (T), e podemos retornar e . Também podemos ler os pontos finais de e a partir do número de e dividindo-o em lg ( n ) bits mais à esquerda e lg ( n ) bits mais à direita.
• A terceira opção é que xor (T) é um número diferente de zero que não representa uma aresta real. Isso só pode acontecer se houver duas ou mais arestas no conjunto de cortes (T), uma vez que, nesse caso, xor (T) é xor de vários números de arestas. Nesse caso, relatamos "falha", pois sabemos que existem arestas no cutset, mas não podemos identificar nenhuma aresta única.

Nosso objetivo agora é lidar com essa terceira opção.

Primeiro, crie uma sequência de níveis lg ( n ) das estruturas de conjunto de cortes, cada uma contendo cerca de metade das arestas do nível superior (ou seja, para cada nível, escolha cada aresta do nível superior com probabilidade 1/2). Se no primeiro nível xor (T) retornar um valor ilegal, o que significa que cutset (T) tem duas ou mais arestas, então há uma chance de que no próximo nível, que contém menos arestas, xor (T) retornará um valor legal valor desde o cutset (T) irá conter uma única aresta. Se xor (T) ainda retorna um valor ilegal, continue para o próximo nível, etc. Como o número de arestas está diminuindo, há dois casos:

• O bom caso é que finalmente encontramos um nível no qual o conjunto de cortes (T) contém uma única aresta; então retornamos essa borda e finalizamos.
• O caso ruim é que eventualmente encontramos um nível no qual cutset (T) não contém arestas; então relatamos "falha", pois sabemos que existem arestas no cutset, mas não podemos identificar nenhuma aresta única.

É possível comprovar que a probabilidade de sucesso é de pelo menos 1/9.

Em seguida, crie uma coleção de versões independentes C  lg ( n ) da estrutura de nível, onde C é uma constante. Em cada versão, faça uma redução aleatória independente das arestas de nível para nível. Tente cada consulta em cada uma das versões até que uma delas seja bem-sucedida. A probabilidade de que todas as versões falhem é no máximo:

${\ displaystyle (1-1 / 9) ^ {C \ lg {n}} = 2 ^ {- 0,17C \ lg {n}} = n ^ {- 0,17C}}$

Pela seleção adequada de C , podemos tornar a probabilidade de falha arbitrariamente próxima de 0.

Operações

Podemos adicionar uma estrutura de cutset a uma estrutura de conectividade dinâmica.

As operações Insert e Delete na estrutura do cutset são feitas exatamente da mesma maneira: a aresta inserida / excluída é XORed em ambas as suas extremidades.

Quando uma aresta é excluída da floresta de abrangência usada para a estrutura de conectividade dinâmica, a estrutura do conjunto de cortes é usada para encontrar uma aresta substituta.

Análise

Uma única estrutura de conjunto de cortes requer apenas memória O ( n lg n ) - apenas um único número, com 2 lg n bits, para cada um dos n vértices. Não temos que manter as próprias bordas. Para gráficos densos, isso é muito mais barato do que manter o gráfico inteiro na memória.

Temos que manter as versões lg ( n ), cada uma contendo níveis lg ( n ). Portanto, o requisito de memória total é . ${\ displaystyle O (n \ lg ^ {3} n)}$

O tempo de consulta é O (polylog ( n )) no pior caso. Isso está em contraste com a estrutura The Level , em que o tempo de consulta é O (polylog ( n )) amortizado, mas o tempo de pior caso é O ( n ).

Conectividade dinâmica offline

Se a ordem em que as arestas serão excluídas for conhecida com antecedência, podemos resolver o problema de conectividade dinâmica em log (n) por consulta. Se pudermos manter uma Floresta de Extensão Máxima onde as arestas são ordenadas por seu tempo de exclusão, sabemos que quando excluímos alguma aresta que está na floresta, não há aresta possível que possa substituí-la. Se houvesse alguma aresta que conecta os mesmos dois componentes que a aresta excluída faz, então essa outra aresta faria parte da floresta de extensão máxima em vez da aresta que excluímos. Isso torna a operação de exclusão trivial: simplesmente precisamos dividir a árvore em duas partes se a aresta a ser excluída fizer parte de nossa floresta ou, caso contrário, ignorar a operação.

Adicionar uma borda é um pouco mais complicado. Se adicionarmos uma aresta e de u a v, então se uev não estiverem conectados, então esta aresta fará parte da Floresta de Extensão Máxima. Se eles estiverem conectados, queremos adicionar u-> v à nossa floresta, se isso puder melhorar nossa Floresta de Extensão Máxima. Para fazer isso, precisamos verificar rapidamente qual aresta tem o menor tempo de remoção no caminho de u a v. Se o tempo de remoção dessa aresta vier após o tempo de remoção de e, então não podemos melhorar nossa floresta de abrangência mínima. Caso contrário, a outra aresta deve ser excluída e substituída por e.

Isso requer que façamos as seguintes operações: adicionar uma aresta, cortar uma aresta e consultar a aresta mínima em um caminho, o que pode ser feito facilmente com uma árvore de corte de link em log (n) por operação.

Veja também

• Problema dinâmico (algoritmos)
• Refinamento de partição

Referências

• Veja também: Thorup, M. (2000). Conectividade de gráfico totalmente dinâmico quase ideal . Anais do trigésimo segundo simpósio anual da ACM em Teoria da Computação - STOC '00. p. 343. doi : 10.1145 / 335305.335345 . ISBN   1581131844 .