b'\n_START_ARTICLE_\n\xc3\x81rvore de extens\xc3\xa3o m\xc3\xadnima\n_START_PARAGRAPH_\nDado um grafo n\xc3\xa3o orientado conectado, uma \xc3\xa1rvore de extens\xc3\xa3o deste grafo \xc3\xa9 um subgrafo o qual \xc3\xa9 uma \xc3\xa1rvore que conecta todos os v\xc3\xa9rtices. Um \xc3\xbanico grafo pode ter diferentes \xc3\xa1rvores de extens\xc3\xa3o. N\xc3\xb3s podemos assinalar um peso a cada aresta, que \xc3\xa9 um n\xc3\xbamero que representa qu\xc3\xa3o desfavor\xc3\xa1vel ela \xc3\xa9, e atribuir um peso a \xc3\xa1rvore de extens\xc3\xa3o calculado pela soma dos pesos das arestas que a comp\xc3\xb5em. Uma \xc3\xa1rvore de extens\xc3\xa3o m\xc3\xadnima (tamb\xc3\xa9m conhecida como \xc3\xa1rvore de extens\xc3\xa3o de peso m\xc3\xadnimo ou \xc3\xa1rvore geradora m\xc3\xadnima) \xc3\xa9 ent\xc3\xa3o uma \xc3\xa1rvore de extens\xc3\xa3o com peso menor ou igual a cada uma das outras \xc3\xa1rvores de extens\xc3\xa3o poss\xc3\xadveis. Generalizando mais, qualquer grafo n\xc3\xa3o direcional (n\xc3\xa3o necessariamente conectado) tem uma floresta de \xc3\xa1rvores m\xc3\xadnimas, que \xc3\xa9 uma uni\xc3\xa3o de \xc3\xa1rvores de extens\xc3\xa3o m\xc3\xadnimas de cada uma de suas componentes conexas._NEWLINE_Um exemplo de uso de uma \xc3\xa1rvore de extens\xc3\xa3o m\xc3\xadnima seria a instala\xc3\xa7\xc3\xa3o de fibras \xc3\xb3ticas num campus de uma faculdade. Cada trecho de fibra \xc3\xb3tica entre os pr\xc3\xa9dios possui um custo associado (isto \xc3\xa9, o custo da fibra, somado ao custo da instala\xc3\xa7\xc3\xa3o da fibra, m\xc3\xa3o de obra, etc). Com esses dados em m\xc3\xa3os (os pr\xc3\xa9dios e os custos de cada trecho de fibra \xc3\xb3tica entre todos os pr\xc3\xa9dios), podemos construir uma \xc3\xa1rvore de extens\xc3\xa3o que nos diria um jeito de conectarmos todos os pr\xc3\xa9dios sem redund\xc3\xa2ncia. Uma \xc3\xa1rvore geradora m\xc3\xadnima desse grafo nos daria uma \xc3\xa1rvore com o menor custo para fazer essa liga\xc3\xa7\xc3\xa3o.\n_START_SECTION_\nPoss\xc3\xadvel Multiplicidade\n_START_PARAGRAPH_\nPodem existir v\xc3\xa1rias \xc3\xa1rvores de extens\xc3\xa3o m\xc3\xadnima com o mesmo peso; Em particular, em um grafo n\xc3\xa3o ponderado (onde todos os pesos s\xc3\xa3o iguais), toda \xc3\xa1rvore de extens\xc3\xa3o \xc3\xa9 m\xc3\xadnima.\n_START_SECTION_\nUnicidade\n_START_PARAGRAPH_\nSe cada aresta tem um peso distinto, ent\xc3\xa3o existir\xc3\xa1 somente uma \xc3\xa1rvore de extens\xc3\xa3o m\xc3\xadnima distinta. Isso pode ser provado por indu\xc3\xa7\xc3\xa3o ou por contradi\xc3\xa7\xc3\xa3o._NEWLINE_Isso \xc3\xa9 verdade em muitas situa\xc3\xa7\xc3\xb5es real\xc3\xadsticas, como no exemplo do cabeamento do campus, dado acima. \xc3\x89 muito dif\xc3\xadcil que tenhamos duas possibilidades de cabeamento com exatamente o mesmo custo. Isso pode ser generalizado para florestas de \xc3\xa1rvores m\xc3\xadnimas.\n_START_SECTION_\nSubgrafo de custo m\xc3\xadnimo\n_START_PARAGRAPH_\nSe todos os pesos s\xc3\xa3o n\xc3\xa3o-negativos, ent\xc3\xa3o uma \xc3\xa1rvore de extens\xc3\xa3o m\xc3\xadnima \xc3\xa9 o subgrafo de custo m\xc3\xadnimo conectando todos os v\xc3\xa9rtices, j\xc3\xa1 que qualquer subgrafo contendo c\xc3\xadclos vai possuir um peso total maior.\n_START_SECTION_\nPropriedade dos ciclos\n_START_PARAGRAPH_\nPara qualquer ciclo C no grafo, se o peso de uma aresta e de C \xc3\xa9 maior do que os pesos das outras arestas de C, ent\xc3\xa3o essa aresta n\xc3\xa3o pode pertencer a uma \xc3\xa1rvore de extens\xc3\xa3o m\xc3\xadnima.\n_START_SECTION_\nPropriedade do corte\n_START_PARAGRAPH_\nPara qualquer corte C no grafo, se o peso de uma aresta e de C \xc3\xa9 menor do que os pesos de outras arestas C, ent\xc3\xa3o essa aresta pertence a todas as \xc3\xa1rvores de extens\xc3\xa3o m\xc3\xadnima poss\xc3\xadveis do grafo.\n_START_SECTION_\nAlgoritmos\n_START_PARAGRAPH_\nO primeiro algoritmo a encontrar uma \xc3\xa1rvore de extens\xc3\xa3o m\xc3\xadnima foi desenvolvido pelo cientista checo Otakar Bor\xc5\xafvka em 1926 (veja algoritmo de Boruvka). Seu prop\xc3\xb3sito era fornecer uma cobertura el\xc3\xa9trica eficiente na \xc3\xa1rea rural da cidade de Mor\xc3\xa1via do Sul.  Existem hoje dois algoritmos comummente usados, o algoritmo de Prim e o algoritmo de Kruskal. Todos s\xc3\xa3o algoritmos gulosos que rodam em tempo polinomial, ent\xc3\xa3o o problema de encontrar tais \xc3\xa1rvores pertence a classe de complexidade P._NEWLINE_O mais r\xc3\xa1pido algoritmo de \xc3\xa1rvore m\xc3\xadnima de extens\xc3\xa3o foi desenvolvido por Bernard Chazelle, e foi baseado no algoritmo de  Bor\xc5\xafvka. Ele roda em um tempo de O(m\xc2\xa0\xce\xb1(m,n)), onde m \xc3\xa9 o n\xc3\xbamero de arestas, n refere-se ao n\xc3\xbamero de v\xc3\xa9rtices e \xce\xb1 \xc3\xa9 a cl\xc3\xa1ssica fun\xc3\xa7\xc3\xa3o inversa da fun\xc3\xa7\xc3\xa3o de Ackermann. A fun\xc3\xa7\xc3\xa3o \xce\xb1 cresce de forma extremamente lenta, ent\xc3\xa3o para todos os prop\xc3\xb3sitos pr\xc3\xa1ticos ele pode ser considerado uma constante n\xc3\xa3o maior que quatro; portanto o algoritmo de Chazelle chega muito perto de um tempo O(m)._NEWLINE_Qual \xc3\xa9 o algoritmo mais r\xc3\xa1pido poss\xc3\xadvel para este problema? Isto \xc3\xa9 um dos mais antigos problemas em aberto na ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o. H\xc3\xa1 claramente um limite linear inferior, j\xc3\xa1 que \xc3\xa9 necess\xc3\xa1rio examinar todas as arestas ao menos uma vez.'