CONHEÇA GRAFOS: INTERDISCIPLINARIDADE E CONTEXTUALIZAÇÃO
Jorge Bria (UFF)
[email protected]
Introdução
O tema grafos nada tem a ver com gráficos, é tema inédito no país para fins da
Educação Básica, é desconhecido da maioria dos professores de todos os níveis, sua
aplicabilidade possui abrangência realmente impressionante com ênfase em modelagem
(em inúmeras áreas do conhecimento humano, diversificadas situações-problema de
nosso próprio dia-a-dia, jogos em geral...), exerce forte atração sobre quem passa a
conhecê-lo e vem “como luva” ao encontro de nossos PCN: interdisciplinaridade,
transversalidade, contextualização…
Este minicurso motiva-se a partir da tese de doutorado e do projeto de extensão,
com respectivos títulos “Grafos no Ensino Fundamental e Médio: Matemática,
Interdisciplinaridade e Realidade” (COPPE/UFRJ, junho/2001) e “Propondo GRAFOS,
novo tópico matemático fortemente interdisciplinar para Educação Básica” (UFF, 2002
a 2004), de autoria e coordenação do Prof. Jorge Bria.
Nos últimos meses de execução em 2003 do referido projeto de extensão, nossa
equipe desenvolveu, entre outros, um texto-questionário (predominantemente, de
divulgação e sondagem) sobre a proposta geral Grafos para Educação Básica,
essencialmente escrito sob minha orientação pelas alunas do Curso de Graduação em
Matemática Camila Matheus Rodrigues da Silva, Daniele Paula Costa e Márcia Maria
Martins, material este que foi enviado a aproximadamente 200 professores, de inúmeros
municípios do estado do Rio de Janeiro, dos quais já tínhamos recebido retorno (até a
época da digitação deste texto de minicurso, em janeiro/2004) de quase 100 destes
profissionais mostrando, além de registros muito positivos sobre o tema, interesse em
participarem de oficinas que nos propúnhamos a dinamizar a respeito ao longo da
Anais do VIII ENEM – Minicurso
GT 7 – Formação de Professores que Ensinam Matemática
2
renovação de execução do projeto em 2004. A seguir, reproduzimos síntese do
parágrafo de apresentação de tal texto-questionário:
“De uso já consagrado em Engenharia de Produção, mas ainda não explorado no
ensino da Matemática na Escola e desconhecido da maioria dos professores, foi tema
proposto na tese de doutorado (COPPE/UFRJ, 2001) do Prof. Jorge Bria, de quem
somos orientandas formais no projeto Propondo Grafos, um novo tópico matemático
fortemente interdisciplinar para Educação Básica, da UFF, onde cursamos a
licenciatura em Matemática. A tese, de título “Grafos no Ensino Fundamental e Médio:
Matemática, Interdisciplinaridade e Realidade”, traz depoimentos manuscritos de apoio
à proposta de 61 professores de 17 municípios RJ julgando o tema adeqüável às várias
séries do Ensino Fundamental e Médio, fizemos experimentos com gratificante retorno
nas 6ª e 8ª séries em escolas públicas e particulares (Cantagalo, São João de Meriti e
Niterói) e recente trabalho de apresentação/divulgação da proposta foi publicado nos
anais da XI CIAEM - Conferência Interamericana de Educação Matemática (BlumenauSC, julho/2003). Viemos convidá-lo(la) para inteirar-se mais do assunto, lendo breve
exposição que preparamos, devolvendo-nos preenchida o mais breve possível a Ficha
de Manifestação Inicial de Interesse em anexo (sem qualquer compromisso no
momento) e, talvez − gostaríamos muito!!! −, participando conosco, para o que depois
o(a) convidaremos, de ações conjuntas como novas leituras, encontros, oficinas,
trabalhos com seus alunos, divulgação...”
Anais do VIII ENEM – Minicurso
GT 7 – Formação de Professores que Ensinam Matemática
3
Algumas áreas ou contextos em que se já se podem encontrar aplicações dos grafos
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
roteiros de passeio ou viagem
moléculas químicas
plantas de imóveis
redes elétricas
Ciências Sociais
árvore da vida
organogramas
árvores de procedimentos computacionais
telecomunicações: alocação de freqüências
Lingüística
“árvores” de possibilidades, decisão...
estruturas rígidas (Engenharia Civil)
Arqueologia
códigos
alocação de horários, atividades…
jogos: dominó, xadrez, baralho, da velha...
Psicologia do desenvolvimento
Genética
Ecologia
Música
jogos de “quebra-cabeça”
demanda de energia elétrica
minimização de caminhos em geral
distribuição de serviços: água, luz, gás, telefone…
circuitos impressos (componentes eletrônicos)
análise ou coloração de mapas
organização de tráfego
trajetos ótimos: vendedor, carteiro, caminhão de lixo…
saídas de labirintos
instalações: mecânicas, hidráulicas, elétricas, a cabo…
organização de campeonatos
combinatória, probabilidades, matrizes, poliedros...
Alguns dos 61 depoimentos de professores (17 municípios RJ) apoiando a proposta
y “Este conteúdo é tão significativo e com lógica tão profunda... Deveria ser abordado
desde a pré-escola (com didática toda especial) e, assim, estaríamos os estimulando
desde pequenos a raciocínios criativos”
y “Um caminho para o desenvolvimento da nova era Educação Matemática”
Anais do VIII ENEM – Minicurso
GT 7 – Formação de Professores que Ensinam Matemática
4
y “Muito interessante… Eu usava e não sabia”
y “Os alunos adoram criar suas próprias estratégias de resolução de problemas... Grafos
possibilitariam partir das estratégias dos alunos. Quando introduzidas noções de
Combinatória, por que não usar grafos?”
y “O tema favorece aplicações interdisciplinares, além de permitir o trabalho com o
lado lúdico, o que ajuda na motivação e interesse pelo assunto. Parece-me também o
tema poder favorecer o desenvolvimento de projetos em cima de modelagem de
problemas”
y “Seria oportuno e produtivo trabalhando com a realidade de cada região”
y “Sim... Sou professor, técnico em eletrotécnica, faço projetos elétricos. Agora vejo
que sempre lidei com grafos, pois os circuitos elétricos sempre são ramificados”
y “Grande valia em Educação Artística... Em tecelagens em cores variadas (pregos
trançando fios). Nada mais são do que grafos onde pregos são vértices, fios são arestas”
y “É o tipo de trabalho que estimula muito o raciocínio, a criatividade, e isso é
importante nos dias atuais, já que temos uma carência nesses aspectos”
y “Deveria ser aplicado a partir do 1o segmento do Ensino Fundamental, para que o
gosto e a prática da Matemática fosse constante desde a época da infância”
y “Pode ser abordado da 1a à 8a séries do Fundamental até o Ensino Médio, em
situações-problema, auxiliando-os a elaborar suas estratégias de raciocínio”
y “A partir da 5a série... Ensinaríamos grafos junto com o estudo do mapa do Brasil”
y
“Nunca tinha pensado em traduzir problemas dessa forma... Esse tema traria
reviravolta nessas séries”
y
“Como probabilidade e estatística, o tema dá oportunidade da realização de
problemas do dia-a-dia”
Depoimentos de alunos da 8ª série (escola pública, Cantagalo-RJ) no Estudo de
Caso da tese, e exatamente dos que, no início dos experimentos, haviam registrado
Matemática como a disciplina de seu menor interesse ou maior dificuldade
y “Gostei muito, foi um jeito muito melhor de aprender, estimula a querer aprender um
pouco mais”
y “A aula foi ótima! É muito fácil fazer os grafos”
Anais do VIII ENEM – Minicurso
GT 7 – Formação de Professores que Ensinam Matemática
5
y “A aula foi muito interessante, criativa, consegui entender melhor os enunciados das
questões”
y “Achei legal esse ensino mais fácil de entender”
O que é um grafo?
Problema 1: A figura 1 mostra diagrama representando (forma ou escala exatas não
importam) 9 estradas de certa região, onde A, B, C, D, E, F e G são cidades. Partindo de
A, e sabendo que tais estradas são de mão dupla (nos dois sentidos), é possível
visitarmos todas as outras cidades, sem repetirmos nenhuma, terminando tal viagem
rodoviária justamente na cidade de partida (não considere isto uma repetição)?
A
B
G
F
D
C
Figura 1
E
Modelagem/resolução: Basta-nos aqui rápida “inspeção visual” para chegarmos à
resposta... Possível!!! A ordenação ACEGBFDA nos dá roteiro de viagem que satisfaz
às exigências impostas pelo enunciado.
Conceitos em grafos: Ao que antes chamamos diagrama dizemos agora tratar-se de um
grafo. O grafo da figura 1, em particular, possui 7 vértices (representando as cidades A,
B, C, D, E, F e G) e 9 arestas (as estradas). Ao representarmos a situação-problema
dessa forma (enfatizamos: não são importantes forma ou comprimento das linhas que
expressam arestas), estamos fazendo modelagem em grafos da questão proposta,
concebendo um grafo-modelo à mesma. O leitor deve perceber que, certamente, já
desenhou grafos por inúmeras vezes em sua vida!!! Passemos a outros conceitos úteis e
bem simples... Diz-se que a aresta AB, por exemplo, é incidente nos vértices A e B;
uma seqüência “contínua” de arestas, do tipo CEGBF, é dita um percurso (conectando
os vértices C e F); grau de um vértice é o número de arestas nele incidentes (os vértices
Anais do VIII ENEM – Minicurso
GT 7 – Formação de Professores que Ensinam Matemática
6
A, B, C, D, E, F e G possuem graus, respectivamente, iguais a 3, 4, 3, 2, 2, 2 e 2). Há
generalizações do conceito de grafo que acabamos de apresentar: grafos com arestas
múltiplas (permitida a existência de mais de uma linha ligando dois vértices), digrafos
(grafos direcionados ou orientados; a cada linha é atribuído um sentido), grafos
valorados (a cada linha é atribuído um valor numérico). Assim, no Problema 1
(possivelmente, também, alterando ou acrescentando questões), o grafo-modelo seria
um digrafo caso algumas estradas fossem de mão única; um grafo com arestas múltiplas
seria utilizado se houvesse mais de uma estrada ligando duas cidades; um grafo
valorado seria escolhido se o problema levasse em consideração alguma valorização
quantitativa a atribuir-se a cada estrada (valor numérico representando distância, nível
de dificuldade ou risco de passagem por tal estrada, número de pontos turísticos
interessantes, etc).
O problema precursor do estudo dos grafos!!!
Os grafos vêm do século XVIII. A idéia de representarmos objetos através de
pontos (vértices) e, fixada determinada relação a ser satisfeita por alguns pares desses
objetos, sempre ligarmos dois vértices relacionados por meio de uma ou mais linhas
(arestas), isto é, a idéia original dos grafos, nasceu a partir de um problema precursor
(Euler, 1707-1783), que agora reproduzimos.
Problema 2: Havia um rio com duas ilhas A e B. Rotulando as duas margens do rio,
respectivamente, por C e D, tínhamos 7 pontes; uma ligando as ilhas A e B, duas de
A até a margem C, duas de A até a margem D, uma de B a C e a outra de B a D
(mapa na figura 2). Era possível, partindo-se de qualquer uma dessas quatro regiões,
margem ou ilha, atravessarmos as sete pontes sem repetirmos nenhuma?
Modelagem/resolução: O leitor não encontrará dificuldade de fazê-las (serão
imediatas!!!) após a leitura, por exemplo, da resolução do problema 4, explicada no
início da folha 5.
C
A
B
D
Figura 2
Anais do VIII ENEM – Minicurso
GT 7 – Formação de Professores que Ensinam Matemática
7
Dois exemplos de situações-problema com resolução por modelagem em grafos
Problema 3: João e Paulo são conhecidos um do outro, Ana, Dalva, Henrique e Paulo,
todos estes, conhecem-se entre si também. Mas Ana, Lucas e Maria, dentre estas três
pessoas, nenhuma conhece as outras duas. Já Lucas e João conheceram-se há muito
tempo numa excursão da escola, tornando-se até grandes amigos. Aproveitando os
pontos assinalados na figura 3 (cada ponto representa uma dessas pessoas, levando a
letra inicial de seu nome), obtenha o grafo que modela a situação descrita ligando dois
pontos somente quando estes representarem pessoas que se conhecem. Feito isto, e
apenas visualizando o grafo-modelo obtido, responda: (a) Dentre estas, qual a mais
“popular”, isto é, a que conhece e é conhecida por mais pessoas desse grupo?; (b) E qual
a pessoa mais “deslocada” no grupo? Observação: note-se que, para cada pessoa X, o
número de outras que ela conhece e pelas mesmas é conhecida será, evidentemente, o
grau do vértice que a representa no grafo-modelo obtido.
P
J
M
A
Figura 3
D
L
H
Problema 4: Um carteiro, deslocado para trabalhar noutra região (figura 4) da cidade,
quer descobrir percurso para entrega da correspondência diária em que, saindo do posto
dos Correios, passe por todas as ruas, nunca passe por trecho de rua pelo qual já tenha
passado e, quando da entrega pela última rua, já esteja voltando ao posto inicial. Para tal
região, isto é possível?
Posto dos Correios )
Figura 4
Anais do VIII ENEM – Minicurso
GT 7 – Formação de Professores que Ensinam Matemática
8
Modelagem/resolução: Com esquinas representadas por vértices, e cada trecho (entre
duas esquinas) de rua por uma aresta, a figura 5 nos dá o grafo-modelo do problema.
H
A
O ponto A está
G
F
representando o
posto dos Correios
Figura 5
B
C
D
E
Desta vez, no entanto, para resolver o Problema 4 com base em seu grafo-modelo,
vamos recorrer a um resultado da Teoria dos Grafos, bastante simples de aplicar-se por
sinal: Existe percurso que passa por todas as arestas de um grafo sem repetir nenhuma
se, e somente se, o grafo possui todos os vértices de grau par ou exatamente dois
vértices de grau ímpar; no primeiro caso, os vértices inicial e final do percurso
coincidem; no segundo, os vértices de grau ímpar são os inicial e final do percurso.
Com este resultado, passa a ser imediata a
Resposta ao Problema 4: Em seu grafo-modelo (figura 5), os graus de todos os vértices
são pares! Portanto, a resposta é “Sim”... Para sua nova região, é possível um percurso
como quer o carteiro.
Voltando ao problema 2 precursor dos grafos (final da página 3), e concebendo o
grafo-modelo com cada margem ou ilha sendo representada por um vértice, e com uma
aresta para cada ponte, conclui-se a resposta “Impossível”!!! Aliás, em tal grafo, chega
até a ocorrer todos os vértices terem grau ímpar.
Algumas contribuições importantes dos grafos para a Educação Básica:
• Representação do conhecimento em geral e forte exercício da modelagem matemática
• Ambiente propício para didática por resolução de problemas, jogos...
• Reconhecimento de estruturas similares de situações-problema em contextos distintos
• Transporte de estratégias de pensamento em situações-problema de estruturas
similares
Anais do VIII ENEM – Minicurso
GT 7 – Formação de Professores que Ensinam Matemática
9
• Desenvolvimento da organização do raciocínio, raciocínio lógico...
• Priorização do “ato de pensar” em vez de decorar, repetir, condicionar-se
• Desenvolvimento da capacidade do aprender a aprender (o novo), rumo à autonomia
• Boas possibilidades de abordagens computacionais (opcional), adeqüáveis a várias
faixas etárias
• Interdisciplinaridade, transversalidade e contextualização
• Maior poder de atração da Matemática sobre os educandos em geral,
independentemente das “áreas” ou matérias em que se concentrem seus maiores
interesses ou afinidades
• Matemática para não (necessariamente) matemáticos... Matemática para todos!!!
Grafos aplicam-se muito à modelagem de situações-problema em jogos!!!
Problema 5: Apenas com as pedras 0-1, 0-3, 0-6, 1-1, 1-2, 1-4, 2-3, 3-3, 3-4, 3-6, 4-4,
4-5, 4-6 e 5-6 de um dominó, é possível dispô-las seqüencialmente da forma usual em
tal jogo? Se possível, qualquer seqüência-resposta seria, evidentemente, do tipo
expresso na figura 6, não necessariamente na ordem em que na mesma estão sendo
vistas. Caso sua resposta seja “SIM”, registre ainda que números estariam ocupando as
extremidades (isto é, qual o primeiro número da primeira pedra e o último da última
pedra) de uma possível seqüência-resposta.
?
... ... ...
?
Figura 6
Estratégia inicial simplificadora da modelagem e resolução: Desconsiderar pedras de
números repetidos (1-1, 3-3 e 4-4). Claro que, uma vez achada uma possível seqüênciaresposta com as outras pedras, bastará depois inserir as três pedras inicialmente retiradas
em posições adeqüadas, como se vê feito com a pedra 1-1 na figura 6. Assumindo já tal
estratégia, então (sem as pedras 1-1, 3-3 e 4-4), passemos à
Anais do VIII ENEM – Minicurso
GT 7 – Formação de Professores que Ensinam Matemática
10
Modelagem/resolução: Tomemos como vértices 0, 1, 2, 3, 4, 5 e 6 (são todos os
números do dominó!) e, como arestas, somente as conexões (ligações entre vértices) 01,
03, 06, 12, 14, 23, 34, 36, 45, 46 e 56 que correspondem, precisamente, a todas as
pedras disponíveis, assim obtendo o grafo-modelo da figura 7.
O leitor não deve estar
tendo dificuldades para notar que a questão original prática “existe uma seqüênciaresposta possível num jogo de dominó estando disponíveis apenas tais pedras?” traduzse, à linguagem dos grafos, como “o grafo-modelo da figura 7 possui algum percurso
que passe por todas as arestas sem repetição de nenhuma?”. Mas tal grafo possui só os
vértices 0 e 1 com grau ímpar!!! Ainda pelo resultado do início desta folha, portanto,
este grafo admite tal percurso (desde que se inicie em 0 e termine em 1, ou vice-versa)...
Por exemplo, o percurso 12345036410 (acompanhe-o na figura 7) que, agora traduzido
de volta à “linguagem do dominó”, expressa-se como na figura 8, já incluídas ao final as
três pedras 1-1, 3-3 e 4-4 inicialmente retiradas... Resposta final: SIM, é possível!!!
4
5
3
Figura 7
2
6
0
1
Figura 8
• Atenção... Importante!!! → No problema 11 da lista que se segue, finalizando este
texto, para mostrar que é possível “fechar” (entenda bem o sentido deste “fechar”!!!) o
jogo de dominó completo, proceda rigorosamente segundo a estratégia de modelagem
que acabamos de utilizar. O grafo-modelo obtido, no entanto, terá todos os seus vértices
Anais do VIII ENEM – Minicurso
GT 7 – Formação de Professores que Ensinam Matemática
11
com grau par e, assim, pelo mesmo resultado de que já nos valemos, existirá um tal
percurso-resposta sem repetição de nenhuma aresta... Só que, desta vez, em tal percurso,
volta-se ao vértice inicial de partida, que é exatamente o que faz com que se possa, não
só montar seqüencialmente todo o conjunto das pedras mas, além disso, fazê-lo de
forma a “fechá-lo”, isto é, pondo-se a extremidade final da última pedra encostada na
extremidade inicial da primeira pedra.
Enunciados de alguns outros problemas modeláveis em grafos
(no Problema 10, o famoso resultado conhecido como o Teorema das 4 Cores)
6. Sonhos, Acordados, Bem Querer e Felicidade são cidades de país bem próximo.
Duas das estradas existentes levam-nos de Sonhos a Acordados, cinco de Acordados a
Bem Querer e três de Bem Querer à Felicidade. De quantos modos podemos ir de
Sonhos à Felicidade?
7. Quer-se oferecer em congresso minicursos M1, M2, M3, M4, M5, M6, M7. A cada
dia, sessões de todos os minicursos, cada um em horário fixo: 8:00/9:30, 9:30/11:00,
11:00/12:30, 14:30/16:00 ou 16:00/17:30 horas. Não devem coincidir horário: M1 com
M3, M4, M6 e M7; M2 com M3, M5 e M7; M3 com M1, M2, M5, M6 e M7; M4 com
M1, M5, M6 e M7; M5 com M2, M3, M4 e M7; M6 com M1, M3 e M4; M7 com M1,
M2, M3, M4 e M5. Todos os minicursos podem ser oferecidos? Qual é o número
mínimo de horários fixos para minicursos? Exiba quadro de horários com tal mínimo.
8. Versos do grande poeta brasileiro Carlos Drummond de Andrade: “João amava
Teresa, que amava Raimundo, que amava Maria, que amava Joaquim, que amava Lili,
que não amava ninguém …”. Represente graficamente (modelagem em grafos!!!) a
situação descrita.
9. O problema das 3 casas e dos 3 serviços: Se temos três casas I, II e III e três fontes
de serviço E (eletricidade), G (gás) e A (água), é possível levar todos estes serviços às
três casas satisfazendo-se simultaneamente as três condições que se seguem?...
Condições: (a) para cada casa, um tubo de cada serviço; (b) tais nove tubos passando
todos abaixo do chão; (c) não haver nenhum cruzamento entre dois tubos, nem mesmo
em níveis diferentes de profundidade (um abaixo do outro).
10. Dado qualquer mapa de país com 6 regiões (estados, por exemplo), de quantos
modos podemos colori-las com 5 cores disponíveis de forma que regiões vizinhas nunca
levem a mesma cor? Para todo mapa (sejam quantas forem suas regiões componentes),
Anais do VIII ENEM – Minicurso
GT 7 – Formação de Professores que Ensinam Matemática
12
qual o número de cores com que, garantidamente, podemos colori-lo obedecendo à
restrição citada? Como resposta a esta última questão, enunciamos agora o famoso
Teorema das 4 Cores: todo mapa (sejam quantas forem suas regiões componentes!!!)
pode ser colorido com, no máximo, 4 cores, de modo que regiões com fronteira entre si
levem cores diferentes.
11. É possível “fechar” o jogo de dominó completo, isto é, dispor todas as suas pedras,
como usualmente, coincidindo o último número da última pedra com o primeiro da
primeira pedra?
Palavras-chaves
1. Grafos
2. Modelagem
3. Interdisciplinaridade
Sobre bibliografia sugerida
Extensa listagem de bibliografia recomendada será distribuída aos participantes
por ocasião da própria dinamização do minicurso, não tendo nenhuma obra sido aqui
incluída em possível lista de Referências Bibliográficas simplesmente pelo fato de
propositadamente não terem sido feitas, ao longo do presente texto, citações e/ou
indicações em número suficiente e/ou em forma padrão, por opção do próprio autor. A
vasta bibliografia recomendada a ser divulgada oportunamente incluirá, de forma
predominante, obras nas seguintes linhas ou relacionáveis aos seguintes contextos:
•
grafos (teoria e/ou aplicações)
•
modelagem no ensino
•
interdisciplinaridade, transversalidade e contextualização
•
resolução de problemas
•
jogos
•
legislação educacional brasileira (LDB, PCN...)
•
outros tópicos (de aplicação específica) em Educação Matemática
•
Educação em geral (textos selecionados “tipo referenciais” para este trabalho)