Árvore de abrangência mínima

Da Wikipédia, a enciclopédia livre
Ir para navegação Pular para pesquisar

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

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

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 extensa for that graph would be a subset of those paths that has no cycles but still connects every house; there might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost, representing the least expensive path for laying the cable.

Properties

Possible multiplicity

If there are n vertices in the graph, then each spanning tree has n − 1 edges.

This figure shows there may be more than one minimum spanning tree in a graph. In the figure, the two trees below the graph are two possibilities of minimum spanning tree of the given graph.

There may be several minimum spanning trees of the same weight; in particular, if all the edge weights of a given graph are the same, then every spanning tree of that graph is minimum.

Uniqueness

If each edge has a distinct weight then there will be only one, unique minimum spanning tree. This is true in many realistic situations, such as the telecommunications company example above, where it's unlikely any two paths have exactly the same cost. This generalizes to spanning forests as well.

Proof:

  1. Assume the contrary, that there are two different MSTs A and B.
  2. Since A and B differ despite containing the same nodes, there is at least one edge that belongs to one but not the other. Among such edges, let e1 be the one with least weight; this choice is unique because the edge weights are all distinct. Without loss of generality, assume e1 is in A.
  3. As B is an MST, {e1} B must contain a cycle C with e1.
  4. As a tree, A contains no cycles, therefore C must have an edge e2 that is not in A.
  5. Since e1 was chosen as the unique lowest-weight edge among those belonging to exactly one of A and B, the weight of e2 must be greater than the weight of e1.
  6. As e1 and e2 are part of the cycle C, replacing e2 with e1 in B therefore yields a spanning tree with a smaller weight.
  7. This contradicts the assumption that B is an MST.

More generally, if the edge weights are not all distinct then only the (multi-)set of weights in minimum spanning trees is certain to be unique; it is the same for all minimum spanning trees.[1]

Minimum-cost subgraph

If the weights are positive, then a minimum spanning tree is in fact a minimum-cost subgraph connecting all vertices, since subgraphs containing cycles necessarily have more total weight.[citation needed]

Cycle property

For any cycle C in the graph, if the weight of an edge e of C is larger than the individual weights of all other edges of C, then this edge cannot belong to an MST.

Proof: Assume the contrary, i.e. that e belongs to an MST T1. Then deleting e will break T1 into two subtrees with the two ends of e in different subtrees. The remainder of C reconnects the subtrees, hence there is an edge f of C with ends in different subtrees, i.e., it reconnects the subtrees into a tree T2 with weight less than that of T1, because the weight of f is less than the weight of e.

Cut property

This figure shows the cut property of MSTs. T is the only MST of the given graph. If S = {A,B,D,E}, thus V-S = {C,F}, then there are 3 possibilities of the edge across the cut(S,V-S), they are edges BC, EC, EF of the original graph. Then, e is one of the minimum-weight-edge for the cut, therefore S ∪ {e} is part of the MST T.

For any cut C of the graph, if the weight of an edge e in the cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph.

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.

Borda 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. [2]

Algoritmos

In all of the algorithms below, m is the number of edges in the graph and n is the number of vertices.

Classic algorithms

The first algorithm for finding a minimum spanning tree was developed by Czech scientist Otakar Borůvka in 1926 (see Borůvka's algorithm). Its purpose was an efficient electrical coverage of Moravia. The algorithm proceeds in a sequence of stages. In each stage, called Boruvka step, it identifies a forest F consisting of the minimum-weight edge incident to each vertex in the graph G, then forms the graph as the input to the next step. Here denotes the graph derived from G by contracting edges in F (by the Cut property, these edges belong to the MST). Each Boruvka step takes linear time. Since the number of vertices is reduced by at least half in each step, Boruvka's algorithm takes O(m log n) time.[2]

A second algorithm is Prim's algorithm, which was invented by Vojtěch Jarník in 1930 and rediscovered by Prim in 1957 and Dijkstra in 1959. Basically, it grows the MST (T) one edge at a time. Initially, T contains an arbitrary vertex. In each step, T is augmented with a least-weight edge (x,y) such that x is in T and y is not yet in T. By the Cut property, all edges added to T are in the MST. Its run-time is either O(m log n) or O(m + n log n), depending on the data-structures used.

A third algorithm commonly in use is Kruskal's algorithm, which also takes O(m log n) time.

A fourth algorithm, not as commonly used, is the reverse-delete algorithm, which is the reverse of Kruskal's algorithm. Its runtime is O(m log n (log log n)3).

All four of these are greedy algorithms. Since they run in polynomial time, the problem of finding such trees is in FP, and related decision problems such as determining whether a particular edge is in the MST or determining if the minimum total weight exceeds a certain value are in P.

Faster algorithms

Several researchers have tried to find more computationally-efficient algorithms.

In a comparison model, in which the only allowed operations on edge weights are pairwise comparisons, Karger, Klein & Tarjan (1995) found a linear time randomized algorithm based on a combination of Borůvka's algorithm and the reverse-delete algorithm.[3][4]

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. [5] [6] 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 linear de tempo em casos especiais

Gráficos densas

If the graph is dense (i.e. m/n ≥ log log log n), then a deterministic algorithm by Fredman and Tarjan finds the MST in time O(m).[7] The algorithm executes a number of phases. Each phase executes Prim's algorithm many times, each for a limited number of steps. The run-time of each phase is O(m+n). If the number of vertices before a phase is , the number of vertices remaining after a phase is at most . Hence, at most phases are needed, which gives a linear run-time for dense graphs.[2]

There are other algorithms that work in linear time on dense graphs.[5][8]

Integer weights

If the edge weights are integers represented in binary, then deterministic algorithms are known that solve the problem in O(m + n) integer operations.[9] Whether the problem can be solved deterministically for a general graph in linear time by a comparison-based algorithm remains an open question.

Decision trees

Given graph G where the nodes and edges are fixed but the weights are unknown, it is possible to construct a binary decision tree (DT) for calculating the MST for any permutation of weights. Each internal node of the DT contains a comparison between two edges, e.g. "Is the weight of the edge between x and y larger than the weight of the edge between w and z?". The two children of the node correspond to the two possible answers "yes" or "no". In each leaf of the DT, there is a list of edges from G that correspond to an MST. The runtime complexity of a DT is the largest number of queries required to find the MST, which is just the depth of the DT. A DT for a graph G is called optimal if it has the smallest depth of all correct DTs for G.

For every integer r, it is possible to find optimal decision trees for all graphs on r vertices by brute-force search. This search proceeds in two steps.

A. Generating all potential DTs

  • There are different graphs on r vertices.
  • For each graph, an MST can always be found using r(r-1) comparisons, e.g. by Prim's algorithm.
  • Hence, the depth of an optimal DT is less than .
  • Hence, the number of internal nodes in an optimal DT is less than .
  • Every internal node compares two edges. The number of edges is at most so the different number of comparisons is at most .
  • Hence, the number of potential DTs is less than: .

B. Identifying the correct DTs To check if a DT is correct, it should be checked on all possible permutations of the edge weights.

  • The number of such permutations is at most .
  • 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 .

Portanto, o tempo total necessário para encontrar um DT ideal para todos os gráficos com r vértices é:, que é menor que: . [2]

Algoritmo ótimo

Seth Pettie and Vijaya Ramachandran have found a provably optimal deterministic comparison-based minimum spanning tree algorithm.[2] The following is a simplified description of the algorithm.

  1. Let , where n is the number of vertices. Find all optimal decision trees on r vertices. This can be done in time O(n) (see Decision trees above).
  2. Partition the graph to components with at most r vertices in each component. This partition uses a soft heap, which "corrupts" a small number of the edges of the graph.
  3. Use the optimal decision trees to find an MST for the uncorrupted subgraph within each component.
  4. Contract each connected component spanned by the MSTs to a single vertex, and apply any algorithm which works on dense graphs in time O(m) to the contraction of the uncorrupted subgraph
  5. Add back the corrupted edges to the resulting forest to form a subgraph guaranteed to contain the minimum spanning tree, and smaller by a constant factor than the starting graph. Apply the optimal algorithm recursively to this graph.

The runtime of all steps in the algorithm is O(m), except for the step of using the decision trees. The runtime of this step is unknown, but it has been proved that it is optimal - no algorithm can do better than the optimal decision tree. Thus, this algorithm has the peculiar property that it is provably optimal although its runtime complexity is unknown.

Parallel and distributed algorithms

Research has also considered parallel algorithms for the minimum spanning tree problem. With a linear number of processors it is possible to solve the problem in time.[10][11] Bader & Cong (2006) demonstrate an algorithm that can compute MSTs 5 times faster on 8 processors than an optimized sequential algorithm.[12]

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., [13] podem operar, segundo as afirmações dos autores, tão pouco quanto 2 a 5 vezes mais lento do que um tradicional algoritmo na memória. 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ório , então, conforme n se aproxima de + ∞, o peso esperado do MST se aproxima, Onde is the Riemann zeta function (more specifically is Apéry's constant). Frieze and Steele also proved convergence in probability. Svante Janson proved a central limit theorem for weight of the MST.

For uniform random weights in , the exact expected size of the minimum spanning tree has been computed for small complete graphs.[14]

Vertices Expected size Approximate expected size
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

Applications

Minimum spanning trees have direct applications in the design of networks, including computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids (which they were first invented for, as mentioned above).[15] They are invoked as subroutines in algorithms for other problems, including the Christofides algorithm for approximating the traveling salesman problem,[16] approximating the multi-terminal minimum cut problem (which is equivalent in the single-terminal case to the maximum flow problem),[17] e aproximando a correspondência perfeita ponderada de custo mínimo . [18]

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

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 . [37]

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. [38] [39] [40] (Observe que este problema não está relacionado à árvore geradora 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 ótima é NP-difícil , [41] 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. [42] Árvores de abrangência máxima encontram aplicações em algoritmos de análise para linguagens naturais [43] 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. [44] [45] [46]

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. [47]

Uma borda de gargalo é a borda com maior peso em uma árvore geradora. 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. [48] [49]

Referências

  1. ^ "As árvores abrangentes mínimas de um gráfico ponderado têm o mesmo número de arestas com um determinado peso?" . cs.stackexchange.com . Obtido em 4 de abril de 2018 .
  2. ^ a b c d e Pettie, Seth; Ramachandran, Vijaya (2002), "An ótimo algoritmo de árvore geradora mínima" (PDF) , Journal of the Association for Computing Machinery , 49 (1): 16–34, doi : 10.1145 / 505241.505243 , MR 2148431 , S2CID 5362916   .
  3. ^ Karger, David R .; Klein, Philip N .; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum spanning trees", Journal of the Association for Computing Machinery , 42 (2): 321-328, doi : 10.1145 / 201019.201022 , MR 1409738 , S2CID 832583  
  4. ^ Pettie, Seth; Ramachandran, Vijaya (2002), "Minimizando a aleatoriedade na árvore de abrangência mínima, conectividade paralela e algoritmos de definição máxima", Proc. 13º Simpósio ACM-SIAM sobre Algoritmos Discretos (SODA '02) , São Francisco, Califórnia, pp. 713-722.
  5. ^ a b Chazelle, Bernard (2000), "A minimum spanning tree algoritmo with inverse-Ackermann type complex", Journal of the Association for Computing Machinery , 47 (6): 1028-1047, doi : 10.1145 / 355541.355562 , MR 1866456 , S2CID 6276962  .
  6. ^ Chazelle, Bernard (2000), "A pilha flexível: uma fila de prioridade aproximada com taxa de erro ideal" (PDF) , Journal of the Association for Computing Machinery , 47 (6): 1012–1027, doi : 10.1145 / 355541.355554 , MR 1866455 , S2CID 12556140   .
  7. ^ Fredman, ML; Tarjan, RE (1987). "Fibonacci heaps e seus usos em algoritmos de otimização de rede aprimorados". Jornal do ACM . 34 (3): 596. doi : 10.1145 / 28869.28874 . S2CID 7904683 . 
  8. ^ Gabow, HN ; Galil, Z .; Spencer, T .; Tarjan, RE (1986). "Algoritmos eficientes para encontrar árvores geradoras mínimas em gráficos direcionados e não direcionados". Combinatorica . 6 (2): 109. doi : 10.1007 / bf02579168 . S2CID 35618095 . 
  9. ^ Fredman, ML ; Willard, DE (1994), "Trans-dichotomous algoritms for minimum spanning trees and shortest path", Journal of Computer and System Sciences , 48 (3): 533–551, doi : 10.1016 / S0022-0000 (05) 80064-9 , MR 1279413 .
  10. ^ Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), "Encadeamentos simultâneos e algoritmo de árvores de abrangência mínima paralela ideal", Journal of the Association for Computing Machinery , 48 (2): 297-323, doi : 10.1145 / 375827.375847 , MR 1868718 , S2CID 1778676  .
  11. ^ Pettie, Seth; Ramachandran, Vijaya (2002), "Um algoritmo paralelo otimizado de trabalho aleatório para encontrar uma floresta de abrangência mínima" (PDF) , SIAM Journal on Computing , 31 (6): 1879–1895, doi : 10.1137 / S0097539700371065 , MR 1954882  .
  12. ^ Bader, David A .; Cong, Guojing (2006), "algoritmos de memória compartilhada rápida para calcular a floresta de abrangência mínima de gráficos esparsos", Journal of Parallel and Distributed Computing , 66 (11): 1366–1378, doi : 10.1016 / j.jpdc.2006.06. 001 , S2CID 2004627 .
  13. ^ Dementiev, romano; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F. (2004), "Engineering an external memory minimum spanning tree algoritmo", Proc. IFIP 18º Congresso Mundial de Computação, TC1 3ª Conferência Internacional sobre Ciência da Computação Teórica (TCS2004) (PDF) , pp. 195–208 .
  14. ^ Steele, J. Michael (2002), "Minimal spanning trees for graphs with random edge lengths", Mathematics and computer science, II (Versailles, 2002) , Trends Math., Basel: Birkhäuser, pp. 223-245, MR 1940139 
  15. ^ Graham, RL ; Hell, Pavol (1985), "On the history of the minimum spanning tree problem", Annals of the History of Computing , 7 (1): 43-57, doi : 10.1109 / MAHC.1985.10011 , MR 0783327 , S2CID 10555375  
  16. ^ Nicos Christofides , Análise do pior caso de uma nova heurística para o problema do caixeiro viajante , Relatório 388, Escola de Graduação em Administração Industrial, CMU, 1976.
  17. ^ Dahlhaus, E .; Johnson, DS ; Papadimitriou, CH ; Seymour, PD ; Yannakakis, M. (agosto de 1994). "A complexidade dos cortes multiterminais" (PDF) . SIAM Journal on Computing . 23 (4): 864–894. doi : 10.1137 / S0097539792225297 . Arquivado do original (PDF) em 24 de agosto de 2004 . Página visitada em 17 de dezembro de 2012 .
  18. ^ Supowit, Kenneth J .; Plaisted, David A .; Reingold, Edward M. (1980). Heurísticas para correspondência perfeita ponderada . 12º Simpósio Anual da ACM em Teoria da Computação (STOC '80). Nova York, NY, EUA: ACM. pp. 398–419. doi : 10.1145 / 800141.804689 .
  19. ^ Sneath, PHA (1 de agosto de 1957). "A aplicação dos computadores à taxonomia" . Journal of General Microbiology . 17 (1): 201–226. doi : 10.1099 / 00221287-17-1-201 . PMID 13475686 . 
  20. ^ Asano, T .; Bhattacharya, B .; Keil, M .; Yao, F. (1988). Algoritmos de agrupamento baseados em árvores de abrangência mínima e máxima . Quarto Simpósio Anual de Geometria Computacional (SCG '88). 1 . pp. 252-257. doi : 10.1145 / 73393.73419 .
  21. ^ Gower, JC; Ross, GJS (1969). "Mínimo Spanning Trees and Single Linkage Cluster Analysis". Journal of the Royal Statistical Society . C (Estatísticas Aplicadas). 18 (1): 54–64. doi : 10.2307 / 2346439 . JSTOR 2346439 . 
  22. ^ Päivinen, Niina (1 de maio de 2005). "Clustering com uma árvore de abrangência mínima de estrutura semelhante a escala livre". Cartas de reconhecimento de padrões . 26 (7): 921–930. doi : 10.1016 / j.patrec.2004.09.039 .
  23. ^ Xu, Y .; Olman, V .; Xu, D. (1 de abril de 2002). "Agrupamento de dados de expressão gênica usando uma abordagem da teoria dos gráficos: uma aplicação de árvores geradoras mínimas" . Bioinformática . 18 (4): 536–545. doi : 10.1093 / bioinformática / 18.4.536 . PMID 12016051 . 
  24. ^ Dalal, Yogen K .; Metcalfe, Robert M. (1 de dezembro de 1978). "Encaminhamento de caminho reverso de pacotes de broadcast". Comunicações da ACM . 21 (12): 1040–1048. doi : 10.1145 / 359657.359665 . S2CID 5638057 . 
  25. ^ Ma, B .; Hero, A .; Gorman, J .; Michel, O. (2000). Registro de imagem com algoritmo de spanning tree mínimo (PDF) . Conferência Internacional sobre Processamento de Imagens. 1 . pp. 481–484. doi : 10.1109 / ICIP.2000.901000 .
  26. ^ P. Felzenszwalb, D. Huttenlocher: Efficient Graph-Based Image Segmentation. IJCV 59 (2) (setembro de 2004)
  27. ^ Suk, Minsoo; Song, Ohyoung (1 de junho de 1984). "Extração de características curvilíneas usando árvores geradoras mínimas". Visão computacional, gráficos e processamento de imagens . 26 (3): 400–411. doi : 10.1016 / 0734-189X (84) 90221-4 .
  28. ^ Tapia, Ernesto; Rojas, Raúl (2004). "Reconhecimento de expressões matemáticas manuscritas on-line usando uma construção de árvore de abrangência mínima e dominância de símbolos" (PDF) . Reconhecimento de gráficos. Avanços e perspectivas recentes . Notas de aula em Ciência da Computação. 3088 . Berlin Heidelberg: Springer-Verlag. pp. 329–340. ISBN  978-3540224785.
  29. ^ Ohlsson, H. (2004). Implementação de filtros FIR de baixa complexidade usando uma árvore de abrangência mínima . 12ª Conferência Eletrotécnica do Mediterrâneo IEEE (MELECON 2004). 1 . pp. 261–264. doi : 10.1109 / MELCON.2004.1346826 .
  30. ^ Assunção, RM; MC Neves; G. Câmara; C. Da Costa Freitas (2006). “Técnicas de regionalização eficientes para unidades geográficas socioeconômicas usando árvores de abrangência mínima” . International Journal of Geographical Information Science . 20 (7): 797–811. doi : 10.1080 / 13658810600665111 . S2CID 2530748 . 
  31. ^ Devillers, J .; Dore, JC (1 de abril de 1989). "Potência heurística do método de árvore geradora mínima (MST) em toxicologia". Ecotoxicologia e Segurança Ambiental . 17 (2): 227–235. doi : 10.1016 / 0147-6513 (89) 90042-0 . PMID 2737116 . 
  32. ^ Mori, H .; Tsuzuki, S. (1 de maio de 1991). "Um método rápido para análise de observabilidade topológica usando uma técnica de spanning tree mínima". Transações IEEE em sistemas de energia . 6 (2): 491–500. Bibcode : 1991ITPSy ... 6..491M . doi : 10.1109 / 59.76691 .
  33. ^ Filliben, James J.; Kafadar, Karen; Shier, Douglas R. (1 January 1983). "Testing for homogeneity of two-dimensional surfaces". Mathematical Modelling. 4 (2): 167–189. doi:10.1016/0270-0255(83)90026-X.
  34. ^ Kalaba, Robert E. (1963), Graph Theory and Automatic Control (PDF)
  35. ^ Mantegna, R. N. (1999). Hierarchical structure in financial markets. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193-197.
  36. ^ Djauhari, M., & Gan, S. (2015). Problema de otimalidade da topologia da rede na análise do mercado de ações . Physica A: Statistical Mechanics and Its Applications, 419, 108-114.
  37. ^ Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman , ISBN 0-7167-1045-5. ND12
  38. ^ Gabow, Harold N. (1977), "Dois algoritmos para gerar árvores de abrangência ponderada em ordem", SIAM Journal on Computing , 6 (1): 139-150, doi : 10.1137 / 0206011 , MR 0441784 .
  39. ^ Eppstein, David (1992), "Finding the k smallest spanning trees", BIT , 32 (2): 237–248, doi : 10.1007 / BF01994879 , MR 1172188 , S2CID 121160520  .
  40. ^ Frederickson, Greg N. (1997), "Ambivalent data structure for dynamic 2-edge- connect and k smallest spanning trees" , SIAM Journal on Computing , 26 (2): 484-538, doi : 10.1137 / S0097539792226825 , MR 1438526 .
  41. ^ Jothi, Raja; Raghavachari, Balaji (2005), "Approximation Algorithms for the Capacited Minimum Spanning Tree Problem and Its Variants in Network Design", ACM Trans. Algoritmos , 1 (2): 265–282, doi : 10.1145 / 1103963.1103967 , S2CID 8302085 
  42. ^ Hu, TC (1961), "The maximum capacity route problem", Operations Research , 9 (6): 898-900, doi : 10.1287 / opre.9.6.898 , JSTOR 167055 .
  43. ^ McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, janeiro (2005). "Análise de dependência não projetiva usando algoritmos de árvore de abrangência" (PDF) . Proc. HLT / EMNLP .
  44. ^ Spira, PM; Pan, A. (1975), "On find and updates spanning trees and shortest path" (PDF) , SIAM Journal on Computing , 4 (3): 375-380, doi : 10.1137 / 0204032 , MR 0378466  .
  45. ^ Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), "Poly-logarithmic deterministic totalmente dynamic algorítmos para conectividade, árvore de abrangência mínima, 2-edge e biconnectivity", Journal of the Association for Computing Machinery , 48 (4): 723-760, doi : 10.1145 /502090.502095 , MR 2144928 , S2CID 7273552  .
  46. ^ Chin, F .; Houck, D. (1978), "Algorithms for update minimal spanning trees", Journal of Computer and System Sciences , 16 (3): 333–344, doi : 10.1016 / 0022-0000 (78) 90022-3.
  47. ^ Chang, RS; Leu, SJ (1997), "The minimum labeling spanning trees", Information Processing Letters , 63 (5): 277-282, doi : 10.1016 / s0020-0190 (97) 00127-0.
  48. ^ "Tudo sobre Bottleneck Spanning Tree" . flashing-thoughts.blogspot.ru . Obtido em 4 de abril de 2018 .
  49. ^ http://pages.cpsc.ucalgary.ca/~dcatalin/413/t4.pdf

Outras leituras

Ligações externas