• Noções de análise combinatória e teoria dos grafos.

• Princípio Fundamental da Contagem.

A Teoria dos Grafos é um dos conhecimentos matemáticos com mais aplicações a realidade. É muito utilizado nos planejamentos de redes elétricas, hidráulicas, de computadores ou ainda para otimizar custos em distribuição de produtos ou até na coleta do lixo urbano.

Para saber mais sobre esta teoria recomendamos a leitura da Apostila 5 - Introdução a Teoria dos Grafos - OBMEP, acessível em 

http://www.obmep.org.br/export/sites/default/arquivos/apostilas_pic2008/Apostila5-Grafos.pdf

Um vídeo interessante sobre grafos pode ser visto no endereço:

http://www.youtube.com/watch?v=PXYT3opZIyc

Leitura complementar:

P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi,   Uma Introdução Sucinta à Teoria dos Grafos,  2004.   [Texto sobre alguns tópicos de teoria dos grafos.]

ATIVIDADE 1

 Conhecendo o Google Mapas

1º) Leve os alunos ao laboratório de informática.

2º) Organize-os em duplas por computador.

3º) Peça ao aluno que procure no site do googlemaps (http://maps.google.com.br/) um mapa de ruas próximas a sua casa ou escola.

4º) Em seguida, mande-o denominar cada cruzamento por uma letra. Veja o exemplo abaixo:

Imagem do autor a partir de http://maps.google.com.br

5º) Use a ferramenta rota para obter a distância e o tempo gasto para percorrer o trajeto entre cada cruzamento (vértice).

Imagem do autor a partir de http://maps.google.com.br

6º) Peça a cada aluno que faça uma tabela contendo a distância e o tempo gasto entre esses pontos.

7º) Agora peça para que sejam feitos esquemas gráficos para representar estas informações. Uma representação comum é feita substituindo os cruzamentos por pontos (vértices) e as ligações por linhas (arestas). Neste momento não é necessário dar nome a este tipo de representação.

Aos alunos que forem mais rápido, ou seja, que tenham terminado a atividade antes dos outros, o professor pode pedir a esses alunos que tentem localizar outros pontos, como por exemplo o endereço da escola, da casa, mas é necessário que o professor esteja atento para que não se estabeleça a brincadeira.

ATIVIDADE 2

 O Problema do Carteiro

Professor, após coletar os dados obtidos na atividade anterior, apresente para a turma um problema como este.

Um carteiro é responsável por entregar as cartas na região estudada por você na atividade 1, partindo da agência que fica no ponto A (deixe que o aluno faça a distribuição dos pontos) ele deve passar por todos os pontos indicados na figura.

Imagem do autor a partir de http://maps.google.com.br

Sugestões de perguntas:

a) É possível para o carteiro realizar um caminho onde possa entregar todas as correspondências passando exatamente uma vez por cada rua? Determine, se possível, esse trajeto ou explique a impossibilidade.   

b) Que ruas você recomendaria ao carteiro, para serem repetidas, de forma a minimizar seu trajeto, garantindo que todas as ruas fossem percorridas?

Os alunos devem buscar responder essas questões a partir de discussões em grupos.

ATIVIDADE 3

Divida a turma em pequenos grupos de no máximo 5 alunos e faça com eles algumas placas, de cartolina por exemplo.

Distribua essas placas no terreno da escola, onde cada uma delas representará um vértice (Casa, Armazém, Pracinha, Banca de Jornal, Quitanda, Cancela e Escola) do grafo que será construído.

Em seguida, peça aos alunos para calcularem a distância entre cada placa, a medida adotada pode ser o número de paços entre as placas, por exemplo. Depois disso, os grupos deverão esboçar um esquema, indicando a medida entre as placa. Veja um exemplo:

Imagem do autor

Reforce que as placas representam os vértices e as linhas as arestas do grafo.

Peça aos alunos para descreverem todos os caminhos possíveis de “casa” até “escola” indicando a medida do trajeto.  

Aproveite para apresentar o problema das pontes de Köenisberg. Um problema clássico da teoria dos Grafos.

Os habitantes de Köenisberg (hoje Kaliningrado) se perguntava se seria possível atravessar as sete pontes do Rio Prega, sem passar duas vezes na mesma ponte, retornando ao ponto de partida. O problema e sua modelagem por grafos está apresentada na figura a seguir.

Fonte: http://www.universitario.com.br/noticias/noticias_noticia.php?id_noticia=10201

Observamos que o problema dá origem a um grafo com arestas múltiplas, o que não afetará a solução. Leonard Euler mostrou que a resposta era negativa, estabelecendo assim uma condição necessária; embora se acredite que a suficiência não lhe fosse desconhecida. Esta segunda parte foi publicada por Hierholzer em 1873, muito mais tarde.

Google Maps - http://maps.google.com.br/maps?hl=pt-br&tab=wl

O livro "Grafos: jogos e desafios" (http://www.projetofundao.ufrj.br/matematica/images/stories/capagrafos.jpg) oferece exemplos de aplicações da Teoria dos Grafos em problemas de várias disciplinas, ou do cotidiano, apresentados como jogos e desafios.   

Para saber mais sobre esta teoria recomendamos a leitura da Apostila 5 - Introdução a Teoria dos Grafos - OBMEP, acessível em   

  http://www.obmep.org.br/export/sites/default/arquivos/apostilas_pic2008/Apostila5-Grafos.pdf

Professor, para avaliação, sugerimos os exercícios disponíveis na Apostila 5 - Introdução a Teoria dos Grafos - OBMEP, acessível em 

http://www.obmep.org.br/export/sites/default/arquivos/apostilas_pic2008/Apostila5-Grafos.pdf