Árvore de abrangência mínima - Minimum spanning tree

Um gráfico plano e sua árvore geradora mínima. Cada aresta é rotulada com seu peso, que aqui é aproximadamente proporcional ao seu comprimento.

Uma árvore de cobertura mínima ( MST ) ou de peso mínima abrangendo árvore é um subconjunto das arestas de um ligado grafo não-dirigido, ponderada de ponta que liga todos os vértices juntos, sem quaisquer ciclos e com o peso total de borda mínimo possível. Ou seja, é uma árvore geradora cuja soma dos pesos das arestas é a menor possível. De modo mais geral, qualquer grafo não direcionado de aresta ponderada (não necessariamente conectado) tem uma floresta de abrangência mínima , que é uma união das árvores de abrangência mínima para seus componentes conectados .

Existem muitos casos de uso para árvores abrangentes mínimas. Um exemplo é uma empresa de telecomunicações tentando instalar um cabo em um novo bairro. Se for restringido a enterrar o cabo apenas ao longo de certos caminhos (por exemplo, estradas), então haveria um gráfico contendo os pontos (por exemplo, casas) conectados por esses caminhos. Alguns dos caminhos podem ser mais caros, porque são mais longos ou exigem que o cabo seja enterrado mais profundamente; esses caminhos seriam representados por arestas com pesos maiores. A moeda é uma unidade aceitável para o peso da aresta - não há requisitos para que os comprimentos das arestas obedeçam às regras normais de geometria, como a desigualdade do triângulo . Uma árvore geradora para esse gráfico seria um subconjunto desses caminhos que não tem ciclos, mas ainda conecta todas as casas; pode haver várias árvores abrangentes possíveis. Um spanning tree mínimo seria aquele com o menor custo total, representando o caminho menos caro para colocar o cabo.

Propriedades

Possível multiplicidade

Se houver $n$ vértices no gráfico, cada árvore geradora terá $n - 1$ arestas.

Esta figura mostra que pode haver mais de uma árvore de abrangência mínima em um gráfico. Na figura, as duas árvores abaixo do gráfico são duas possibilidades de árvore geradora mínima do gráfico fornecido.

Pode haver várias árvores abrangentes mínimas com o mesmo peso; em particular, se todos os pesos das arestas de um dado gráfico são os mesmos, então cada árvore geradora desse gráfico é mínima.

Singularidade

Se cada aresta tiver um peso distinto, haverá apenas uma única árvore geradora mínima . Isso é verdade em muitas situações realistas, como no exemplo da empresa de telecomunicações acima, em que é improvável que dois caminhos tenham exatamente o mesmo custo. Isso também se generaliza para florestas abrangentes.

Prova:

Suponha o contrário , que existem dois MSTs A e B diferentes .
Como A e B diferem apesar de conterem os mesmos nós, há pelo menos uma aresta que pertence a um, mas não ao outro. Entre essas arestas, seja e ₁ a que tem menos peso; esta escolha é única porque os pesos das arestas são todos distintos. Sem perda de generalidade, assuma e ₁ está em um .
Como B é um MST, { e ₁ } B deve conter um ciclo C com e ₁ . ${\ displaystyle \ cup}$
Como uma árvore, A não contém ciclos, portanto C deve ter uma aresta e ₂ , que não é em um .
Visto que e ₁ foi escolhido como a única aresta de menor peso entre aquelas pertencentes a exatamente um de A e B , o peso de e ₂ deve ser maior que o peso de e ₁ .
Como e ₁ e e ₂ fazem parte do ciclo C, substituir e ₂ por e ₁ em B, portanto, resulta em uma árvore geradora com um peso menor.
Isso contradiz a suposição de que B é um MST.

De maneira mais geral, se os pesos das arestas não forem todos distintos, então apenas o (multi) conjunto de pesos nas árvores de abrangência mínima certamente será único; é o mesmo para todas as árvores abrangentes mínimas.

Subgrafo de custo mínimo

Se os pesos forem positivos , então uma árvore geradora mínima é de fato um subgrafo de custo mínimo conectando todos os vértices, uma vez que os subgráficos contendo ciclos necessariamente têm mais peso total.

Propriedade de ciclo

Para qualquer ciclo $C$ no gráfico, se o peso de uma aresta $e$ de $C$ for maior do que os pesos individuais de todas as outras arestas de $C$ , então essa aresta não pode pertencer a um MST.

Prova: Suponha o contrário , ou seja, que $e$ pertence a um MST $T 1$ . Em seguida, a exclusão $de e$ vai quebrar $T 1$ em duas sub-árvores com as duas extremidades $e$ em diferentes sub-árvores. A parte restante de $C$ volta a ligar os sub-árvores, por conseguinte, há uma borda $F$ de $C$ com extremidades em diferentes sub-árvores, isto é, que volta a ligar os sub-árvores em uma árvore $t 2$ com um peso menor do que a de $T 1$ , porque o peso de $f$ for inferior a o peso de $e$ .

Propriedade de corte

Esta figura mostra a propriedade de corte dos MSTs. T é o único MST do gráfico fornecido. Se S = {A, B, D, E}, então VS = {C, F}, então existem 3 possibilidades da aresta através do corte (S, VS), elas são arestas BC, EC, EF do original gráfico. Então, e é uma das arestas de peso mínimo para o corte, portanto S ∪ {e} faz parte do MST T.

Para qualquer corte C do gráfico, se o peso de uma aresta e no conjunto de corte de C for estritamente menor do que os pesos de todas as outras arestas do conjunto de corte de C , então esta aresta pertence a todos os MSTs do gráfico .

Prova: Suponha que haja um MST T que não contenha e . Adicionar e a T produzirá um ciclo, que cruza o corte uma vez em e e cruza de volta em outra aresta e ' . Excluindo e ' obtemos uma árvore geradora T ∖ {e'} ∪ {e} de peso estritamente menor que T . Isso contradiz a suposição de que T era um MST.

Por um argumento semelhante, se mais de uma aresta tem peso mínimo em um corte, então cada aresta está contida em alguma árvore geradora mínima.

Limite de custo mínimo

Se a aresta de custo mínimo e de um gráfico for única, essa aresta será incluída em qualquer MST.

Prova: se e não fosse incluído no MST, a remoção de qualquer uma das arestas (de maior custo) do ciclo formado após a adição de e ao MST resultaria em uma árvore geradora de menor peso.

Contração

Se T é uma árvore de arestas MST, então podemos contrair T em um único vértice enquanto mantemos a invariante que a MST do grafo contraído mais T dá a MST para o gráfico antes da contração.

Algoritmos

Em todos os algoritmos abaixo, m é o número de arestas no gráfico e n é o número de vértices.

Algoritmos clássicos

O primeiro algoritmo para encontrar uma árvore geradora mínima foi desenvolvido pelo cientista tcheco Otakar Borůvka em 1926 (veja o algoritmo de Borůvka ). Seu objetivo era uma cobertura elétrica eficiente da Morávia . O algoritmo prossegue em uma sequência de estágios. Em cada estágio, denominado passo de Boruvka , ele identifica uma floresta F consistindo na aresta de peso mínimo incidente em cada vértice do grafo G , e então forma o gráfico como entrada para a próxima etapa. Aqui denota o gráfico derivado de G pelas arestas em contração em F (pela propriedade Cut , essas arestas pertencem ao MST). Cada etapa do Boruvka leva um tempo linear. Como o número de vértices é reduzido em pelo menos metade em cada etapa, o algoritmo de Boruvka leva um tempo O ( m log n ). ${\ displaystyle G_ {1} = G \ setminus F}$ ${\ displaystyle G \ setminus F}$

Um segundo algoritmo é o algoritmo de Prim , que foi inventado por Vojtěch Jarník em 1930 e redescoberto por Prim em 1957 e Dijkstra em 1959. Basicamente, ele aumenta o MST ( T ) uma aresta de cada vez. Inicialmente, T contém um vértice arbitrário. Em cada passo, T é aumentada com uma borda menor peso ( x , y ) tais que x é em T e Y não está ainda em T . Pela propriedade Cut , todas as arestas adicionadas a T estão no MST. Seu tempo de execução é O ( m log n ) ou O ( m + n log n ), dependendo das estruturas de dados usadas.

Um terceiro algoritmo comumente usado é o algoritmo de Kruskal , que também leva tempo O ( m log n ).

Um quarto algoritmo, não tão comumente usado, é o algoritmo de exclusão reversa , que é o inverso do algoritmo de Kruskal. Seu tempo de execução é O ( m log n (log log n ) ³ ).

Todos os quatro são algoritmos gananciosos . Uma vez que eles correm em tempo polinomial, o problema de encontrar tais árvores é em FP , e afins problemas de decisão , tais como determinar se uma borda em particular é no MST ou determinando se o peso total mínimo excede um determinado valor são em P .

Algoritmos mais rápidos

Vários pesquisadores tentaram encontrar algoritmos mais eficientes do ponto de vista computacional.

Em um modelo de comparação, no qual as únicas operações permitidas nos pesos das arestas são comparações de pares, Karger, Klein & Tarjan (1995) encontraram um algoritmo linear aleatório no tempo baseado em uma combinação do algoritmo de Borůvka e o algoritmo de exclusão reversa.

O algoritmo baseado em comparação não aleatório mais rápido com complexidade conhecida, de Bernard Chazelle , é baseado no soft heap , uma fila de prioridade aproximada. Seu tempo de execução é O ( m α ( m , n )), onde α é o inverso funcional clássico da função de Ackermann . A função α cresce muito lentamente, de modo que, para todos os efeitos práticos, pode ser considerada uma constante não maior que 4; assim, o algoritmo de Chazelle leva muito perto do tempo linear.

Algoritmos de tempo linear em casos especiais

Gráficos densos

Se o gráfico for denso (ou seja, m / n ≥ log log log n ), então um algoritmo determinístico de Fredman e Tarjan encontra o MST no tempo O ( m ). O algoritmo executa várias fases. Cada fase executa o algoritmo de Prim muitas vezes, cada uma por um número limitado de etapas. O tempo de execução de cada fase é O ( m + n ). Se o número de vértices antes de uma fase for , o número de vértices restantes depois de uma fase é no máximo . Portanto, no máximo as fases são necessárias, o que dá um tempo de execução linear para gráficos densos. ${\ displaystyle n '}$ ${\ displaystyle n '/ 2 ^ {m / n'}}$ ${\ displaystyle \ log ^ {*} {n}}$

Existem outros algoritmos que funcionam em tempo linear em gráficos densos.

Pesos inteiros

Se os pesos das arestas são inteiros representados em binário, então são conhecidos algoritmos determinísticos que resolvem o problema em O ( m + n ) operações inteiras. Se o problema pode ser resolvido deterministicamente para um gráfico geral no tempo linear por um algoritmo baseado em comparação permanece uma questão em aberto.

Árvores de decisão

Dado o grafo G onde os nós e arestas são fixos, mas os pesos são desconhecidos, é possível construir uma árvore de decisão binária (DT) para calcular o MST para qualquer permutação de pesos. Cada nó interno da DT contém uma comparação entre as duas bordas, por exemplo, "é o peso da aresta entre x e y maior do que o peso da aresta de entre W e Z ?". Os dois filhos do nó correspondem às duas respostas possíveis "sim" ou "não". Em cada folha do DT, há uma lista de arestas de G que correspondem a um MST. A complexidade do tempo de execução de uma DT é o maior número de consultas necessárias para encontrar o MST, que é apenas a profundidade da DT. A DT para um grafo G é chamado ideal se tem a menor profundidade de todos os DTs corretos para G .

Para cada inteiro r , é possível encontrar árvores de decisão ótimas para todos os gráficos em r vértices por busca de força bruta . Essa pesquisa prossegue em duas etapas.

A. Gerando todos os DTs potenciais

Existem diferentes gráficos em r vértices. ${\ displaystyle 2 ^ {r \ escolha 2}}$
Para cada gráfico, um MST sempre pode ser encontrado usando comparações r ( r -1), por exemplo, pelo algoritmo de Prim .
Conseqüentemente, a profundidade de um DT ideal é menor que . ${\ displaystyle r ^ {2}}$
Portanto, o número de nós internos em uma TD ótima é menor que . ${\ displaystyle 2 ^ {r ^ {2}}}$
Cada nó interno compara duas arestas. O número de arestas é no máximo, portanto o número diferente de comparações é no máximo . ${\ displaystyle r ^ {2}}$ ${\ displaystyle r ^ {4}}$
Assim, o número de potenciais DTS é inferior a: . ${\ displaystyle {(r ^ {4})} ^ {(2 ^ {r ^ {2}})} = r ^ {2 ^ {(r ^ {2} +2)}}}$

B. Identificando os TDs corretos Para verificar se um TD está correto, ele deve ser verificado em todas as permutações possíveis dos pesos das arestas.

O número de tais permutações é no máximo . ${\ displaystyle (r ^ {2})!}$
Para cada permutação, resolva o problema MST no gráfico fornecido usando qualquer algoritmo existente e compare o resultado com a resposta dada pelo DT.
O tempo de execução de qualquer algoritmo MST é no máximo , então o tempo total necessário para verificar todas as permutações é no máximo . ${\ displaystyle (r ^ {2})}$ ${\ displaystyle (r ^ {2} +1)!}$

Assim, o tempo total necessário para encontrar um óptimo DT para todos os gráficos com r vértices é: , o que é menos do que: . ${\ displaystyle 2 ^ {r \ escolha 2} \ cdot r ^ {2 ^ {(r ^ {2} +2)}} \ cdot (r ^ {2} +1)!}$ ${\ displaystyle 2 ^ {2 ^ {r ^ {2} + o (r)}}}$

Algoritmo ótimo

Seth Pettie e Vijaya Ramachandran encontraram um algoritmo de árvore geradora mínima com base em comparação determinística provavelmente ideal. A seguir está uma descrição simplificada do algoritmo.

Let , onde n é o número de vértices. Encontre todas as árvores de decisão ótimas em r vértices. Isso pode ser feito no tempo O ( n ) (consulte Árvores de decisão acima). ${\ displaystyle r = \ log \ log \ log n}$
Particione o gráfico para componentes com no máximo r vértices em cada componente. Esta partição usa um soft heap , que "corrompe" um pequeno número das bordas do gráfico.
Use as árvores de decisão ideais para encontrar um MST para o subgráfico não corrompido dentro de cada componente.
Contraia cada componente conectado estendido pelos MSTs a um único vértice e aplique qualquer algoritmo que funcione em gráficos densos no tempo O ( m ) para a contração do subgrafo não corrompido
Adicione de volta as arestas corrompidas à floresta resultante para formar um subgráfico com garantia de conter a árvore de abrangência mínima e menor por um fator constante do que o gráfico inicial. Aplique o algoritmo ideal recursivamente a este gráfico.

O tempo de execução de todas as etapas do algoritmo é O ( m ), exceto para a etapa de uso das árvores de decisão . O tempo de execução desta etapa é desconhecido, mas foi provado que é ótimo - nenhum algoritmo pode fazer melhor do que a árvore de decisão ótima. Assim, esse algoritmo tem a propriedade peculiar de ser provavelmente ótimo, embora sua complexidade de tempo de execução seja desconhecida .

Algoritmos paralelos e distribuídos

A pesquisa também considerou algoritmos paralelos para o problema de spanning tree mínimo. Com um número linear de processadores é possível resolver o problema a tempo. Bader & Cong (2006) demonstram um algoritmo que pode computar MSTs 5 vezes mais rápido em 8 processadores do que um algoritmo sequencial otimizado. ${\ displaystyle O (\ log n)}$

Outros algoritmos especializados foram projetados para calcular árvores de abrangência mínima de um gráfico tão grande que a maior parte deve ser armazenada em disco o tempo todo. Esses algoritmos de armazenamento externo , por exemplo, conforme descrito em "Engineering an External Memory Minimum Spanning Tree Algorithm" por Roman, Dementiev et al., Podem operar, segundo as afirmações dos autores, tão pouco quanto 2 a 5 vezes mais lento do que um tradicional in-memory algoritmo. Eles contam com algoritmos de classificação de armazenamento externo eficientes e técnicas de contração de gráfico para reduzir o tamanho do gráfico de forma eficiente.

O problema também pode ser abordado de forma distribuída . Se cada nó for considerado um computador e nenhum nó souber de nada, exceto seus próprios links conectados, ainda se pode calcular a árvore geradora mínima distribuída .

MST em gráficos completos

Alan M. Frieze mostrou que dado um gráfico completo em n vértices, com pesos de aresta que são variáveis aleatórias distribuídas de forma idêntica e independentes com função de distribuição satisfatória , então quando n se aproxima de + ∞ o peso esperado das abordagens MST , onde está a função zeta de Riemann ( mais especificamente é a constante de Apéry ). Frieze e Steele também provaram convergência em probabilidade. Svante Janson provou um teorema do limite central para o peso do MST. ${\ displaystyle F}$ ${\ displaystyle F '(0)> 0}$ ${\ displaystyle \ zeta (3) / F '(0)}$ ${\ displaystyle \ zeta}$ ${\ displaystyle \ zeta (3)}$

Para pesos aleatórios uniformes em , o tamanho exato esperado da árvore de abrangência mínima foi calculado para pequenos gráficos completos. ${\ displaystyle [0,1]}$

Vértices	Tamanho esperado	Tamanho estimado aproximado
2	1/2	0,5
3	3/4	0,75
4	31/35	0,8857143
5	893/924	0,9664502
6	278/273	1.0183151
7	30739/29172	1.053716
8	199462271/184848378	1.0790588
9	126510063932/115228853025	1.0979027

Formulários

Árvore de extensão mínima têm aplicações diretas na concepção das redes, incluindo as redes de computadores , redes de telecomunicações , redes de transporte , redes de abastecimento de água e redes elétricas (que eles foram inventados em primeiro lugar para, como mencionado acima). Eles são chamados como sub-rotinas em algoritmos para outros problemas, incluindo o algoritmo de Christofides para aproximar o problema do caixeiro viajante , aproximando o problema de corte mínimo multiterminal (que é equivalente no caso de terminal único ao problema de fluxo máximo ) e aproximando o correspondência perfeita ponderada de custo mínimo .

Outras aplicações práticas baseadas em árvores geradoras mínimas incluem:

Taxonomia .
Análise de cluster : agrupamento de pontos no plano, agrupamento de ligação única (um método de agrupamento hierárquico ), agrupamento teórico de gráfico e agrupamento de dados de expressão gênica .
Construção de árvores para transmissão em redes de computadores.
Registro e segmentação de imagens - consulte segmentação mínima baseada em árvore de abrangência .
Extração de características curvilíneas em visão computacional .
Reconhecimento de escrita manual de expressões matemáticas.
Projeto de circuito : implementação de multiplicações múltiplas constantes eficientes, como usado em filtros de resposta de impulso finito .
Regionalização das áreas sócio-geográficas, o agrupamento das áreas em regiões homogêneas e contíguas.
Comparando dados de ecotoxicologia .
Topológica observability em sistemas de energia.
Medindo a homogeneidade de materiais bidimensionais.
Controle de processo Minimax .
Árvores de abrangência mínima também podem ser usadas para descrever os mercados financeiros. Uma matriz de correlação pode ser criada calculando um coeficiente de correlação entre quaisquer duas ações. Esta matriz pode ser representada topologicamente como uma rede complexa e uma árvore de abrangência mínima pode ser construída para visualizar relacionamentos.

Problemas relacionados

Árvores Steiner mínimas de vértices de polígonos regulares com N = 3 a 8 lados. O menor comprimento de rede L para N > 5 é a circunferência menos um lado. Os quadrados representam pontos Steiner.

O problema de encontrar a árvore de Steiner de um subconjunto de vértices, ou seja, a árvore mínima que abrange o subconjunto dado, é conhecido como NP-Completo .

Um problema relacionado é a árvore geradora k -minimum ( k -MST), que é a árvore que abrange algum subconjunto de k vértices no gráfico com peso mínimo.

Um conjunto de k-menores árvores de abrangência é um subconjunto de k árvores de abrangência (de todas as árvores de abrangência possíveis) de forma que nenhuma árvore de abrangência fora do subconjunto tenha peso menor. (Observe que este problema não está relacionado à árvore de abrangência k- mínima.)

A árvore geradora mínima euclidiana é uma árvore geradora de um gráfico com pesos de aresta correspondentes à distância euclidiana entre vértices que são pontos no plano (ou espaço).

A árvore geradora retilínea mínima é uma árvore geradora de um gráfico com pesos de aresta correspondendo à distância retilínea entre vértices que são pontos no plano (ou espaço).

No modelo distribuído , onde cada nó é considerado um computador e nenhum nó conhece nada exceto seus próprios links conectados, pode-se considerar a árvore geradora mínima distribuída . A definição matemática do problema é a mesma, mas existem diferentes abordagens para uma solução.

A árvore geradora mínima capacitada é uma árvore que possui um nó marcado (origem ou raiz) e cada uma das subárvores anexadas ao nó não contém mais do que c nós. c é chamado de capacidade de árvore. Resolver CMST de maneira ideal é NP-difícil , mas boas heurísticas, como Esau-Williams e Sharma, produzem soluções próximas do ótimo em tempo polinomial.

A árvore geradora mínima com restrição de grau é uma árvore geradora mínima na qual cada vértice está conectado a não mais do que d outros vértices, para um determinado número d . O caso d = 2 é um caso especial do problema do caixeiro viajante , então a árvore geradora mínima com restrição de grau é NP-difícil em geral.

Para grafos direcionados , o problema de spanning tree mínimo é chamado de problema de Arborescência e pode ser resolvido em tempo quadrático usando o algoritmo Chu – Liu / Edmonds .

Uma árvore de abrangência máxima é uma árvore de abrangência com peso maior ou igual ao peso de todas as outras árvores de abrangência. Tal árvore pode ser encontrada com algoritmos como Prim ou Kruskal depois de multiplicar os pesos das arestas por -1 e resolver o problema MST no novo gráfico. Um caminho na árvore de abrangência máxima é o caminho mais largo no gráfico entre seus dois pontos finais: entre todos os caminhos possíveis, ele maximiza o peso da aresta de peso mínimo. Árvores de abrangência máxima encontram aplicações em algoritmos de análise para linguagens naturais e em algoritmos de treinamento para campos aleatórios condicionais .

O problema de MST dinâmico diz respeito à atualização de um MST calculado anteriormente após uma mudança de peso de aresta no gráfico original ou a inserção / exclusão de um vértice.

O problema da árvore de abrangência de rotulagem mínima é encontrar uma árvore de abrangência com menos tipos de rótulos se cada aresta em um gráfico estiver associada a um rótulo de um conjunto de rótulos finito em vez de um peso.

Uma aresta de gargalo é a aresta de maior peso em uma árvore estendida. Uma árvore estendida é uma árvore estendida de gargalo mínimo (ou MBST ) se o gráfico não contiver uma árvore estendida com um peso de borda de gargalo menor. Um MST é necessariamente um MBST (comprovável pela propriedade cut ), mas um MBST não é necessariamente um MST.

Referências

Leitura adicional

Otakar Boruvka on Minimum Spanning Tree Problem (tradução de ambos os documentos de 1926, comentários, história) (2000) Jaroslav Nešetřil , Eva Milková, Helena Nesetrilová. (A seção 7 fornece seu algoritmo, que parece um cruzamento entre o de Prim e o de Kruskal.)
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein . Introdução aos algoritmos , segunda edição. MIT Press e McGraw-Hill, 2001. ISBN 0-262-03293-7 . Capítulo 23: Minimum Spanning Trees, pp. 561–579.
Eisner, Jason (1997). Algoritmos de última geração para árvores de abrangência mínima: uma discussão tutorial . Manuscrito, Universidade da Pensilvânia, abril. 78 pp.
Kromkowski, John David. "Still Unmelted after All These Years", in Annual Editions, Race and Ethnic Relations, 17 / e (2009 McGraw Hill) (Usando a árvore de abrangência mínima como método de análise demográfica da diversidade étnica nos Estados Unidos).

Languages

In other projects