Atividade 9: A Cidade Enlameada — Árvores Geradoras Mínimas

Apresentação

Nossa sociedade é conectada por muitas redes: redes telefônicas, redes de abastecimento, redes de computadores e redes rodoviárias. Para uma determinada rede, há geralmente algumas escolhas sobre onde estradas, cabos ou ligações de rádio podem ser colocados. Temos de encontrar formas eficientes de conectar esses objetos a uma rede.

Disciplinas e conteúdos relacionados

Habilidades

Nível de Ensino

Material

Cada estudante precisará de:

A Cidade Enlameada

Introdução

Esta atividade lhe mostrará como os computadores são usados para encontrar as melhores soluções para os problemas da vida real tais como conectar linhas elétricas entre casas. Os estudantes devem usar a folha de atividade que explica o problema da “Cidade Enlameada”.

Discussão

Compartilhe as soluções encontradas pelos estudantes. Quais estratégias foram utilizadas?

Uma boa estratégia para encontrar a melhor solução é começar com um mapa vazio e, gradualmente, adicionar os pavimentos até que todas as casas estejam conectadas, acrescentando os caminhos em ordem crescente de comprimento, sem conectar casas que já estejam ligadas. Diferentes soluções podem ser encontradas se você mudar a ordem na qual os caminhos de mesmo comprimento são adicionados. Duas soluções possíveis são mostradas abaixo.

Outra estratégia consiste em iniciar com todos os caminhos pavimentados e, depois, remover os caminhos que você não precisa. No entanto, isso requer muito mais esforço.

Onde você encontraria redes na vida real?

Os cientistas da computação chamam as representações dessas redes de “grafos”. Redes reais podem ser representadas por um grafo para resolver problemas, como projetar a melhor rede de estradas entre cidades ou rotas de voos no país.

Há também muitos outros algoritmos que podem ser aplicados aos grafos, tais como encontrar a distância mais curta entre dois pontos, ou o percurso mais curto que passa por todos os pontos.

Variações e extensões

Está é outra forma de representar as cidades e as estradas:

As casas são representadas por círculos, as estradas enlameadas por linhas, e o comprimento de uma estrada é dado pelo número ao lado da linha.

Os cientistas da computação e matemáticos usam frequentemente este tipo de diagrama para representar esses problemas. Eles o chamam de grafo.

Elabore alguns de seus próprios problemas do tipo Cidade Enlameada e teste-os com seus amigos.

Você pode descobrir uma regra para descrever quantas estradas ou conexões são necessárias para obter a melhor solução? Isso depende de quantas casas existem na cidade?

Folhas de Atividades e Materiais Adicionais

Você também pode baixar todas as folhas de atividade e materiais adicionais em formato editável aqui.

Do que se trata tudo isso?

Suponha que você esteja projetando a forma como um serviço tal como eletricidade, gás ou água deva ser entregue a uma nova comunidade. Uma rede de fios ou canos é necessária para conectar todas as casas à companhia prestadora do serviço. Toda casa precisa estar conectada à rede em algum ponto, mas a rota utilizada pela companhia para chegar até a casa não interessa realmente; apenas importa que essa rota exista.

A tarefa de projetar uma rede com um comprimento total mínimo é chamado de problema da Árvore Geradora Mínima (do inglês, minimal spanning tree).

Árvores geradoras mínimas não são úteis apenas em redes de gás e eletricidade; elas também nos ajudam a resolver problemas em redes de computadores, redes telefônicas, de oleodutos, e de rotas aéreas. No entanto, ao decidir as melhores rotas para as pessoas viajarem, você tem de levar em conta a forma que tornará a viagem mais conveniente para o viajante, bem como quanto irá custar. Ninguém quer passar horas em um avião utilizando a maior rota para chegar a outro país apenas porque é a mais barata. O algoritmo da cidade enlameada pode não ser muito útil para essas redes, porque ele simplesmente minimiza o comprimento total das estradas ou rotas de voo.

Árvores geradoras mínimas também são úteis para resolução de outros problemas envolvendo grafos, tais como o “Problema do Caixeiro Viajante”, que tenta encontrar a rota mais curta que visita todos os pontos da rede.

Existem algoritmos eficientes (métodos) para resolver problemas de árvore geradora mínima. Um método simples, que fornece uma solução ótima, consiste em começar sem conexões, e adicioná-las em ordem crescente de tamanho, acrescentando apenas as conexões que juntem partes da rede que ainda não foram conectadas. Esse método é chamado de algoritmo de Kruskal, em referência a J.B. Kruskal, que o publicou em 1956.

Para muitos problemas em grafos, incluindo o “Problema do Caixeiro Viajante”, os cientistas da computação ainda procuram encontrar métodos que achem a melhor solução possível.

Para saber mais

O tópico grafos não faz parte do currículo da educação básica, mas pode ser acessível para estudantes de todas as idades. A coleção Matemática Multimídia possui diversos recursos educacionais que abordam esse tópico com níveis de complexidade muito variados. Se você se interessou, conheça alguns deles aqui.

O Portal da Matemática da OBEMP oferece um módulo sobre grafos com várias video-aulas que partem de uma abordagem bastante inicial até problemas bastante avançados.

O blog Imaginário Puro traz um texto sobre árvores geradoras mínimas que pode ser bastante enriquecedor para o leitor interessado.

Soluções e Dicas

Variações e extensões

Quantas estradas ou conexões são necessárias se houver n casas na cidade? Acontece que uma solução ótima terá sempre exatamente n-1 conexões, pois isso é sempre suficiente para conectar n casas, e acrescentando uma casa a mais seria criar rotas alternativas desnecessárias entre as casas.