|
Árvore de extensão mínima Dado um grafo não orientado conectado, uma árvore de extensão deste grafo é um subgrafo o qual é uma árvore que conecta todos os vértices. Um único grafo pode ter diferentes árvores de extensão. Nós podemos assinalar um peso a cada aresta, que é um número que representa quão desfavorável ela é, e atribuir um peso a árvore de extensão calculado pela soma dos pesos das arestas que a compõem. Uma árvore de extensão mínima (também conhecida como árvore de extensão de peso mínimo ou árvore geradora mínima) é então uma árvore de extensão com peso menor ou igual a cada uma das outras árvores de extensão possíveis. Generalizando mais, qualquer grafo não direcional (não necessariamente conectado) tem uma floresta de árvores mínimas, que é uma união de árvores de extensão mínimas de cada uma de suas componentes conexas. Um exemplo de uso de uma árvore de extensão mínima seria a instalação de fibras óticas num campus de uma faculdade. Cada trecho de fibra ótica entre os prédios possui um custo associado (isto é, o custo da fibra, somado ao custo da instalação da fibra, mão de obra, etc). Com esses dados em mãos (os prédios e os custos de cada trecho de fibra ótica entre todos os prédios), podemos construir uma árvore de extensão que nos diria um jeito de conectarmos todos os prédios sem redundância. Uma árvore geradora mínima desse grafo nos daria uma árvore com o menor custo para fazer essa ligação. PropriedadesPossível MultiplicidadePodem existir várias árvores de extensão mínima com o mesmo peso; Em particular, em um grafo não ponderado (onde todos os pesos são iguais), toda árvore de extensão é mínima. UnicidadeSe cada aresta tem um peso distinto, então existirá somente uma árvore de extensão mínima distinta. Isso pode ser provado por indução ou por contradição. Isso é verdade em muitas situações realísticas, como no exemplo do cabeamento do campus, dado acima. É muito difícil que tenhamos duas possibilidades de cabeamento com exatamente o mesmo custo. Isso pode ser generalizado para florestas de árvores mínimas. Subgrafo de custo mínimoSe todos os pesos são não-negativos, então uma árvore de extensão mínima é o subgrafo de custo mínimo conectando todos os vértices, já que qualquer subgrafo contendo cíclos vai possuir um peso total maior. Propriedade dos ciclosPara qualquer ciclo C no grafo, se o peso de uma aresta e de C é maior do que os pesos das outras arestas de C, então essa aresta não pode pertencer a uma árvore de extensão mínima. Propriedade do cortePara qualquer corte C no grafo, se o peso de uma aresta e de C é menor do que os pesos de outras arestas C, então essa aresta pertence a todas as árvores de extensão mínima possíveis do grafo. AlgoritmosO primeiro algoritmo a encontrar uma árvore de extensão mínima foi desenvolvido pelo cientista checo Otakar Borůvka em 1926 (veja algoritmo de Boruvka). Seu propósito era fornecer uma cobertura elétrica eficiente na área rural da cidade de Morávia do Sul. Existem hoje dois algoritmos comummente usados, o algoritmo de Prim e o algoritmo de Kruskal. Todos são algoritmos gulosos que rodam em tempo polinomial, então o problema de encontrar tais árvores pertence a classe de complexidade P. O mais rápido algoritmo de árvore mínima de extensão foi desenvolvido por Bernard Chazelle, e foi baseado no algoritmo de Borůvka. Ele roda em um tempo de O(m α(m,n)), onde m é o número de arestas, n refere-se ao número de vértices e α é a clássica função inversa da função de Ackermann. A função α cresce de forma extremamente lenta, então para todos os propósitos práticos ele pode ser considerado uma constante não maior que quatro; portanto o algoritmo de Chazelle chega muito perto de um tempo O(m). Qual é o algoritmo mais rápido possível para este problema? Isto é um dos mais antigos problemas em aberto na ciência da computação. Há claramente um limite linear inferior, já que é necessário examinar todas as arestas ao menos uma vez. Ligações externas
|
