MATEMÁTICA DISCRETA NO ENSINO MÉDIO

Transcrição

RELATÓRIOS DE PESQUISA EM ENGENHARIA DE PRODUÇÃO, v.13, Série B. n.2, p. 8-19.
MATEMÁTICA DISCRETA NO ENSINO MÉDIO UM TRABALHO COM GRAFOS EULERIANOS
Christine Sertã Costa
Colégio Pedro II – Departamento de Matemática
Pontifícia Universidade Católica do Rio de Janeiro – Departamento de Matemática
Resumo
O trabalho aqui relatado faz parte de uma proposta de introdução de novos conceitos da Matemática
Discreta a turmas do ensino Fundamental e Médio em escolas do Brasil que vem amadurecendo nos
últimos anos. Esta abordagem foi inicialmente apresentada em Jurkiewicz (2002) e desde então já são
encontrados na literatura alguns relatos de experiências bem sucedidas com este enfoque. Algumas mais
recentes estão em Ferreira & Lozano (2009), Lopes (2010) e Lozano, Rangel & Pires (2010). Neste
trabalho a área escolhida dentro da Matemática Discreta foi a Teoria dos Grafos - especificamente grafos
eulerianos, que é um problema bem resolvido, simples e de muita aplicabilidade desta teoria. Este
projeto foi desenvolvido em 2012 com alunos do 1º. Ano do ensino médio do Colégio Pedro II – Unidade
Humaitá, localizado na cidade do Rio de Janeiro.
Palavras-Chave: Matemática Discreta, Grafos Eulerianos, Ensino.
Abstract
The work reported here is part of a proposal to introduce new concepts of Discrete Mathematics to
classes of Elementary Schools and Middle Schools in Brazil that has matured in recent years. This
approach was first presented in Jurkiewicz – 2002 and has since found in the literature are few reports of
successful experiences with this approach. Some recent of them can be found in Ferreira & Lozano
(2009), Lopes (2010) and Lozano, Rangel & Pires (2010). In this work within the chosen area was the
Discrete Mathematics Graph Theory - specifically the problem of Eulerian graphs. This is a wellresolved and simple problem of the theory and with many applications. This project was developed with
students from the 1st. Year of High School at the Colégio Pedro II - Humaitá Unit, located in the city of
Rio de Janeiro.
Keywords: Discrete Mathematics, Eulerian Graphs, Education.
Artigo submetido em 15/7/2013. Versão final recebida em 17/8/2013. Publicado em 9/9/2013.
MATEMÁTICA DISCRETA NO ENSINO MÉDIO - UM TRABALHO COM GRAFOS EULERIANOS
1. Introdução
A Teoria dos Grafos é um ramo da Matemática Discreta com diversas aplicações em vários
níveis no mundo contemporâneo, mas, apesar disso, ela não tem sido amplamente estudada nos
cursos de licenciatura em Matemática nem apresentada a alunos do ensino Fundamental e
Médio no Brasil. Especificamente, conceitos básicos de grafos e algumas de suas aplicações,
incluindo os grafos eulerianos (tema do presente estudo), podem ser bem compreendidos e
interessantes para alunos das séries iniciais e possibilitam a construção de trabalhos aplicados e
interdisciplinares, tópicos ressaltados pelos PCN’s.
Como argumentos favoráveis à inclusão de assuntos relacionados com a Matemática Discreta
nas séries iniciais, pode-se citar que muitas das questões abordadas por esta teoria:
-permitem a apresentação de problemas interessantes do mundo contemporâneo que motivam o
aluno a buscar um entendimento completo da questão proposta e da sua solução. Muitas vezes
esses problemas naturalmente possibilitam um debate interdisciplinar.
-possibilitam o exercício constante da enumeração de casos, do desenvolvimento de estratégias
variadas de solução e da análise crítica das soluções encontradas por cada caminho para os
problemas propostos.
-propiciam a discussão e a implementação de abordagens computacionais.
-estão sendo temas atuais em olimpíadas de Matemática (OBM, OMERJ, OBMEP, etc) e
concursos de vestibulares (ENEM) no país.
Todo o relato acima motivou a construção deste trabalho que apresenta as etapas da aplicação
de um projeto realizado com alunos do 1º ano do Ensino Médio do Colégio Pedro II – unidade
Humaitá com o objetivo de promover a esses alunos um primeiro contato com a teoria dos
grafos eulerianos. As etapas, observações obtidas e conclusões estão descritas no decorrer do
presente estudo.
2. Primeira etapa do Projeto: Escolha do tema, forma motivadora de apresentá-lo e busca
de uma solução.
Com o intuito de apresentar os conceitos básicos de grafos, teoria desconhecida para os alunos
do ensino Médio, escolheu-se trabalhar com os grafos eulerianos, muito em função da
simplicidade na modelagem do problema proposto utilizando esta Teoria bem como pela forma
bem resolvida, simples e elegante de entendimento da solução. Além disso, esse tema foi o
primeiro registro que se tem conhecimento de um problema relacionado com o que hoje em dia
se chama Teoria dos Grafos: O Problema das Sete Pontes, muito conhecido entre os estudantes
da área. Uma descrição do mesmo pode ser encontrada em Boaventura Netto (2009), entre
outros.
Para motivar a introdução desta nova teoria, escolheu-se um problema que causasse interesse
no público e tivesse clareza tanto na modelagem como nas soluções das questões propostas. Por
isso foi escolhido o problema do Caso Count Van Diamond, encontrado em
http://www.inf.ufsc.br/grafos/temas/euleriano/euleriano.htm e descrito a seguir com algumas
adaptações.
O material apresentado adiante, chamado de Desafio Interessante, foi entregue aos alunos e
eles tiveram uma semana para debater e construir suas próprias soluções para as questões
9
propostas. Cabe relembrar que até este momento grafos era um assunto completamente
desconhecido para o grupo.
COLÉGIO PEDRO II – UNIDADE HUMAITÁ II
1ª. ANO ENSINO MÉDIO – 1º. TURNO – MATEMÁTICA
DESAFIO INTERESSANTE: O CASO COUNT VAN DIAMOND
O cenário ao lado é a
residência do bbilionário
Count Van Diamond,
que acaba de ser
assassinado na Sala da
Piscina de sua mansão.
JARDIM
Sherlock Gomes (um conhecido detetive que nas horas vagas é um estudioso de várias áreas da
Matemática) foi chamado para investigar o caso. Os presentes na mansão na hora do crime
prestaram os depoimentos descritos a seguir.
- O mordomo alega ter visto o jardineiro e a empregada saírem do jardim e entrarem na sala da
piscina por uma das portas de acesso e mais tarde voltarem ao jardim pela outra porta.
- O jardineiro,, em sua defesa, afirma que entrou para repor flores em todos os cômodos da casa.
Garante que
ue entrou na casa por uma das portas ligadas ao jardim, passou por todas as portas da
casa uma única vez e, em seguida, voltou ao jardim saindo pela porta que não entrou.
- A empregada por sua vez, sustenta que entrou para limpar todos os cômodos da casa, exceto o
bar. Garante também que passou por todas as portas da casa, menos as portas que levam ao bar,
uma única vez e em seguida voltou ao jardim pela porta que não entrou.
Sherlock Gomes então:
–
Confirmou
onfirmou pelas câmeras de segurança da casa que realmente o jardineiro e a
empregada tinham passado certo tempo dentro da casa e que ambos entraram por uma das
portas e saíram pela outra, como afirmaram.
–
Constatou
onstatou que, conforme os depoimentos
depoimentos levantados, realmente os vasos de todos os
cômodos da casa tinham flores viçosas e certamente recém colocadas nos seus respectivos
vasos e, com exceção do bar, todos os demais cômodos estavam extraordinariamente limpos.
10
–
Estudou a planta da residência (conforme figura acima), pensou um pouco e, em pouco
tempo, declarou que havia solucionado o caso.
Questões Propostas:
Sabendo que o suspeito indicado por Sherlock Gomes é aquele cujo depoimento apresenta uma
contradição, responda as questões propostas a seguir:
a)
Considerando que o relato da empregada é verdadeiro, apresente se possível,
dois caminhos distintos que ela possa ter tomado para limpar os cômodos, conforme
afirmou.
b)
Considerando que o relato do jardineiro é verdadeiro, apresente se possível, um
caminho que ele possa ter tomado para trocar as flores dos vasos da casa, conforme
afirmou.
c)
Quem é o suspeito apontado por Sherlock Gomes? Explique o raciocínio que o
detetive desenvolveu para acusá-lo.
d)
Que tipo de alteração você faria na planta da casa de modo que o depoimento
do referido suspeito apontado no item (c) não fosse mais contraditório? Justifique.
e)
Se uma pessoa encontra-se na Sala Principal ela consegue passear pela casa
passando uma única vez por todas as suas portas? Em caso afirmativo, apresente uma
solução que satisfaça e destaque onde esta pessoa terminaria esse passeio.
A proposta exposta foi construída com o objetivo de apresentar os conceitos básicos de grafos
conexos não orientados e a questão da euleridade - teoria pode ser encontrada em (Boaventura
Netto, 2009). Porém, inicialmente pretendeu-se verificar que tipos de estratégias os alunos
usariam para responder às questões e a forma como apresentariam argumentações para
sustentar suas soluções sem interferências, apenas com os encaminhamentos sugeridos pelas
questões propostas.
3. Resultados Obtidos com a Primeira Etapa
Com os itens (a) e (b) propostos, tinha-se uma expectativa que eles construíssem caminhos por
tentativas (item a) ou, depois de exaustivas tentativas, fossem capazes de afirmar que tal
caminho não existe (item b). Além disso, esses itens dão os subsídios necessários para que
estejam aptos a resolver o item (c). E isso realmente foi verificado na prática.
Sobre o item (a): A grande maioria dos grupos apresentou as duas soluções pedidas para o item
(a) a partir da construção de caminhos na própria figura da planta da mansão apresentada na
proposta (figura 1). Alguns apresentaram estes caminhos expressos textualmente (figura 2).
Cabe uma observação: muitos dos que apresentaram as duas soluções pedidas no item (a) o
11
fizeram simplesmente invertendo a ordem dos ccômodos
ômodos visitados na primeira solução por eles
apresentada.
Figura 1 : Dois caminhos de percursos possíveis realizados pela empregada
Figura 2: Apresentação dos dois caminhos pedidos no item (a) da proposta
Sobre o item (b): três tipos de solução foram
fora apresentadas:
- simplesmente enunciavam que este caminho não era possível;
- construíam na própria planta da mansão um caminho que passa uma única vez por todas as
portas, exceto a porta que liga o Quarto Principal à Sala Principal, mostrando a contradiç
contradição do
depoimento do jardineiro (figura 3) ou
- afirmavam que para trocar as flores de todos os vasos seria necessário passar duas vezes por
uma porta, contrariando o depoimento do jardineiro (figura 4).
12
Figura 3: Apresentação de um caminho que não passa pela porta que liga Sala Principal ao Quarto Principal
Figura 4 : Opções que justificam a contradição do depoimento do jardineiro
Sobre o item (c): Uma vez construídos os itens (a) e (b) foi imediato para os grupos apontar o
jardineiro como suspeito, resposta do item (c), alegando que não era possível construir um
caminho com as restrições colocadas no depoimento do mesmo. Nenhum trabalho justificou o
porquê da impossibilidade desta construção de alguma outra forma que não fosse por tentativas
exaustivas de satisfazer as condições de cada depoimento.
Sobre o item (d): as soluções propostas foram:
- retirada do bar da mansão (justificado
justificado pelo desenvolvimento
desenvolv
do item (a)).
- retirada da porta que liga o Quarto Principal à Sala Principal (solução obtida pelos que
tentavam construir um caminho com as restrições do jardineiro e verificavam que não
passavam pela referida porta – desenvolvimento do item (b)).
(b)
Sobre o item (e): os grupos novamente apresentaram
apresenta m na planta da mansão um caminho que
começa na Sala Principal, passa por todas as portas uma única vez e termina no Quarto
Principal (figura 5), obtido por exaustão
exaustão.
13
Figura 5 : Caminho que começa na Sala principal e termina no Quarto Principal
4. Segunda etapa do Projeto: A introdução dos novos conceitos da Teoria dos Grafos e a
solução do Problema baseada nesta teoria
Após a análise dos resultados obtidos com as respostas dos alunos para o desafio proposto,
chegou a hora da apresentação da nova teoria com o objetivo de mostrar uma nova forma para
resolver o problema e consolidar conceitos que possibilitem solucionar outros
ros problemas
correlatos. Nesta etapa então foram apresentados às turmas os primeiros minutos do filme O
Legado
de
Pitágoras,
Pitágoras
que
pode
ser
encontrado
em
http://tvescola.mec.gov.br/index.php?option=com_zoo&view=item&item_id=1917
a.mec.gov.br/index.php?option=com_zoo&view=item&item_id=1917..
Neste trecho do filme é apresentado
apresenta o famoso Problema das Sete Pontes de Konigsberg
(território da Prússia até 1945, atual Kaliningrado, na Rússia), que é um histórico problema
da Matemática Discreta e uma das principais fundações da Teoria dos Grafos.
De forma bastante agradável e didática, o filme mostra a cidade de Konigsberg.
Konigsberg. Cortada pelo
Rio Prególia, esta cidade têm
m duas grandes ilhas que juntas formam um complexo que na
época tinha sete pontes (cabe ressaltar que neste momento seria interessante a intervenção de
outras áreas do conhecimento tais como a História e a Geografia). Discutia-se
se na cidade se
seria possível atravessar todas as pontes passando uma única vez por cada uma delas. Muitos
tentaram resolver o problema e em 1736 uma solução foi apresentada por Leonard Euler. O
filme apresenta uma animação bem interessante
interessante para a tentativa de solução do problema.
Introduz-se assim,, mesmo que de forma bem simplificada, o conceito intuitivo de grafo e sua
representação gráfica. A cada parte de terra do problema, associa-se
se um ponto (chamado de
vértice) e a cada ponte associa-se
associa
uma linha (chamada de aresta). Dessa forma, o grafo
representativo do problema das Sete Pontes é apresentado aos alunos conforme a ffigura 6.
Figura 6 : representação gráfica do grafo representativo do Problema das Sete Pontes
14
Após assistirem ao filme e terem tido
t
contatoo com os conceitos básicos de grafos (seus
elementos – vértices e arestas; definições de grafo simples, orientados e não orientados,
caminhos e ciclos e grau de um vértice), foi possível desenvolver as questões referentes a
grafos não orientados que têm, ou não, um ciclo ou caminho euleriano.. Essas questões foram
provocadas pelo professor e discutidas
discutid exaustivamente com as turmas (figura 7)) até que eles
próprios conseguissem concluir o Teorema de Euler (uma demonstração pode ser encontrada
em Boaventura - 2006).
Figura 7 : Grafos com ciclo euleriano, caminho euleriano e sem caminho euleriano
Resumo das conclusões
ões obtidas pelas turmas (Teorema de Euler)
Seja G um grafo conexo simples não orientado.
- Se todos os vértices de G têm grau par,
par então G é um grafo euleriano: é possível, a partir de
qualquer vértice de G, passar por todas as suas arestas uma única vez e retornar ao vértice de
partida.
- Se exatamente dois vértices de G têm grau ímpar, então G é um grafo que
ue possui um caminho
euleriano: é possível, a partir de um dos vértices de grau ímpar, passar por todas as suas arestas
uma única vez e finalizar no outro vértice de grau ímpar.
- Se G tem mais de dois vértices de grau ímpar,
ímpar então G não possui nem
em ciclo euleriano nem
caminho euleriano.
Neste momento, os alunos novamente se organizaram nos grupos e rapidamente procuraram
modelar, solucionar e justificar o problema do caso Count Van Diamond usando a Teoria dos
Grafos. O grafo representativo do problema, no qual cada cômodo da casa foi representado por
um vértice e as portas por arestas ligando esses vértices, foi elaborado com facilidade pelos
grupos e encontra-se na figura 8.
8
15
Figura 8:: Grafo representativo do problema do caso Count Van Diamond
Nesta etapa, os alunos naturalmente concluíram que os vértices SP (Sala Principal) e QP
(Quarto Principal) são os únicos dos quais saem um número ímpar de arestas (vértices de grau
ímpar). Sendo assim, conseguiram
iram concluir que este grafo possui um caminho euleriano, desde
que se comece em SP (ou QP)) e termine em QP (ou SP). Todoss os demais itens propost
propostos no
trabalho foram novamente respondidos,
respondidos agora com mais clareza tendo por base as conclusões
obtidas da nova teoria apresentada
apresentada.
5. Terceira etapa do Projeto: A avaliação por parte do grupo participante
Finalmente, foi pedido aos alunos que avaliassem todo o trabalho e colocassem
colocassem suas opiniões
pessoais sobre o interesse no tema, análise do quantoo efetivamente tinham aprendido e na
dinâmica da realização do projeto em todas as suas etapas.
A tônica dos retornos obtidos foi
fo muito favorável e os seguintes tópicos merecem destaque
destaque,
pois retratam relatos de todas as avaliações obtidas:
- O grande interessee pelo tema motivador do trabalho: elucidação de um crime.
crime Muitos
inclusive gostariam que o desafio tivesse mais pessoas envolvidas para que dificultasse a
solução.
- O total entendimento das definições apresentadas sobre grafos e a clareza sobre como decidir
se um grafo é ou não euleriano.
- A facilidade e simplificação para responder as questões propostas a partir da nova teoria.
- A importância da apresentação de um conteúdo a partir de um problema interessante proposto
que possibilite formas distintas de solução e debates de diversas abordagens.
- A curiosidade de se desenvolver
desenvolv assuntos da Matemática “sem contas nem fórmulas”.
16
6. Alguns problemas interessantes que também desenvolvem este conteúdo.
Com o intuito de acrescentar opções distintas para abordagem do tema em função do público
alvo que se pretende trabalhar, alguns problemas que se adaptam ao tema são propostos a seguir
mostrando a variedade de motivações que podem ser proporcionadas.
Problema 1:
Considere as 21 peças do jogo de dominó que não são peças duplas (dois números iguais na
mesma peça). Cada uma dessas peças corresponde a um subconjunto de cardinalidade 2 do
conjunto {0,1,2,3,4,5,6}. Com vocês sabem, a regra do jogo do dominó determina que é permitido "encostar" uma peça x formada pelos número {i,j} numa peça y com os números {k,l} se e
só se j = k formando assim a sequência (i,j,j,l). Responda as questões a seguir. Procure justificá-las usando conceitos da Teoria dos Grafos.
(a) É possível formar uma “roda” que contenha todas essas 21 peças?
(b) Eliminando-se dessas 21 peças todas as que contêm o número “6”, é possível formar uma
“roda” com as restantes?
(c ) Acrescentando-se a essas 21 peças as peças duplas do dominó, é possível formar a roda?
Problema 2:
Imagine que nas figuras a seguir os vértices são esquinas e as arestas ruas de mão dupla.
Suponha que pretende-se recolher o lixo de todas as ruas consideradas minimizando ao máximo
o gasto de combustível, ou seja, passando uma única vez por cada rua e retornando ao ponto de
partida.
(a) Isto é possível no grafo (a) ? E no (b)
(b) Apresente um percurso possível para o grafo que você respondeu SIM no item anterior
(c) Para o grafo que você respondeu NÃO, decida se é possível recolher todo o lixo
passando uma única vez por cada rua mas não retornando ao ponto de partida.
Apresente um percurso que satisfaça, se possível.
17
Problema 3 ( http://www.inf.ufsc.br/grafos/temas/euleriano/euleriano.htm):
Tertuliano Gonçalves havia prometido casamento a Josefina das Graças. O evento deveria ser
realizado, segundo ele, assim que acabasse o contrato de trabalho assinado recentemente com
uma empresa encarregada de pavimentar toda a rede de estradas que liga Santana do Caixa
Prego (cidade onde mora Josefina) às cidades da região. O trabalho iria começar em Santana e
prosseguir em continuidade, estrada após estrada, terminando, segundo explicou Tertuliano, na
própria Santana. A rede de estradas é dada pela tabela abaixo, na qual a cidade de Santana do
Caixa Prego é representada pelo número 1 e se existe um X na linha i coluna j da tabela é
porque existe uma estrada ligando diretamente a cidade i até a cidade j.
(a) Você, que leu a estória, acredita que Tertuliano estava sendo sincero com Josefina? Por
quê?
(b) E se o itinerário 1-5-9-10 estivesse a cargo de outra empresa, estaria ele sendo sincero?
7. Considerações Finais
O objetivo primordial do presente trabalho é apresentar mais um projeto onde a inclusão de
conceitos da Matemática Discreta nos Ensinos Fundamental e Médio trouxe resultados
satisfatórios. Isso se deu com a introdução de conceitos da teoria dos Grafos, assunto não
trabalhado nos currículos padrões dessas séries no país.
Verificou-se que o tema favorece o raciocínio, motiva a construção de estratégias para busca da
solução, viabiliza um enfoque interdisciplinar em várias abordagens e principalmente causa
interesse ao alunado já que, em função do público alvo que se pretende atingir, várias
aplicações práticas distintas podem ser estabelecidas.
Além disso, cabe destacar que a estratégia de apresentar um problema motivador interessante e
de dividir as turmas em grupos não só estimulou a participação ativa de todos os envolvidos
como também permitiu a construção de habilidades necessárias na aprendizagem e
acompanhamento perceptivo por parte do professor.
Espera-se que este trabalho dê mais uma contribuição para o desenvolvimento do ensino da
Matemática Discreta nos Ensinos Fundamental e Médio das escolas do Brasil.
18
Referências Bibliográficas
Boaventura Netto, P.O. & Jurkiewicz, S. Grafos: Introdução e prática. Blucher, 2009. (ISBN
978-5-212-0473-2)
Boaventura Netto, P.O. Grafos: Teoria, Modelos, Algoritmos. 4ª edição, Blucher,2006. (ISBN
85-212-0391-8)
Ferreira, G.P. & Lozano, A.R.G (2009). A Viabilidade do Ensino de Matemática Discreta na
Educação Básica usando Modelagem Matemática, IX Congresso Nacional de Educação –
EDUCERE, III Encontro Sul Brasileiro de Psicopedagogia, PUCPR, 5558-5568.
Jurkiewicz, S. (2002). Matemática Discreta em Sala de aula. História e Tecnologia do Ensino
de Matemática. Carvalho. L. M.; Guimarães, L. C. (org), IME-UERJ, Rio de Janeiro, v1, 115161.
Lopes, M.L.M.L. Grafos: jogos e desafios. IM/UFRJ, 2010. (ISBN: 978-85-87674-20-3).
Lozano, D. & Rangel, S. & Pires, C. (2010). Uma Proposta de Oficina de Coloração de Mapas
e Grafos para o Ensino Fundamental e Médio, PODes – Revista Eletrônica Pesquisa
Operacional para o Desenvolvimento, v.2, n.3, 216-225.
19

MATEMÁTICA DISCRETA NO ENSINO MÉDIO

Transcrição

Documentos relacionados

UNIVERSIDADE FEDERAL DE MINAS GERAIS DEPARTAMENTO

Introduç˜ao `a Teoria dos grafos

Apresentação: Problema do isomorfismo em grafos

Matemática Discreta

Isomorfismo em Grafos

b-coloraç˜ao de grafos com poucos P4`s

Exercicios 3 - Departamento de Matemática - PUC-Rio

O que é um grafo?

Método Bonecas Russas para Conjunto Independente

Teoria dos Grafos Aula 9

faculdade norte capixaba de sâo mateus análise e desenvolvimento

Traçado automático de hipergrafos direcionados