Plano de Aula sobre o ensino de grafos

Objetivos: - Introduzir o conceito de grafos por meio de uma dinâmica; - Formalizar a definição de grafos e trabalhar algumas propriedades; - Mostrar aos alunos algumas aplicações de grafos no cotidiano; - Desenvolver atividades que auxiliem a compreensão dos alunos sobre grafos. Primeira aula: Dinâmica inicial: Antes de falar em grafos com os alunos, iremos propor uma dinâmica para apresentar o conteúdo a eles. A dinâmica iniciará com a seguinte questão: Cada aluno irá receber tiras de barbantes e a pergunta inicial será: Quais colegas da turma você já encontrou fora da escola? Assim, um por um, os alunos irão dizer os colegas que já encontraram fora da escola e entregarão a ponta de uma tira do barbante para cada um, segurando todas as outras pontas.

Ao final dessa dinâmica, observaremos se grupos isolados foram formados, ou sem algum aluno não se “ligou” a nenhum outro, assim como o número de ligações de cada aluno. Por fim, convidaremos os alunos a pensarem em cada um deles como um vértice e cada ligação feita com o barbante, uma aresta. Conversaremos com os alunos sobre problemas famosos de grafos, como o das “Pontes de Königsberg” e os indagaremos sobre que outros grafos, semelhantes ao que construímos na primeira aula, eles poderiam construir. Pontes de Königsberg: A cidade de Königsber é banhada pelo rio Pregel que, ao atravessar a cidade, se ramifica formando uma ilha, que está ligada à restante parte da cidade por meio de sete pontes. Dizia-se que os habitantes da cidade tentavam efetuar um percurso que os obrigava a passar por todas as pontes uma única vez.

Como suas tentativas foram sempre falhas, muitos deles acreditavam que não era possível encontrar tal percurso. Eles tinham razão? Terceira aula: Nessa aula iremos propor problemas que utilizamos os grafos para resolver. o turista começou o seu percurso em Tripla, mas não terminou por lá; c. o turista começou e terminou o seu percurso na ilha de Tripla; Terceiro Problema: Uma peça de fio tem 120cm de comprimento. É possível usá-la para formar arestas de um cubo com arestas de 10cm? Qual o menor número de cortes que é preciso fazer no fio para que se possa formar o cubo desejado? Quarto Problema: As estradas que ligam à região Norte do Brasil são sempre um problema para quem necessita utilizar, visto que são escassas e de má qualidade.

A região também possui uma grande bacia hidrográfica, o que impossibilita a construção de estradas em alguns trechos. Um candidato a presidência da república necessita se deslocar de Goiás, para Boa Vista, Roraima para cumprir alguns compromissos de sua campanha. Ao final da quarta aula, discutiremos com os alunos um exemplo real de aplicação de um grafo: APLICAÇÕES DE GRAFOS Problema do Lixo (otimização de gastos) Em uma pequena cidade temos 6 pontos de recolhimento de lixo e 10 ruas entre eles. O prefeito quer otimizar o gasto com gasolina do caminhão e fazer com que o caminhão passe por todos os pontos de recolhimento e ruas uma única vez. Logo, esse problema da vida real, pode ser resolvido com grafos, valendo-se de um grafo que satisfaz um Teorema de Euler sobre grafos conexos que garante que o grafo pode ser percorrido, pois o mesmo possui vértices de grau par.

Tente sair de um ponto e passar por todas as arestas uma única vez, voltando ao ponto inicial sem tirar o lápis do papel. ANEXOS Conjunto de definições: Definição: O grau de um vértice é o número de arestas ligadas a ele. Definição: Um circuito Euleriano é um circuito que contém todas as arestas de G. Iremos apresentar também os seguintes REFERÊNCIAS ARAÚJO, Adérito. As Pontes de Gönigsberg. Disponível <http://www. mat. O. MELLO, M. P. MURARI, I. T. pucrs. br/ciencias/viali/graduacao/po_2/literatura/grafos/monografias/tcc1. pdf> acesso em: 08 de dezembro de 2017.