Objetivo

Abordar a teoria dos grafos de forma simples, permitindo a aplicação de atividades divertidas e dinâmicas nas escolas a fim de estimular o interesse dos alunos no estudo de Matemática. A atividade proposta tem caráter interdisciplinar e consiste em determinar um roteiro de viagem que inclua 20 cidades brasileiras.

Resumo

Trazemos o “Jogo de Hamilton” (Icosian Game, ou A Voyage round the world) para o contexto brasileiro e apresentamos “O Problema do Caixeiro Viajante”. 
1. Inciamos a palestra/oficina com a seguinte situação: Considerando a cidade de São José do Rio Preto, e outras 19 cidades brasileiras, encontrar um roteiro de viagem que partindo de São José do Rio Preto inclua as outras 19 cidades apenas uma vez e retorne ao ponto de partida. Considerando a existência de mais de um roteiro, e associando um custo a cada um deles, determinar o roteiro de menor valor. 
2. Fazemos uma breve apresentação do Problema do Caixeiro Viajante e de conceitos básicos da Teoria dos Grafos.
3. Usando o conceito de permutação discutimos a dificuldade do problema e apresentamos a idéia de algoritmos heurísticos.
4. Propomos uma breve discussão sobre a importância do problema na solução de outros problemas do dia a dia.

Requisitos e Público Alvo

Não há. A palestra/oficina será adequada à maturidade do grupo.

Recursos

Papel, quadro de giz ou branco, ou “flip chart”. Se possível projetor multimídia e tela (ou parede branca) para as ilustrações, preferivelmente com computador.

Duração

Duas horas, aproximadamente.

Avaliação

No fim da atividade, os participantes fazem uma breve avaliação respondendo as seguintes perguntas: 1. Qual foi a coisa mais importante que aprendeu? 2. Qual foi a maior dúvida que ficou? 3. Comentários.

Bibliografia

1. Jurkiewicz, S., Grafos - Uma Introdução, Apostilas OBMEP, disponível em http://www.obmep.org.br/docs/apostila5.pdf (última visita 25/10/2017. 

2. Rabelo, A. S. ; Moreira, M. ; Rangel, S. O problema do caixeiro viajante como auxiliar no desenvolvimento do raciocínio no ensino fundamental e médio. In: XXXIII CNMAC, 2010. Anais do .... Rio de Janeiro: SBMAC, 2010.

3. Rangel, Socorro. Espaços Museológicos e o Ensino de Matemática. In: Elso Drigo Filho. (Org.). Espaços Museológicos e Educação Formal. 1ed.Jundiai: Paco Editorial, 2015, v. 1, p. 77-88.