Componente fortemente conectado - Strongly connected component
| Tópicos relevantes sobre |
| Conectividade de gráfico |
|---|
Na teoria matemática de grafos direcionados , diz-se que um gráfico está fortemente conectado se todos os vértices forem alcançáveis de todos os outros vértices. Os componentes fortemente conectados de um gráfico direcionado arbitrariamente formam uma partição em subgráficos que são eles próprios fortemente conectados. É possível testar a forte conectividade de um gráfico, ou encontrar seus componentes fortemente conectados, em tempo linear (ou seja, Θ ( V + E )).
Definições
Um gráfico direcionado é denominado fortemente conectado se houver um caminho em cada direção entre cada par de vértices do gráfico. Ou seja, existe um caminho do primeiro vértice do par para o segundo e outro caminho do segundo vértice para o primeiro. Em um grafo orientado G que não pode por si só ser fortemente ligados, um par de vértices u e v são ditos ser fortemente ligados um ao outro se há um caminho em cada direcção entre eles.
A relação binária de estar fortemente conectado é uma relação de equivalência , e os subgráficos induzidos de suas classes de equivalência são chamados de componentes fortemente conectados . Equivalentemente, um componente fortemente conectado de um grafo direcionado G é um subgrafo fortemente conectado e maximal com esta propriedade: nenhuma aresta ou vértice adicional de G pode ser incluído no subgrafo sem quebrar sua propriedade de estar fortemente conectado. O conjunto de componentes fortemente ligados forma uma partição do conjunto de vértices de L .
Se cada componente fortemente ligado é contratada para um único vértice, o gráfico resultante é um gráfico acíclico dirigido , a condensação de G . Um grafo direcionado é acíclico se e somente se não tiver subgráficos fortemente conectados com mais de um vértice, porque um ciclo direcionado é fortemente conectado e cada componente não trivial fortemente conectado contém pelo menos um ciclo direcionado.
Algoritmos
Algoritmos de tempo linear baseados em DFS
Vários algoritmos baseados na primeira pesquisa de profundidade computam componentes fortemente conectados em tempo linear .
- O algoritmo de Kosaraju usa duas passagens de primeira pesquisa em profundidade . O primeiro, no gráfico original, é usado para escolher a ordem em que o loop externo da segunda pesquisa de primeira profundidade testa os vértices por já terem sido visitados e os explora recursivamente, caso contrário. A segunda pesquisa de profundidade está no gráfico de transposição do gráfico original, e cada exploração recursiva encontra um único novo componente fortemente conectado. Recebeu o nome de S. Rao Kosaraju , que o descreveu (mas não publicou seus resultados) em 1978; Micha Sharir posteriormente o publicou em 1981.
- O algoritmo de componentes fortemente conectados de Tarjan , publicado por Robert Tarjan em 1972, executa uma única passagem de primeira pesquisa em profundidade. Ele mantém uma pilha de vértices que foram explorados pela pesquisa, mas ainda não atribuídos a um componente, e calcula "números baixos" de cada vértice (um número de índice do ancestral mais alto alcançável em uma etapa de um descendente do vértice) que ele usa para determinar quando um conjunto de vértices deve ser retirado da pilha para um novo componente.
- O algoritmo de componente forte baseado em caminho usa uma primeira pesquisa em profundidade, como o algoritmo de Tarjan, mas com duas pilhas. Uma das pilhas é usada para rastrear os vértices ainda não atribuídos aos componentes, enquanto a outra rastreia o caminho atual na primeira árvore de pesquisa de profundidade. A primeira versão de tempo linear desse algoritmo foi publicada por Edsger W. Dijkstra em 1976.
Embora o algoritmo de Kosaraju seja conceitualmente simples, o algoritmo de Tarjan e o algoritmo baseado em caminhos requerem apenas uma pesquisa em profundidade em vez de duas.
Algoritmos baseados em acessibilidade
Os algoritmos de tempo linear anteriores são baseados na pesquisa em profundidade, que geralmente é considerada difícil de paralelizar. Fleischer et al. em 2000, propôs uma abordagem de dividir e conquistar com base em consultas de alcançabilidade , e tais algoritmos são normalmente chamados de algoritmos SCC baseados em alcançabilidade. A ideia dessa abordagem é escolher um vértice de pivô aleatório e aplicar consultas de acessibilidade para frente e para trás a partir desse vértice. As duas consultas particionam o conjunto de vértices em 4 subconjuntos: vértices alcançados por ambos, um ou nenhuma das pesquisas. Pode-se mostrar que um componente fortemente conectado deve estar contido em um dos subconjuntos. O subconjunto de vértices alcançado por ambas as pesquisas forma componentes fortemente conectados, e o algoritmo então recorre nos outros 3 subconjuntos.
O tempo de execução sequencial esperado desse algoritmo é mostrado como O ( n log n ), um fator de O (log n ) a mais do que os algoritmos clássicos. O paralelismo vem de: (1) as consultas de alcançabilidade podem ser paralelizadas mais facilmente (por exemplo, por uma pesquisa em largura (BFS), e pode ser rápido se o diâmetro do gráfico for pequeno); e (2) a independência entre as subtarefas no processo de dividir para conquistar. Este algoritmo tem um bom desempenho em gráficos do mundo real, mas não tem garantia teórica sobre o paralelismo (considere se um gráfico não possui arestas, o algoritmo requer O ( n ) níveis de recursões).
Blelloch et al. em 2016 mostra que se as consultas de alcançabilidade forem aplicadas em uma ordem aleatória, o limite de custo de O ( n log n ) ainda se mantém. Além disso, as consultas podem então ser agrupadas em uma maneira de duplicação de prefixo (ou seja, 1, 2, 4, 8 consultas) e executadas simultaneamente em uma rodada. A extensão geral desse algoritmo é log 2 n consultas de alcançabilidade, que é provavelmente o paralelismo ideal que pode ser alcançado usando a abordagem baseada em alcançabilidade.
Gerando gráficos aleatórios fortemente conectados
Peter M. Maurer descreve um algoritmo para gerar grafos fortemente conectados aleatórios, baseado em uma modificação de um algoritmo para aumento de conectividade forte , o problema de adicionar o mínimo de arestas possível para fazer um grafo fortemente conectado. Quando usado em conjunto com os modelos Gilbert ou Erdős-Rényi com reclassificação de nós, o algoritmo é capaz de gerar qualquer grafo fortemente conectado em n nós, sem restrição aos tipos de estruturas que podem ser gerados.
Formulários
Algoritmos para encontrar componentes fortemente conectados podem ser usados para resolver problemas de 2-satisfatibilidade (sistemas de variáveis booleanas com restrições nos valores dos pares de variáveis): como Aspvall, Plass & Tarjan (1979) mostraram, uma instância de 2-satisfatibilidade é insatisfatória se e somente se houver uma variável v tal que v e seu complemento estão ambos contidos no mesmo componente fortemente conectado do gráfico de implicação da instância.
Componentes fortemente conectados também são usados para calcular a decomposição de Dulmage – Mendelsohn , uma classificação das arestas de um grafo bipartido , de acordo com se podem ou não fazer parte de uma combinação perfeita no gráfico.
Resultados relacionados
Um gráfico direcionado está fortemente conectado se e somente se tiver uma decomposição em orelha , uma partição das arestas em uma sequência de caminhos e ciclos direcionados de modo que o primeiro subgráfico na sequência seja um ciclo e cada subgrafo subsequente seja um compartilhamento de ciclo um vértice com subgráficos anteriores ou um caminho que compartilha seus dois pontos finais com subgráficos anteriores.
De acordo com o teorema de Robbins , um grafo não direcionado pode ser orientado de tal forma que se torne fortemente conectado, se e somente se for conectado por 2 arestas . Uma maneira de provar esse resultado é encontrar uma decomposição de orelha do gráfico não direcionado subjacente e, em seguida, orientar cada orelha de forma consistente.
Veja também
Referências
links externos
- Implementação Java para computação de componentes fortemente conectados na biblioteca jBPT (consulte a classe StronglyConnectedComponents).
- Implementação C ++ de componentes fortemente conectados