Experimento

Ministério da Ciência e Tecnologia

Ministério da Educação

Secretaria de Educação a Distância

Guia do professor

licença Esta obrá está licenciada sob uma licença Creative Commons

Caminhos e grafos

Objetivos da unidadeIntroduzir o conceito de grafos;1. Analisar o conceito de grafo e identificar grafos que possuem 2. caminhos fechados e suas aplicações no cotidiano.

Análise de dAdos e probAbilidAde

Guia do professor

SinopseEste experimento apresenta atividades introdutórias para a Teoria de Grafos. Primeiro, a partir de problemas inspirados nas “Pontes de Konigsberg”, os alunos irão explorar uma série de situações reais que podem ser represen­tadas por grafos. Ao fim dessa etapa, eles deverão criar seus próprios caminhos, desafiando seus colegas a explorá­los.

ConteúdosCombinatória, Grafos.

ObjetivosIntroduzir o conceito de grafos;1. Analisar o conceito de grafo e identificar grafos que possuem caminhos 2. fechados e suas aplicações no cotidiano.

DuraçãoUma aula dupla.

Caminhos e grafos

Caminhos e grafos Guia do professor 2 / 6

Introdução

O problema das pontes de Konigsberg ficou famoso por ter servido de inspiração ao matemático Leonhard Euler, no começo do século XVIII, para a escrita do artigo que é considerado por muitos como o início da Topologia. Konigsberg é uma cidade localizada atualmente na Rússia, às margens do rio Pregel, e famosa pelas suas sete pontes que ligavam a parte conti­nental às suas duas ilhas, como mostrado na figura abaixo:

O desafio consistia em realizar um passeio pelas pontes de modo que o turista, sem passar duas vezes pela mesma ponte, percorresse todas elas. Na formulção original, Euler não impôs a condição de que o caminho terminasse no ponto de partida, mas é muito comum impô­la e faremos isso no experimento. Um passeio com essas características é chamado de passeio euleriano.

Euler resolveu o problema introduzindo o conceito de Grafo e, a partir de então, esse conceito vem sendo amplamente utilizado para analisar situações simples como a explorada neste experimento ou até situações complexas como compactação de arquivos em computadores. Outro resul­tado obtido por Euler e cuja demonstração utiliza argumentação de natu­reza topológica, semelhante ao que exploraremos aqui, é a conhecida “fórmula de Euler para poliedros”, que relaciona o número de vértices, arestas e faces de um poliedro.

Motivação

Apesar de Grafos não fazer parte do conteúdo programático do Ensino Médio, é um conceito matemático bastante simples e que pode servir como ferramenta para análises de situações muito variadas. O uso que se faz de Grafos no software “Matrizes e Aviões”, por exemplo, possibilita a análise de malhas aéreas através de operações de matrizes. Além disso, as situações formuladas neste experimento são simples e desafiadoras, assim como o problema original que inspirou Euler.

fig. 1

Caminhos e grafos Guia do professor 3 / 6

Um caminho em um grafo é uma sequência contínua de vértices e arestas. Um tal caminho é fechado se, a partir de um de seus vértices, é possível percorrer todos os outros vértices do caminho, passando uma única vez por todas as suas arestas e retornos ao vértice de partida.

A partir desses dois conceitos, o experimento desafia o aluno a representar algumas situações usando o conceito de grafos e procurar por caminhos fechados nestes.

Etapa 1 Exploração de caminhos

Esta é uma etapa de familiarização, na qual o aluno é desafiado a procurar por caminhos fechados em diversas situações reais, formuladas sem auxílio de grafos. O objetivo principal é fazer o aluno perceber que nem sempre é possível encontrar um caminho fechado, mesmo em situações simples, como acon­tece no segundo passeio pelo museu. A pergunta que encerra esta etapa na folha do aluno – “Qual será o menor caminho possível para o entregador de jornais?” – visa apenas fazê­lo perceber que qualquer caminho fechado tem o mesmo tamanho, igual à soma do comprimento de todas as arestas, pois passa por todas elas uma única vez Ao final, sugerimos que o professor introduza os grafos buscando mos­trar como eles facilitam a resolução dos problemas, uma vez que simplifica a representação das situações e a unifica em torno dos mesmos conceitos. Um detalhe importante sobre a tradução das situações enunciadas para grafos é a identificação do que deve ser chamado de aresta e do que deve ser chamado de vértice. No problema original de Euler, as pontes representavam as arestas e as porções de terra eram representadas pelos vértices. Note que a formulação do problema era: fazer um passeio por todas as pontes sem repetir nenhuma delas e terminando na mesma

O experimento

Comentários iniciais

Todo o experimento depende essencialmente de dois conceitos, o de Grafo e o de caminho fechado em um Grafo.

Um grafo consiste de um conjunto finito e não vazio de pontos chamados vértices (representados abaixo pelos números). Os vértices, por sua vez, são ligados por segmentos que são chamados de arestas (represen tados abaixo pelas letras).

Definição de grafo

Definição de caminho fechado

1

2

3

4

5

A

B

C

D

E

F

G

fig. 2 Ilustração conceitual

Caminhos e grafos Guia do professor 4 / 6

Fechamento

O ponto chave do fechamento desta atividade é a formalização da condição necessária e suficiente para que um grafo admita um caminho fechado.

Os grafos que admitem caminho fechado são aqueles, e somente aqueles, que em cada vértice incide um número par de arestas.

A demonstração rigorosa para esse resultado pode ser encontrado no livro Introdução a Análise Combinatória (vide BibliogrAfiA), mas a essência dos argumentos está no fato de que as arestas que incidem em cada um dos vértices devem vir sempre aos pares para que se possa “chegar” por uma e “sair” pela outra. Se algum vértice tiver um número ímpar de arestas (2n+ 1), poderemos passar por ele n vezes (passando por 2n arestas) sem problemas, mas na próxima vez que atingi­lo, não haverá arestas por onde sair. Uma vez conhecida essa condição, fica simples perceber qual grafo admite ou não um caminho fechado, por maior que ele seja.

porção de terra. Em relação ao conceito de grafos, isso se traduz para: passar por todas as arestas, sem repetir nenhuma, e terminar no mesmo vértice onde o caminho começou. No caso do museu, o desafio é percorrer todas as portas (e não salas, como seria de se esperar), terminando na mesma sala. Logo, as portas representam as arestas e as salas representam os vértices. Na caso do entregador de jornais, as ruas são representadas por arestas e os vértices são as conexões entre as ruas e a gráfica.

Etapa 2 Quem conhece cria

Nesta etapa, o objetivo é que os alunos criem grafos com e sem caminhos fechados para desafiar os outros grupos a encontrá­los. Como os alunos ainda não conhecem a condição para que um grafo admita um caminho fechado, pode ser que algum grupo se engane ao achar que determinado grafo o admite ou não. Deixe que isso ocorra e fomente as discussões entre os grupos sobre isso. No final, sugerimos que os grupos tentem alterar os grafos para os quais ninguém encontrou um caminho fechado, de forma que eles passem a admitir um. Note que “alterar um grafo” significa incluir novas arestas. A última pergunta desta etapa na Folha do Aluno desafia o estudante a resolver o problema das pontes de Konigsberg. Sugerimos que o componente histórico seja explorado para estimular os alunos, afinal, esse problema mereceu os cuidados de uma dos maiores matemáticos da história!

Condição para existência de caminhos fechados em um grafo

Caminhos e grafos Guia do professor 5 / 6

Bibliografia

Eves, H. Introdução à História da Matemática. Campinas: Editora da Unicamp, 2004.

SAntos, José Plínio O.; Mello, Margarida P.; MurAri, Idani T. C. Introdução à Análise Combinatória. Campinas: Editora da Unicamp, 2002.

Variações

Este experimento dá condições para a exploração de vários outros pro­blemas envolvendo grafos. Um exemplo simples que pode ser originado das situações propostas aos alunos no experimento é a seguinte variação:

A partir dos grafos dados para o problema do entregador de jornais, fixe dois pontos como destino e origem. Qual é a menor distância, em número de arestas, entre eles? De quantas maneiras é possível ir do destino à origem percorrendo exatamente a menor distância possível?

A primeira pergunta é um questionamento recorrente para progra­madores de computador e a segunda pode ser respondida através de análise combinatória. O problema em si fica mais interessante quando tomamos grafos maiores, com muitos pontos e arestas. Uma sugestão para investigação inicial é um quadriculado completo, isto é, um reticulado onde as arestas são os lados dos quadrados e os vértices do garfo são os vértices dos quadrados.

Ficha técnica

Ministério da Ciência e Tecnologia

Ministério da Educação

Secretaria de Educação a Distância

Matemática MultimídiaCoordenador GeralSamuel Rocha de OliveiraCoordenador de ExperimentosLeonardo Barichello

Instituto de Matemática, Estatística e Computação Científica (imecc – unicamp)DiretorJayme Vaz Jr.Vice-DiretorEdmundo Capelas de Oliveira

Universidade Estadual de CampinasReitorJosé Tadeu JorgeVice-ReitorFernando Ferreira da Costa

Grupo Gestor de Projetos Educacionais (ggpe – unicamp)CoordenadorFernando ArantesGerente ExecutivaMiriam C. C. de Oliveira

licença Esta obrá está licenciada sob uma licença Creative Commons

AutorLeonardo Barichello

RevisoresMatemáticaAntônio Carlos PatrocínioLíngua PortuguesaCarolina Bonturi PedagogiaÂngela Soligo

Projeto gráfico e ilustrações técnicasPreface Design

Caminhos e grafos Folha do aluno 1 / 2

Folha do aluno Análise de Dados e Probabilidade

Comentários iniciais

Essa ilustração representa a cidade de Konigsberg. Em 1736, o grande matemático Euler pensou sobre a possi bilidade de se realizar um passeio passando pelas 7 pontes voltando ao ponto inicial, sem repetir nenhuma ponte. Esse problema deu origem a uma séries de outros e, nos dias de hoje, tem muitas aplicações.

Etapa 1 Exploração de caminhosEssa é a planta de uma exposição de um museu. Você 1. acha possível fazer um passeio pelas salas, passando por todas elas e apenas uma vez por cada porta? Se sim, encontre uma solução;

Observe agora a segunda planta. Neste caso, seria pos-2. sível criar um caminho com as mesmas regras? Se sim, encontre uma solução;

Agora vamos pensar no trabalho de um entregador 3. de jornais. Ele deve passar por várias ruas até que abasteça todos os assinantes. A gráfi ca é seu ponto de

partida e deve ser seu ponto de chegada, após entregar todos os jornais. Em cada uma das 3 situações, veja se é possível encontrar um trajeto pelo qual ele entregue todos os jornais, passando apenas uma vez em cada rua. Explique como pensou em cada uma delas.

Qual será o menor caminho possível para o entregador de jornais?

Pense e responda

sala 1 sala 2

sala 3sala 4

sala 5

sala 2

sala 4

sala 5

sala 1

jornal

sala 1 sala 2

sala 4 sala 3

fig. 1

fig. 3

fig. 4

fig. 5

fig. 2

Caminhos e grafos Folha do aluno 2 / 2

Folha do aluno

Etapa 2 Quem conhece criaCrie em dupla 2 grafos para que seus colegas busquem 1. por caminhos fechados. Apenas um deles deve possuir um caminho fechado, mas não identifi que qual possui e qual não possui solução! Faça isso numa folha sepa-rada e assinem, pois o professor irá recolhê-la.Quando receber o grafo de um colega, reproduza-o 2. em seu caderno, anotando os nomes da dupla que o criaram.

Seria possível alterar os caminhos de modo que o novo grafo permita a existência de um caminho fechado? Explique seu raciocínio.

Para alterar um grafo, será permitido apenas acrescentar arestas entre vértices.

Lembra da fi gura do início da atividade? Veja-a nova-mente e tente encontrar uma rota para o passeio. É possível passar por todas as pontes, sem repetir nenhuma? Se sim, diga qual é esse caminho. Se não for possível, explique o motivo e corrij a o mapa, sem esquecer da regra de correção!

Análise de Dados e Probabilidade

Pense e responda

Pense e responda