7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
1/119
Fabio dos Santos GonalvesRoberto Reis de Oliveira Rossi
Introduo ao Ensino de Grafos na Educao Bsica
Barra Mansa - RJ, Brasil
07 de dezembro de 2007
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
2/119
Fabio dos Santos GonalvesRoberto Reis de Oliveira Rossi
Introduo ao Ensino de Grafos na Educao Bsica
Monografia apresentada para obteno do Graude Licenciatura em Matemtica pelo CentroUniversitrio de Barra Mansa, UBM, do Rio deJaneiro.
Orientador:Professor Dr. Ladrio da Silva
CURSO DEMATEMTICAUBM
CENTROUNIVERSITRIO DEBARRAMANSA
Barra Mansa - RJ, Brasil
07 de dezembro de 2007
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
3/119
Monografia do Curso de Matemtica sob o ttulo Introduo ao Ensino de Grafos na Edu-
cao Bsica, defendida por Fabio dos Santos Gonalves e Roberto Reis de Oliveira Rossi,
aprovada em 07 de dezembro de 2007, em Barra Mansa, Estado do Rio de Janeiro, pela banca
examinadora constituda pelos professores:
Prof. Dr. Ladrio da SilvaOrientador
Prof. Msc. Mauro Csar de Melo BaptistaCentro Universitrio de Barra Mansa
Prof. Msc. Laurentino Duodcimo RosadoFernandes
Centro Universitrio de Barra Mansa
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
4/119
Dedicamos esse trabalho aos professores, pais e familia-
res, pela credibilidade, pacincia, confiana e, acima de
tudo, o carinho que nos demonstraram ao longo dessa
rdua caminhada.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
5/119
Agradecimentos
Agradecemos a todos aqueles que estiveram ao nosso lado ao longo dessa caminhada.
A coordenadora do nosso curso, Jaqueline, por todos seus esforos para elevar o nvel do
curso de Matemtica.
Ao professor Ladrio, pela grande amizade e por todo incentivo que nos deu ao logo do
curso.
Aos professores Carlos, Clayton, Luis Antnio, Lda, Lcia e Andr, por todos ensinamento
que nos transmitiram.
Aos professores Ansio e Gernimo, e as professoras Beatriz, Evane, Florncia, Danielle e
Flordlia, por sua significante passagem em nossas vidas.
Aos professores Mauro e Du pelo interesse e participao em nossa banca de avaliao.
A professora Lurdinha, por toda a experincia de vida que nos passou, nos mostrando o
verdadeiro sentido da vida de um educador.
E, acima de tudo, a Deus que nos levantou em todos os momentos que camos.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
6/119
A preocupao com o prprio homem e seu destino deve
constituir sempre o interesse principal de todos os esfor-
os tcnicos... Nunca se esqueam disso em seus diagra-
mas e equaes.
Albert Einstein
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
7/119
Resumo
GONALVES, Fabio dos Santos; ROSSI, Roberto Reis de Oliveira. Introduo ao Ensinode Grafos na Educao Bsica. 2007, 117 pginas. Monografia (Licenciatura em Matemtica):Centro Universitrio de Barra Mansa - UBM, Barra Mansa, 2007.
A Teoria dos Grafos vem se mostrando, ao longo dos anos, como uma importante ferramentana resoluo de problemas, em diversas reas do conhecimento como por exemplo Matemtica,Fsica, Biologia, Logstica, Relaes Humanas e Computao.Desde o Problema das Sete Pontes, muitas descobertas foram realizadas no mbito da Teoria dosGrafos e, conseqentemente, a cada dia surgem mais aplicaes e problemas onde essa teoriapode ser utilizada. Apesar de no ser uma idia nova, relativamente novo o crescente interessepela utilizao da Teoria dos Grafos dentro da educao.Esse trabalho tem o objetivo de sugerir o uso da Teoria dos Grafos na Educao Bsica, abran-gendo o Ensino Fundamental e Ensino Mdio, como ferramenta de auxlio para o ensino daMatemtica. Com esse intuito aplicamos oficinas no Ensino Fundamental e Ensino Mdio e ve-
rificamos alguns benefcios citados por outros autores, os quais mostram que a Teoria dos Grafostraz enormes vantagens para o ensino de matemtica. A utilizao da Teoria dos Grafos destacaa transversalidade e a valorizao do cotidiano do aluno no ensino, requisitos bsicos do PCN.
PALAVRAS CHAVE:Teoria dos Grafos. Matemtica. Educao Bsica.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
8/119
Abstract
GONALVES, Fabio dos Santos; ROSSI, Roberto Reis de Oliveira. Introduction at Te-aching of Graph in Basic Education. 2007, 117 pages. Monograph (Mathematic Licentiate):Center University of Barra Mansa - UBM, Barra Mansa, 2007.
The Graph Theory has been showing, along the years, as an important tool in problems reso-lution, in several areas of acknowledge as Mathematics, Physics, Biology, Logistics, HumanResources and Computer Science.Since the Seven Bridges Problem, many discoveries were achieved in the scope of the GraphTheory and, consequently, each day arise more applications and problems where this theory hasbeen used. Despite of not being a new idea, it is relatively new the crescent interest by the utili-zation of the Graph Theory inside education.This work has the subject to suggest the use of the Graph Theory inside Basic Education, sincethe Fundamental School and High School, as an auxiliary tool for the teaching of Mathematicslearning. With this intention we apply workshops in Basic Education and High School and verify
some benefits cited for other authors, which they show that the Graph Theory brings enormousadvantages for education of mathematics. The use of the Graph Theory detaches the transversa-lity and the valuation of the daily one of the pupil in education, basics requirements of the PCN.
KEYWORDS:Graph Teory. Mathematic. Basic Education.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
9/119
Sumrio
Lista de Figuras
1 Introduo 17
1.1 Objetivo deste trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2 Estrutura da monografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 A Histria da Teoria dos Grafos 20
3 Grafos - Conceitos e Definies 24
3.1 O que um grafo? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Grafo simples, no orientado . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.1 Terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Grafo Orientado ou Digrafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Definies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.5 Grafo Valorado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.6 Algumas Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.6.1 Grau dos Vrtices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
10/119
3.6.2 Grafos Completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.6.3 Circuitos e Ciclos em um Grafo . . . . . . . . . . . . . . . . . . . . . . 32
4 Representao de Grafos 33
4.1 Representao Matricial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1.1 Matriz de Adjacncia de um grafo simples . . . . . . . . . . . . . . . . . 33
4.1.2 Matriz de Adjacncia de um grafo direcionado . . . . . . . . . . . . . . 35
4.1.3 Matriz de Incidncia de um grafo simples . . . . . . . . . . . . . . . . . 36
4.1.4 Matriz de Incidncia de um grafo direcionado . . . . . . . . . . . . . . . 37
4.2 Representao atravs de listas . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2.1 Lista de Adjacncia para grafos simples . . . . . . . . . . . . . . . . . . 38
4.2.2 Lista de Adjacncia para grafos orientados . . . . . . . . . . . . . . . . 39
5 Grafos na Educao 41
5.1 O que diz Piaget? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.1.1 Operacional-Concreto . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.1.2 Operacional-Abstrato . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2 O que diz a Lei? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.2.1 O PCN, a LDB e as Orientaes Curriculares . . . . . . . . . . . . . . . 46
6 Relato da pesquisa 50
6.1 Oficina no Ensino Mdio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
11/119
6.2 Oficina no Ensino Fundamental . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
7 Concluso e Trabalhos Futuros 66
Referncias Bibliogrficas 68
Apndice A -- Atividades para o ensino fundamental 70
A.1 Os trs servios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
A.2 As sete pontes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
A.3 Passando o lpis apenas uma vez . . . . . . . . . . . . . . . . . . . . . . . . . . 75
A.4 Viajando pelo mundo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Apndice B -- Atividades para o ensino mdio 77
B.1 Caminho de custo mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
B.2 Representao matricial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
Apndice C -- Oficinas 81
Apndice D -- Testes Aplicados 98
Anexo A -- Questionrios e Depoimentos 104
Anexo B -- Fotos das Oficinas 116
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
12/119
Lista de Figuras
2.1 Representao da cidade de Konigsberg e as pontes. . . . . . . . . . . . . . . . . 21
3.1 Grafo representando o problema das sete pontes. . . . . . . . . . . . . . . . . . 25
3.2 Uma representao do grafo G da definio. . . . . . . . . . . . . . . . . . . . . 26
3.3 Exemplo do grafo no orientado da definio . . . . . . . . . . . . . . . . . . . 27
3.4 Exemplo do grafo orientado da definio. . . . . . . . . . . . . . . . . . . . . . 28
3.5 Representao do multigrafo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.6 Exemplo de um grafo 2 regular: todos os vrtices possuem grau 2. . . . . . . . 30
3.7 Exemplo de um grafo nulo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.8 Exemplo de um grafo completo de grau 4,K4. . . . . . . . . . . . . . . . . . . . 30
3.9 Exemplo de um grafo simples valorado. . . . . . . . . . . . . . . . . . . . . . . 31
4.1 Grafo para representao matricial. . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2 Grafo orientado para representao matricial. . . . . . . . . . . . . . . . . . . . 35
4.3 Grafo simples para representao da Matriz de Incidncia. . . . . . . . . . . . . 36
4.4 Grafo orientado para representao da Matriz de Incidncia. . . . . . . . . . . . 37
4.5 Grafo simples para representao da Lista de Adjacncia. . . . . . . . . . . . . . 39
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
13/119
4.6 Grafo orientado para representao da Lista de Adjacncia . . . . . . . . . . . . 39
6.1 Mapa utilizado na atividade: Buscando o Caminho de Custo Mnimo . . . . . . . 51
6.2 Grfico da 1a questo pr-teste: J estudou matriz em Matemtica ou em outra
disciplina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.3 Grfico da 2a questo pr-teste: J ouviu falar sobre a Teoria dos Grafos . . . . . 52
6.4 Grfico da 3a questo pr-teste: Conhece alguma funo para matrizes . . . . . . 53
6.5 Grfico da 4a questo pr-teste: J ouviu falar sobre algum dos assuntos . . . . . 53
6.6 Grfico da 5a questo pr-teste: Quais dos assuntos esto relacionados com a
Matemtica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.7 Grfico da 1a questo ps-teste: Conhece pelo menos uma aplicao para a Teo-
ria dos Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.8 Grfico da 3a
questo ps-teste: A Teoria dos Grafos tem alguma relevncia nocotidiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.9 Grfico da 4a questo ps-teste: Gostou da oficina . . . . . . . . . . . . . . . . . 56
6.10 Grfico da 5a questo ps-teste: Problema mais interessante . . . . . . . . . . . 57
6.11 Oficina OEF001 - 6a srie do Ensino Fundamental . . . . . . . . . . . . . . . . 58
6.12 Oficinas OEF001 e OEF002 - aplicadas num evento livre . . . . . . . . . . . . . 59
6.13 Grfico da 1a questo oficna em sala: Gostou da oficina . . . . . . . . . . . . . . 60
6.14 Grfico da 2a questo oficna em sala: Fez atividades semelhantes a essa oficina . 60
6.15 Grfico da 3a questo oficna em sala: Atividade que mais gostou . . . . . . . . . 61
6.16 Grfico da 4a questo oficna em sala: Gosta das aulas tradicionais de Matemtica 61
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
14/119
6.17 Grfico da 5a questo oficna em sala: Mais oficinas como essa no ensino da
Matemtica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.18 Grfico da 1a questo evento livre: Gostou da oficina . . . . . . . . . . . . . . . 62
6.19 Grfico da 2a questo evento livre: Fez atividades semelhantes a essa oficina . . . 63
6.20 Grfico da 3a questo evento livre: Atividade que mais gostou . . . . . . . . . . 63
6.21 Grfico da 4a questo evento livre: Gosta das aulas tradicionais de Matemtica . 64
6.22 Grfico da 5a questo evento livre: Consegue ver relao do contedo no cotidiano 64
C.1 OEF001 - Pg. 01 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
C.2 OEF001 - Pg. 02 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
C.3 OEF001 - Pg. 03 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
C.4 OEF001 - Pg. 04 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
C.5 OEF002 - Pg. 01 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
C.6 OEF002 - Pg. 02 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
C.7 OEM001 - Pg. 01 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
C.8 OEM001 - Pg. 02 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
C.9 OEM001 - Pg. 03 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
C.10 OEM001 - Pg. 04 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
C.11 OEM001 - Pg. 05 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
C.12 OEM001 - Anexo - Pg. 01 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
C.13 OEM001 - Anexo - Pg. 02 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
15/119
C.14 OEM001 - Anexo - Pg. 03 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
C.15 OEM001 - Anexo - Pg. 04 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
D.1 OEF001 - Questionrio - Pg. 01 . . . . . . . . . . . . . . . . . . . . . . . . . . 99
D.2 OEF002 - Questionrio - Pg. 01 . . . . . . . . . . . . . . . . . . . . . . . . . . 100
D.3 OEF001 e OEF002 - Questionrio - Pg. 01 . . . . . . . . . . . . . . . . . . . . 101
D.4 OEM001 - Pr-teste - Pg. 01 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
D.5 OEM001 - Ps-teste - Pg. 01 . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
A.1 Oficina: OEM001 - Ps-Teste respondido - 01 . . . . . . . . . . . . . . . . . . . 105
A.2 Oficina: OEM001 - Ps-Teste respondido - 02 . . . . . . . . . . . . . . . . . . . 106
A.3 Oficina: OEM001 - Ps-Teste respondido - 03 . . . . . . . . . . . . . . . . . . . 107
A.4 Oficina: OEM001 - Ps-Teste respondido - 04 . . . . . . . . . . . . . . . . . . . 108
A.5 Oficina: OEF001 - Questionrio: Jaqueline, 12 anos, 6a srie . . . . . . . . . . . 109
A.6 Oficina: OEF001 - Questionrio: Vanderson Alves, 13 anos, 6a srie . . . . . . . 110
A.7 Oficina: OEF001 e OEF002 - Questionrio: Ana Carolina, 14 anos, 8a srie . . . 111
A.8 Oficina: OEF001 e OEF002 - Questionrio: Alissani Amaral, 14 anos, 8a srie . 112
A.9 Oficina: OEF001 e OEF002 - Questionrio: Thassiana Pereira, 14 anos, 8a
srie . 113
A.10 Oficina: OEM001 - Depoimento: Aluno do curso de 3o ano - Processamento de
Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
A.11 Oficina: OEM001 - Depoimento: Aluno do curso de 3o ano - Processamento de
Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
16/119
A.12 Oficina: OEM001 - Depoimento: Aluno do curso de 3o ano - Processamento de
Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
A.13 Oficina: OEM001 - Depoimento: Aluno do curso de 3o ano - Processamento de
Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
A.14 Oficina: OEM001 - Depoimento: Aluno do curso de 3o ano - Processamento de
Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
A.15 Oficina: OEM001 - Depoimento: Aluno do curso de 3o ano - Processamento de
Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
A.16 Oficina: OEM001 - Depoimento: Aluno do curso de 3o ano - Processamento de
Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
A.17 Oficina: OEM001 - Depoimento: Aluno do curso de 3o ano - Processamento de
Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
A.18 Oficina: OEM001 - Depoimento: Aluno do curso de 3o ano - Processamento de
Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
B.1 Entrada do Colgio Delci Horta, onde foram aplicadas duas oficinas . . . . . . . 116
B.2 Aplicao da oficina OEM001, para alunos da 6a srie . . . . . . . . . . . . . . 116
B.3 Alunos da 6a srie realizando a oficina . . . . . . . . . . . . . . . . . . . . . . . 117
B.4 Aplicao da oficina OEM001 e OEM002 para alunos do ensino fundamental . . 117
B.5 Acadmicos aplicando as oficinas . . . . . . . . . . . . . . . . . . . . . . . . . 117
B.6 Alunos do ensino fundamental participando das oficinas . . . . . . . . . . . . . . 118
B.7 Demonstrao dos mapas utilizados na atividade de Busca do Caminho Mnimo . 118
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
17/119
B.8 Professores do UBM e alunos da oitava srie do colgio Delci Horta . . . . . . . 118
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
18/119
17
1 Introduo
A sociedade humana evolui constantemente, da produo de alimentos at as viagens es-
paciais. O surgimento de novas formas de tecnologia como os computadores e a Internet tem
provocado uma profunda mudana no nosso meio de vida. Novos valores e conceitos surgem
todos os dias, enquanto outros so esquecidos e caem em desuso. Praticamente todas as reas da
sociedade evoluem, ao mesmo tempo, para se adaptar as rpidas mudanas. Porm, dentre essas
diversas reas, existe uma que parece ser a mais resistente a essas mudanas. E essa rea deve-
ria, ao contrrio, ser aquela que mais facilmente se adaptaria s constantes mudanas, pois ela
exatamente a rea responsvel pela maior parte da formao da sociedade e de seus indivduos.
Essa rea a da Educao.
Justamente por ser uma rea que prepara o indivduo para sua vida no meio social, a educao
precisa constantemente se ajustar s novas tecnologias, s inovaes da sociedade. Exatamente
pensando nessas necessidades que esse trabalho vem propor a introduo de um novo saber no
contedo da educao bsica, a Teoria dos Grafos.
A Teoria dos Grafos surgiu por volta de 1700 e, desde ento, vem passando por profundas
mudanas. Cada vez mais problemas so explorados do ponto de vista da Teoria dos Grafos.
Desde o problema que originou tal teoria, o Problema das Sete Pontes, muito tem se discutido
sobre a Teoria dos Grafos e suas aplicaes. Hoje em dia ela est presente em vrias reas do
conhecimento humano. Da biologia logstica, da fsica computao, das relaes humanas
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
19/119
1.1 Objetivo deste trabalho 18
navegao, cada vez mais a Teoria dos Grafos aparece como ferramenta de auxlio para a
resoluo de vrios problemas existentes nessas reas.
Na educao, pelo menos no Brasil, isso no acontece com tanta freqncia. Pouco tem se
falado sobre a utilizao dos seus conceitos nas diversas fases da vida escolar dos estudantes.
Mesmo se mostrando extremamente til, comum ver professores que desconhecem parte ou
totalmente a Teoria dos Grafos, chegando ao ponto extremo de confundir a palavra grafo com
grfico. Apesar de no existirem muitos esforos direcionados para a aplicao da Teoria dos
Grafos na educao, parece que os poucos esforos tm, agora, comeado a dar resultado. Umaprova disso um recente documento, publicado pelo MEC (Ministrio da Educao e Cultura),
que sugere, pela primeira vez, a utilizao de grafos na educao (EDUCAO, 2006).
1.1 Objetivo deste trabalho
O objetivo do trabalho exatamente propor a utilizao da Teoria dos Grafos no ensino
mdio e fundamental, ora ligando-a outros contedos como ferramenta de auxlio, ora apenas
incentivando a investigao dos vrios problemas tratados por essa teoria para os alunos. Espe-
ramos, com isso, contribuir com uma parcela mnima para uma melhor formao do cidado,
dando a esse mais opes e facilitando sua prtica da cidadania.
1.2 Estrutura da monografia
No captulo 2 apresentada uma pequena parte histrica da Teoria dos Grafos, citando alguns
de seus famosos problemas.
No captulo 3 sero apresentados os elementos mais comuns dos grafos assim como os prin-
cipais conceitos dessa teoria.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
20/119
1.2 Estrutura da monografia 19
No captulo 4 sero mostradas algumas formas de representao dos grafos.
No captulo 5 apresetado os aspectos que ligam a Teoria dos Grafos educao, mensio-nando as idias de Piaget e a fundamentao da lei para essa prtica.
No captulo 6 sero relatadas as as pesquisas de campo realizadas, levantando os aspectos
positivos e negativos de cada experincia, alm dos resultados obtidos.
Por fim, no captulo 7 ser apresentado um balano geral do trabalho, exibindo os aspectos
positivos e negativos das prticas sugeridas e o planejamento para os trabalhos futuros dentro
desse tema.
Nos apndices, sero descritas as oficinas e atividades sugeridas para a prtica da Teoria dos
Grafos no ensino fundamental e mdio, que podero servir de modelo para outras pesquisas.
Os anexos iro conter fotos, testes e depoimentos dos alunos referentes as atividades reali-
zadas.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
21/119
20
2 A Histria da Teoria dos Grafos
Considera-se que a Teoria dos Grafos surgiu no sculo XVIII (PENHA, 1983, pp. XX),
quando Leonhard Euler interpretou e deu uma soluo para o problema das sete pontes de K-
nigsberg (atual Kaliningrado na Russia). Nessa cidade, que era cortada pelo rio Pregel, existiam
duas ilhas que eram interligadas entre si por uma ponte e com as margens por seis outras pontes
(quatro em uma ilha e duas na outra). No demorou muito para que os habitantes mais ob-
servadores da cidade, e acostumados a passear por toda a cidade atravessando suas pontes, se
perguntassem: "existe um percurso no qual se possa percorrer toda a cidade, atravessando todas
as suas pontes, mas sem repetir nenhuma dessas pontes?". Ou seja, partindo de um ponto da
cidade, possvel passar por todas as pontes uma nica vez e voltar ao ponto de origem? Euler
provou que tal fato s seria possvel se cada uma destas reas possusse um nmero par de pontes
partindo dela. Segue uma representao da cidade destacando as pontes:
Euler enunciou seu teorema em trs regras:
Se h mais de duas reas s quais leva um nmero mpar de pontes, ento taljornada impossvel. Se entretanto, o nmero de pontes mpar para exatamenteduas reas, ento esta jornada possvel se comear em qualquer dessas reas.Se, finalmente, no existem reas s quais levam um nmero mpar de pontes,ento a jornada requerida pode ser realizada iniciando-a a partir de qualquerrea.(PENHA, 1983)
Nos dias atuais, chama-se de circuito de Euler ou Caminho Euleriano todos os grafos que
possuem tal caracterstica. O problema das sete pontes de Koningsberg formulado por Euler,
considerado tambm um dos primeiros resultados topolgicos na geometria, pois no depende
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
22/119
2 A Histria da Teoria dos Grafos 21
Figura 2.1: Representao da cidade de Konigsberg e as pontes.
de qualquer medida. Com isso, ilustra-se a profunda conexo entre a Teoria dos Grafos e a
Topologia1 (PENHA, 1983).
Outro matemtico que se destacou na Teoria dos Grafos foi Willian Rowan Hamilton que
em 1859 props um jogo que mas tarde ficaria famoso. Consistia em um dodecaedro planificado
e tinha como objetivo, passar uma nica vez por cada vrtice da figura. Esta caracterstica, que
algumas representaes de grafos possuam, ficou conhecida como ciclo Hamiltoniano. Todo
grafo que possui tal caracterstica chamado de grafo hamiltoniano (SANTOS et al., 1998).
Pode-se destacar ainda, Kirchhoff que, em 1847, utilizou grafos para estudo de circuitos eltricos
e Arthur Cayley matemtico ingls que, em 1857, fazia pesquisas na rea de qumica orgnica.
Ambos foram os precursores do conceito de rvore em grafos, que consiste em um grafo com um
nico caminho entre suas extremidades (FREITAS, 2007). Ao longo da histria da matemtica,
1Do gregotopos, forma, elogos, estudo - "estudo das formas", uma parte da matemtica que estuda as proprie-dades geomtricas que no variam mediante uma deformao, A definio da topologia explicita os relacionamentosespaciais entre os objetos atravs de um processo matemtico (INPE, 2007)
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
23/119
2 A Histria da Teoria dos Grafos 22
surgiram vrios outros problemas clssicos relacionados a teoria dos grafos, segue-se a definio
de dois deles:
Problema da Colorao de Mapas ou Problema das Quatro Cores- Surgiu em 1852
quando Francis Guthrie, um estudante Ingls de direito, perguntou a seu irmo Frederick,
estudante de Matemtica, quantas cores eram necessrias para colorir um mapa sem que
pases com fronteiras em comum tivessem cores iguais. Francis j havia realizado alguns
testes e achava que quatro cores seriam suficientes. Frederick levou ento o problema ao
conhecido matemtico Augustus De Morgan, que foi que enunciou matematicamente o
problema, chamando-o de Conjectura de Gunthrie. Apesar disso, De Morgam no con-
seguiu resolver o problema e o enviou a Hamilton, que tambm no conseguiu encontrar
a soluo. A partir desse fato, o problema se tornou um dos mais famosos da histria da
Matemtica. Vrios matemticos, ao longo desses anos, tentaram resolver sem sucesso
o problema das quatro cores, dentre eles pode-se destacar: Herman Minkowski, que foi
professor de Eistein, Alfred Kempe, que tambm era um advogado apaixonado por Ma-
temtica e que, em 1879, publicou um teorema chamado Mtodo das Correntes, que
chegou a ser comemorado como a soluo para a Conjectura de Gunthrie, porm, alguns
anos mais tarde, foram encontrados erros no teorema, erros estes que Kempe no con-
seguiu resolver. Mas foram os matemticos Kenneth Appel e Wolfgang Haken que, 124
anos depois da enunciao do problema, resolveram a Conjectura de Gunthrie com o uso
intenso de computao, mtodo esse que no muito bem aceito pelos matemticos mais
puristas (Seara da cincia, 2007).
Problema do Carteiro Chins- que partiu de uma questo levantada pelo matemtico
chins Mei-Ko Kwan, baseada no Problema das Sete Pontes de Euler, que dizia: Dado
que impossvel atravessar cada ponte exatamente uma vez e retornar para o ponto de
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
24/119
2 A Histria da Teoria dos Grafos 23
partida, qual o nmero mnimo de travessias redundantes que preciso fazer?. Kwan
desenvolveu um teorema em que os arcos do grafo representavam trechos de ruas que um
carteiro deveria percorrer para entregar as cartas e o carteiro deveria percorrer estas ruas
(arcos) com o menor esforo possvel, ou seja, que a distncia percorrida para entregar tais
cartas seja a mnima possvel.
Existem outras variaes deste problema como o Problema do Caixeiro Viajante e o Pro-
blema do Caminho de Custo Mnimo (FREITAS, 2007).
A Teoria dos Grafos foi considerada por muito tempo uma rea morta da Matemtica. Pode-
se citar com exemplo, o fato de o primeiro livro sobre o assunto s ter sido publicado em 1936,
e s tomou fora realmente nos anos 50, com o surgimento da Computao, uma rea que uti-
liza intensamente a Teoria dos Grafos, desde o funcionamento bsico de um computador at o
desenvolvimento de complexos algoritimos, como desenvolvimento de jogos. Em contrapartida,
a computao tambm ajudou muito a Teoria dos Grafos, processando clculos para a resoluo
de alguns complexos problemas, como por exemplo o da colorao de mapas. O ano de 1969,
foi um marco importante para a teoria dos grafos, quando foram publicados cerca de 500 artigos
sobre o tema, que totalizaram cerca de 2000 referncias e que fizeram surgir vrias publicaes
sobre o assunto, como o livro "Reviews of graph theory (Reviso sobre teoria dos grafos), publi-
cado no inicio dos anos 90 contendo um resumo de trabalhos publicados at o final da dcada de
80 (NASCIMENTO; SILVA, 2007).
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
25/119
24
3 Grafos - Conceitos e Definies
3.1 O que um grafo?
Quando busca-se uma definio formal para um grafo, encontra-se em um grande problema:
no existe um padro para a nomeclatura da maioria dos elementos de um grafo. Por exemplo,
muito comum ver autores que utilizam a letraEpara definir as arestas (do inglsEdge). J
outros autores utilizam a letraA, para essa definio.
Um outro exemplo de confuso, quanto ao padro, a definio dos termosCaminho,Ciclo,
Circuitoe Trilha. Pode-se parecer uma coisa simples, mas essa situao gera grandes transtor-
nos quando se busca uma definio formal para um grafo, principalmente no entendimento de
conceitos mais profundos da teoria.
Devido a essa falta de padro, optou-se neste trabalho por utilizar a definies utilizadas
pela maioria das fontes pesquisadas.
A definio para um grafo, geralmente, costuma ser de difcil compreenso. Segundo Schei-nerman (SCHEINERMAN, 2004), a visualizao de uma situao problema onde a Teoria dos
Grafos pode ser utilizada, costuma ser de grande ajuda para facilitar o entendimento de uma
definio. Vejamos um exemplo disso. Imagine o problema que originou a Teoria dos Grafos,
"O Problema das Sete Pontes", que consiste, basicamente, em atravessar toda a cidade, passando
por todas as pontes, porm sem repetir nenhuma delas. A Figura abaixo, a representao na
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
26/119
3.1 O que um grafo? 25
forma de grafo mais clssica para este problema:
Figura 3.1: Grafo representando o problema das sete pontes.
Uma proposta de atividade para um exerccio como esse poderia ser, por exemplo, o de se
tentar contornar toda a figura sem tirar o lpis do papel, e sem repetir nenhum dos caminhos.
Isso no parece sem importncia? Agora imagine uma situao mais complexa, onde voc o
responsvel pelo recolhimento de lixo de uma pequena cidade. Essa cidade conta com apenas um
caminho de lixo, e possui vrias ruas para realizar o recolhimento. Definir uma melhor rota paraessa tarefa, a mais rpida, ou mais econmica, pode ser uma estratgia decisiva para a economia
e infra-estrutura dessa pequena cidade. Agora voc pode perceber melhor a importncia desse
"frvolo"problema? Segundo Scheinerman, uma definio formal para um grafo seria:um grafo
um par G = (V,E), ondeV um conjunto finito e E um conjunto de subconjuntos de
dois elementos deV.
Analise agora agora o exemplo abaixo, para compreender melhor essa definio:
G= ({1,2,3,4,5,6,7},{{1,2},{1,3},{2,3},{3,4},{5,6}})
Aqui,V um conjunto finito {1,2,3,4,5,6,7}e E um conjunto que contm cinco sub-
conjuntos de dois elementos de V:{1,2},{1,3},{2,3},{3,4},{5,6}. Portanto,G= (V,E) um
grafo.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
27/119
3.2 Grafo simples, no orientado 26
Veja agora, uma representao para o grafo G:
Figura 3.2: Uma representao do grafo G da definio.
No sero poucas as definies para grafo encontradas na literatura, alm disso, diferentes
tipos de Grafos recebem definies diferentes. Como a definio citada acima bem genrica,
vamos mostrar algumas definies mais especficas, para tipos de grafos diferentes. Neste traba-
lho, resolveu-se adotar as definies utilizadas pela professora PhD Fabola Gonalves Pereira
Greve, do Departamento de Cincia da Computao da Universidade Federal da Bahia.
3.2 Grafo simples, no orientado
Conforme Greve (GREVE, 2007), um grafo G(V,E) um conjunto finito no vazio Ve um
conjuntoEde pares no-orientados de elementos distintos deV, onde:
V um conjunto de vrtices;
E um conjunto de arestas;
Vejamos um exemplo de grafo para essa definio:
Notao:
1. Chamamos de|V|o nmero de vrtices representado por n, se n=|V|. E|E| o nmero
de arestas representado porm, isto m=|E|;
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
28/119
3.3 Grafo Orientado ou Digrafo 27
Figura 3.3: Exemplo do grafo no orientado da definio
2. Cada aresta e pertencente ao conjunto Eser denotada pelo par de vrtices (x,y) que a
forma. Dizemos que os vrticesxeyso extremos (ou extremidades) da aresta e.
3.2.1 Terminologia
interessante notar as seguintes terminologias:
Vrtices adjacentes - dois vrtices xe yso ditos adjacentes se existe uma aresta eos
unindo;
Vrtices incidentes- os vrticesuevso ditos incidentes na aresta e, se eles so extremos
dee;
Arestas adjacentes - duas arestas so adjacentes se elas tm ao menos um vrtice em
comum;
Arestas incidentes- a arestae= (x,y) incidente a ambos os vrticesxey;
3.3 Grafo Orientado ou Digrafo
Um digrafoD(V,A) um conjunto finito no vazioVe um conjuntoAde pares ordenados
de elementos deV. Ao conjuntoA, d-se o nome de arcos. (GREVE, 2007)
Chama-se arco de xpara yquando o primeiro elemento do par x e o segundo y. Um
exemplo para esta definio seria:
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
29/119
3.4 Definies 28
V={1,2,3,4}
A={(1,3),(1,4),(3,1)(3,2),(4,2)}.
Pode-se ver esse grafo na Figura 3.4.
Figura 3.4: Exemplo do grafo orientado da definio.
ATENO: importante notar aqui, que os segmentos que unem os vrtices nos grafos
no orientados recebem o nome dearestas(E), e os segmentos que unem os vrtices nos grafos
orientados recebem o nome dearcos(A).
3.4 Definies
Vamos ver algumas definies:
Lao- uma aresta formada por um par de vrtices idnticos;
OBS.: Para permitir uma aresta deste tipo (e= (x,x)) basta relaxar a definio de grafo(anterior) retirando a condio de serem elementos distintos.
Arestas mltiplas ou paralelas- quando existe mais de uma aresta entre o mesmo par de
vrtices.
OBS.:Para permitir uma aresta deste tipo basta substituir na definio anterior, o conjunto
de arestas por multiconjunto de arestas.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
30/119
3.4 Definies 29
Multigrafo- um grafo que permite a existncia de arestas mltiplas.
Exemplo:G: V= {1,2,3,4};E= {(1,1),(1,2), (1,3),(2,1),(2,3),(3,1),(3,2),(3,3)(3,4)}
Figura 3.5: Representao do multigrafo.
Grau de um vrtice- o grau de um vrtice v pertencente aV, denotado por grau(v) o
nmero de arestas que incidem emv, ou o nmero de vrtices adjacentes av;
OBS.:Um lao conta duas vezes para o grau de um vrtice. No grafo da Figura 3.5: Grau
V(1) =6.
Grau mximo e mnimo- o maior e o menor grau encontrado entre os vrtices de umgrafo. O grau mximo de um vrtice emGse denota por(G), e o grau mnimo de um
vrtice emG denotado por (G), (SCHEINERMAN, 2004, p.1);
Exemplo:No grafo da Figura 3.5: (G) =7 e (G) =1.
Vrtice isolado- qualquer vrtice de grau zero;
Vrtice terminal- qualquer vrtice de grau 1;
Exemplo:No grafo da Figura 3.5: V(4).
Grafo k-regular- segundo Abreu (ABREU, 2007), G chamadografo regular de grau
kouk-regularquando todos os vrtices deGtem o mesmo grau k;
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
31/119
3.5 Grafo Valorado 30
Figura 3.6: Exemplo de um grafo 2 regular: todos os vrtices possuem grau 2.
Grafo Nulo ou Vazio- De acordo com Abreu, um grafo nulo aquele onde o nmero de
arestas zero. Definimos esse grafo comoN4;
Exemplo: N4: V={A,B,C,D};E={}
Figura 3.7: Exemplo de um grafo nulo.
Grafo Completo- Ainda conforme Abreu, um grafo dito completo se quaisquer dois de
seus vrtices, distintos, so adjacentes. Para cadan >= 1, o grafo completo comnvrtices
denotado porKn.
Figura 3.8: Exemplo de um grafo completo de grau 4, K4.
3.5 Grafo Valorado
Tantos os grafos simples como os grafos direcionados podem ser, ou no, valorados. Se-
gundo Boaventura, (BOAVENTURA, 2006, pp. 11): "um grafo valoradosobre os vrtices,
quando existem uma ou mais funes relacionandoV(E)a conjuntos de nmeros."
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
32/119
3.6 Algumas Propriedades 31
Figura 3.9: Exemplo de um grafo simples valorado.
3.6 Algumas Propriedades
Analisando as informaes que existentes at agora, possvel perceber algumas proprieda-
des dos grafos
3.6.1 Grau dos Vrtices
A soma dos graus de todos os vrtices de um grafo sempre par. Veja um exemplo. dado
um grafoG= (V,E), Quando o grafo regular de grau k, temos:
vVG(V) =2|E|
vVG(V) =k|v| 2|E|=k|v| |E|= k|v|
2
3.6.2 Grafos Completo
Os grafos completos tambm possuem uma interessante caracterstica, segundo (GREVE,
2007): o nmero de arestas igual ao nmero de combinaes de nvrtices dois a dois.
Vejamos:
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
33/119
3.6 Algumas Propriedades 32
|E|= (kX|v|)
2
k o grau;
v o nmero de vrtices;
Assim:|E|= ((n1)n)
2
O que nos prova, que a afirmao acima verdadeira.
3.6.3 Circuitos e Ciclos em um Grafo
Um outro ponto que geralmente causa muita confuso, a definio para Ciclo e para Cir-
cuito. Isso acontece, porque tambm no existe uma padronizao desses termos. Dessa forma,
foi necessrio decidir qual definio seguir para a confeco das atividades sugeridas. Assim,
optou-se por utilizar as seguintes definies:
O trajeto percorrido em um Grafo pode recebe o nome de Ciclo(Caminho) ou Circuito(trilha).
OsCiclosno permitem repetio de vrtices, j os Circuitospermitem essa repetio. Em
nenhum dos casos pode existir uma repetio de arestas ou de arcos.
Os ciclos e circuitos so utilizados na maioria das atividades desenvolvidas ao longo deste
trabalho.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
34/119
33
4 Representao de Grafos
Devido a evoluo da informtica e dos computadores, cada vez mais a Teoria dos Gra-
fos tem sido tratada em cursos como Cincia da Computao e Sistemas de Informao. Alm
disso, devido a grade complexidade dos problemas que podem ser modelados na forma de gra-
fos, cada vez mais importante sua abordagem em cursos como os de Logstica e Engenharia.
Sendo assim, o desenvolvimento de aplicaes computacionais envolvendo a Teoria dos Grafos
tem se tornado muito comum. Mas afinal, como tratar um grafo atravs de uma aplicao com-
putacional. Existem vrias maneiras de se fazer isso, atravs de listas, matrizes, entre outras
formas.
4.1 Representao Matricial
Diversos so os tipos de matrizes que podem ser utilizadas para a modelagem de um grafo,
matriz de incidncia, matriz laplaciana, matriz de adjacncia, entre outras, porm iremos abordar
nesse trabalho apenas aMatriz de Adjacnciae aMatriz de Incidncia.
4.1.1 Matriz de Adjacncia de um grafo simples
Segundo (ABREU, 2007), a Matriz de Adjacncia a matriz de zeros e uns que se constri
naturalmente a partir das relaes de adjacncia entre os vrtices do grafo.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
35/119
4.1 Representao Matricial 34
Seja o grafoG(V,E)da prxima figura:
Figura 4.1: Grafo para representao matricial.
A representao dessa matriz de adjacncia seria:
M=
0 1 1 1 0 0 0
1 0 1 1 1 0 0
1 0 0 0 1 0 0
1 1 0 0 0 0 0
0 1 1 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 1
A matriz adjacncia M(G) = [ai j] ser uma matriz de |v| x |v| onde ai j o nmero de
arestas unindoviav j. Sendo assim, na matrizM, cada linha representa um vrtice e cada coluna
representa se existe ou no uma ligao, atravs de uma aresta, com outro vrtice, onde o valor
0 indica que no existe ligao e o valor 1 indica a existncia de uma ligao. Caso exista um
valor maior que 1, isso indicar o nmero de arestas existentes entre os vrtices em questo.
Vamos analisar algumas caractersticas dessa matriz:
1. Somatrio da coluna igual ao grau do vrtice (lao conta duas vezes);
2. Somatrio da linha igual ao grau do vrtice (lao conta duas vezes);
3. Se existirem apenas zero na diagonal principal, ento o grafo no possui lao;
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
36/119
4.1 Representao Matricial 35
4. Seai j >1, ento existem arestas mltiplas;
5. Se a linha e coluna do vrtice so nulos, ento o vrtice isolado;
6. A matriz simtricaai j=a ji, no caso do grafo ser simples;
7. A complexidade de espao |v|2;
4.1.2 Matriz de Adjacncia de um grafo direcionado
A representao de um grafo direcionado, tambm pode ser feita atravs de uma matriz de
adjacncia, porm a representao um pouco diferente. Vejamos no caso do seguinte grafo
direcionado.
Figura 4.2: Grafo orientado para representao matricial.
Agora vamos analisar sua matriz de adjacncia:
M=
0 1 1 0 0
0 0 0 1 0
0 1 0 0 10 0 0 0 1
0 0 0 0 0
Repare que na matriz de adjacncia do grafo direcionado acima, cada linha indica o vrtice,
e cada coluna representa o vrtice que recebe um arco, do vrtice relacionado. Uma maneira
simples para compreender isso seria imaginar que cada linha representa o vrtice de onde o arco
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
37/119
4.1 Representao Matricial 36
est partindo, e cada coluna representa o vrtice para o qual o arco aponta. Diferentemente da
matriz de adjacncia do grafo no orientado, a matriz de adjacncia do direcionado no ser
sempre simtrica.
4.1.3 Matriz de Incidncia de um grafo simples
Conforme podemos ver em (BOAVENTURA, 2006, pp. 14), a Matriz de Incidncia uma
matrizMde dimensesmxn, onde casa linha representa um vrtice e cada coluna representa uma
aresta ou arco.
Analisando o prximo grafo e sua Matriz de Incidncia, pode-se perceber a diferena com a
Matriz de Adjacncia:
Figura 4.3: Grafo simples para representao da Matriz de Incidncia.
M=
1 1 0 0 0 0
1 0 1 0 0 0
0 1 0 1 1 0
0 0 1 1 0 0
0 0 0 0 1 2
0 0 0 0 0 0
Assim como a Matriz de Adjacncia, a Matriz de Incidncia tambm apresenta algumas
caractersticas particulares
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
38/119
4.1 Representao Matricial 37
1. Somatrio da coluna igual a 2 (lao conta duas vezes);
2. Somatrio da linha igual ao grau do vrtice (lao conta duas vezes);
3. Se existirem duas colunas iguais, elas indicam arestas mltiplas;
4. Uma linha nula indica um vrtice isolado;
5. Mi j=2, indica um lao;
6. A complexidade de espao |v| x |e|, ou seja, ocupa mais espao do que a Matriz de
Adjacncia;
4.1.4 Matriz de Incidncia de um grafo direcionado
Assim como na representao pela Matriz de Adjacncia, a representao de um grafo dire-
cionado possui algumas caractersticas diferentes do grafo simples.
Figura 4.4: Grafo orientado para representao da Matriz de Incidncia.
Basicamente, a diferena da Matriz de Incidncia de um grafo direcionado para um no
direcionado que na representao da direo da seta, usa-se o valor +1 para indicar para onde
vai o arco, e o valor -1 para indicar de onde o arco vem. Veja a Matriz de Incidncia do grafo
acima:
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
39/119
4.2 Representao atravs de listas 38
M=
+1 +1 0 0 0
1 0 +1 0 0
0 1 0 +1 +1
0 0 1 1 0
0 0 0 0 1
As outras caractersticas permanecem as mesmas.
4.2 Representao atravs de listas
Conforme mensionado anteriormente, as matrizes no so as formas de representao de
um grafo. Vejamos agora como realizar a representao de um grafo atravs de uma Lista de
Adjacncia.
4.2.1 Lista de Adjacncia para grafos simples
Uma Lista de Adjacncia, ou Dicionrio, a mais conveniente, segundo Boaventura, devido
a simplicidade e sua economia de apresentao. Mesclando a definio de (GREVE, 2007) com
a de (BOAVENTURA, 2006), pode-se definir a Lista de Adjacncias LA(G)como sendo um
conjunto denlistasA(V), onde cada uma dessas listas formada por um vrtice e pelo conjunto
de vrtices que recebem dele um arco ou que partilham com ele uma aresta.
Veja um exemplo:
E aqui sua representao atravs da Lista de Adjacncia:
A(A)B Cnull
A(B)A Cnull
A(C)ABE null
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
40/119
4.2 Representao atravs de listas 39
Figura 4.5: Grafo simples para representao da Lista de Adjacncia.
A(D)null
A(E) CE null
Eis as caractersticas de uma Lista de Adjacncia:
1. O grau do vrtice ser o mesmo do nmero de elementos na lista A(V), exceto no caso de
lao, que ser contado como 2;
2. Se na lista de um vrtice existir o prprio vrtice, isso indica um lao;
3. Se na lista de um vrtice existirem elementos repetidos, isso indica arestas mltiplas;
4. Se na lista de um vrtice no existirem elementos, isso indica um vrtice isolado;
5. A complexidade de espao n + 2m, sendon=|v|em=|e|;
4.2.2 Lista de Adjacncia para grafos orientados
Como nas formas de representao anteriores, os digrafos tambm possuem uma diferena
quanto a sua representao, comparados com os grafos simples.
Figura 4.6: Grafo orientado para representao da Lista de Adjacncia
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
41/119
4.2 Representao atravs de listas 40
No caso dos digrafos, a lista ser composta pelos vrtices destinos do vrtice em questo.
AB Cnull
B Cnull
CDE null
Dnull
E null
Para os digrafos, a Lista de Adjacncia tambm poderia ser representada atravs de uma
tabela contendo os vrtices origem/destino, ou de destino/origem, porm no existe uma neces-sidade real de ilustrar aqui essa outra forma de representao.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
42/119
41
5 Grafos na Educao
Quando falamos de grafos aplicados educao, o assunto j no to vasto quanto sua
aplicao em outras reas do conhecimento, como computao e logstica. Muito pelo contrrio,
a literatura a respeito do assunto bem escassa. Poucos so os livros dedicados unicamente ao
tema, tanto em portugus quanto em outros idiomas.
Ao se propor a introduo da Teoria dos Grafos, como uma ferramenta dentro da educao
bsica, importante lembrar da importncia da mesma no ensino da Matemtica. Segundo o
professor Jorge Bria:
O ENSINO DA MATEMTICA deve ser concebido e ministrado de modo ATRAENTE
E PRODUTIVO PARA TODOS OS ESTUDANTES, independentemente de suas aptides natu-
rais, maiores afinidades ou vocaes profissionais (BRIA, 1999, pp. 32).
Bria tambm afirma que vrias situaes problemas do nosso cotidiano podem ser tratadas de
maneira simples pelos estudantes, o que seria uma justificativa a mais para a abordagem do tema,
tanto no ensino fundamental como no ensino mdio. Esses fatores poderiam explicar porque
vrios pases no mundo esto explorando a Teoria dos Grafos na educao bsica. Segundo Bria:
"...estejam os grafos j sendo explorados concretamente, ou em fase de pesquisaspara tal possvel explorao, no processo de formao bsica do cidado em al-gum nvel de ensino, em alguns pases como, por exemplo, Argentina, Portugal,Espanha, Alemanha e Estados Unidos."(BRIA, 1999, pp. 34)
Infelizmente o Brasil tem limitado o ensino da Teoria dos Grafos apenas ao ensino superior.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
43/119
5.1 O que diz Piaget? 42
Isto tem ocasionado diversas dificuldades com relao a introduo desse contedo na formao
bsica do indivduo, pois a maioria dos professores da educao bsica desconhece o contedo.
Aqueles poucos que conhecem, geralmente, s conhecem superficialmente. Talvez por isso seja
to comum as pessoas confudirem a palavra grafo com grfico.
5.1 O que diz Piaget?
Para fundamentar em qual fase do processo ensino/aprendizagem a Teoria dos Grafos poderia
ser aplicada, buscou-se amparo em Piaget e suas brilhantes observaes sobre os aspectos que
tangem a educao. Lembrando as palavras de Bria: Piaget inesgotvel!!! E isto evidencia-se
de forma realmente impressionante (BRIA, 1999)
Piaget viveu de 1896 a 1980, tornou-se doutor aos 22 anos. Mais tarde seria tido como
epistemlogo, psiclogo, filsofo, educador e pedagogo, alm de outras titulaes. Foge do ob-
jetivo deste trabalho aprofundar nos conhecimentos de Piaget, porm algumas de suas idias
so extremamente importantes quando se fala na introduo de novos saberes na educao.
extremamente importante saber como e quando determinado contedo deve, e pode, ser intro-
duzido na educao, principalmente no que tange o nvel assimilao do conhecimento de cada
indivduo, pois assim pode-se ter a certeza de que a idia proposta ter maiores chances de ser
aproveitada por aqueles que a iro receber.
Piaget determina quatro estgios no desenvolvimento lgico do indivduo, conforme abor-dado por (GOULART, 1983):
Estgio sensrio-motor- de 0 a 18 ou 24 meses, aproximadamente;
Estgio objetivo-simblico- de 2 a 6 ou 7 anos, aproximadamente;
Estgio operacional-concreto- por volta dos 7 at 11 ou 12 anos, aproximadamente;
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
44/119
5.1 O que diz Piaget? 43
Estgio operacional-abstrato- a partir dos 11 ou 12 anos, aproximadamente;
Como a proposta do ensino de grafos na educao bsica um assunto no muito discu-
tido, muito importante compreender cada um desses estgios, para no cair no erro de propor
uma atividade que no seja coerente com o perodo adequado. Devido a natureza deste traba-
lho, as atividades propostas aqui sero pertinentes apenas aos dois ltimos estgios, o "Estgio
operacional-concreto"e o "Estgio operacional-abstrato". Assim sendo, iremos detalhar melhor
esses nveis destacando suas principais consideraes.
5.1.1 Operacional-Concreto
Para Goulart, essa uma fase de transio entre a ao e as estruturas lgicas mais gerais,
que implicam uma combinatria e uma estrutura de "grupo" (GOULART, 1983). Conforme
as observaes do prprio Piaget, so duas as ordens de operaes encontradas nesse estgio,
as lgico-matemticas e as infralgicas. Basicamente, nas operaes lgico-matemticas, se
relacionam com "semelhanas", classes e relaes simtricas, "diferenas", relaes assimtricas
ou ambas ao mesmo tempo, nmeros. As operaes infralgicas, compreendem as conservaes
fsicas dos objetos, como noes de quantidade, peso e volume, e constituio do espao, como
noes de comprimento, superfcie, permetro, horizontais, verticais, etc.
Nesse estgio, surge a idia de transformao dos objetos, ou seja, o indivduo comea a
perceber que os objetos podem ter sua forma alterada, porm manter algumas de suas caracte-rsticas, como volume, massa, etc. Percebe-se claramente a existncia de uma invariante, que
piaget denominou denooouesquema de conservao. Vrios esquemas de conservao sur-
gem nesse estgio, e esses esquemas esto diretamente ligados a elaboraes lgico-matemticas
de classes, relaes e nmeros, conforme afima Goulart (GOULART, 1983). Como no do in-
teresse deste trabalho um aprofundamentos nos contedos piagetianos, vamos apenas listar os
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
45/119
5.1 O que diz Piaget? 44
esquemas de conservao definidos por Piaget:
1. Conservaes Fsicas
(a) Conservao da Substncia
(b) Conservao do Peso
(c) Conservao do Volume
2. Conservaes Espaciais
(a) Conservao do Comprimento
(b) Conservao de Superfcies
(c) Conservao de Volume Espacial
3. Conservao Numrica
Observando essas caractersticas, possvel propor atividades com grafos que possam auxi-
liar na explorao desses pontos, videAnexo A.
5.1.2 Operacional-Abstrato
Tambm conhecido como"Estgio das Operaes Formais", ocorrendo dos 11-12 anos at
os 14-15 anos, aproximadamente. Nessa etapa j existe uma distino entre o que possvel, e oque real, ou seja, o adolescente j comea realizar experimentaes para saber o quanto essas
relaes possveis so reais. Como diz Goulart, Em lugar de limitar-se a organizar o que lhe
chega atravs dos sentidos, o adolescente tem a capacidade potencial de imaginar o que poderia
estar ali".
Algumas das caractersticas observadas nessa etapa so, segundo Goulart:
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
46/119
5.1 O que diz Piaget? 45
1. Estratgia cognitiva com carterhipottico-dedutivo.
2. Manipulao de dadosenunciados ou preposies, ao invs de dados concretos.
3. Tratamento de problemas atravs de uma anlise combinacional, realizando um inventrio
completo do possvel.
importante observar tambm, que nessa etapa surge um conceito importantssimo no de-
senvolvimento do indivduo, a "COMBINATRIA", que consiste, basicamente, em um prolon-
gamento e generelizao das operaes concretas, e constitui uma classificao das classifica-
es.
Esse fato importante, pois demonstra que essa etapa pode ser a mais proveitosa para o
ensino da Teoria dos Grafos, pois muitos dos problemas que podem ser tratatos com a ajuda dos
grafos, so de origem combinatria. Veja, por exemplo, o Problema do Carteiro Chins, que
consiste em definir um percurso pelo qual o carteiro possa entregar todas as cartas sem repetir,
ou pelo menos repetindo o mnimo, uma rua j utilizada. O tratamento desse problema uma
questo combinatria, pois pode-se tentar determinar esse caminho atravs de uma anlise de
todos os caminhos possveis. NoAnexo Bpoder se observar algumas atividades prprias para
essa fase.
Pode-se perceber claramente a importncia em se aplicar os conhecimentos de Piaget nessa
pesquisa. Porm, sabe-se que o Brasil possui leis bem fundamentadas a respeito dos saberes
a serem tratados na educao. Por isso, importante tambm saber o que as leis brasileiras,
relacionadas ao ensino, dizem sobre esse tema.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
47/119
5.2 O que diz a Lei? 46
5.2 O que diz a Lei?
Para sugerir a utilizao da Teoria dos Grafos na Educao Bsica necessrio, antes de
mais nada, buscar as bases legais que apoiem essa prtica. O melhor lugar para se buscar esse
amparo consultar exatamente os documentos que determinam como dever ser a educao em
nosso pas, a Lei de Diretrizes e Bases, LDB, e os Parmetros Curriculares Nacionais, PCN.
Alm disso, interessante saber o que as Orientaes Curriculares dizem sobre esse contedo.
5.2.1 O PCN, a LDB e as Orientaes Curriculares
O PCN no faz nenhuma referncia especfica utilizao da Teoria dos Grafos no ensino da
Matemtica, tanto para o ensino fundamental como para o ensino mdio. Porm, o PCN contm
algumas recomendaes que podem ser utilizadas para apoiar a prtica. Por exemplo:
"... papel da escola desenvolver uma educao que no dissocie escola e socie-dade, conhecimento e trabalho e que coloque o aluno ante desafios que lhe permi-tam desenvolver atitudes de responsabilidade, compromisso, crtica, satisfao ereconhecimento de seus direitos e deveres."(BRASIL1, 2002, pp. 27)
Essa recomendao, por s s, j seria o argumento suficiente para justificar o ensino da
Teoria dos Grafos, assim como qualquer outro contedo que estimulassem essas atitudes. Alm
disso, podemos tambm buscar o apoio na seguinte recomendao:
"Para que ocorram as inseres dos cidados no mundo do trabalho, no mudo dasrelaes sociais, importante que a Matemtica desempenhe, no currculo, equi-librada e indissocialvelmente, seu papel na formao de capacidades intelectuais,
na estruturao do pensamento, na agilizao do raciocnio do aluno, na sua apli-cao a problemas, situaes da vida cotidiana e atividade do mundo de trabalhoe no apoio a construo de conhecimento em outras." (BRASIL1, 2002, pp. 28)
No se pode deixar de destacar a importncia do entendimento matemtico para a compren-
so de outras reas do conhecimento, e a Teoria dos Grafos se faz presente em vrias delas, con-
forme citado anteriormente. Sendo esse contedo matemtico to importante para reas como
Biologia, Poltica, entre outras, nada mais justo do que sua abordagem dentro do ensino mdio,
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
48/119
5.2 O que diz a Lei? 47
afinal, nessa fase final da educao bsica, busca-se a formao de um cidado lcido e crtico,
com capacidade para interagir plenamente com o meio social no qual ele est inserido. Podemos
ver isso na seguinte recomendao do PCN:
"No ensino mdio, etapa final da escolaridade bsica, a Matemtica deve ser com-preendida como uma parcela do conhecimento humano essencial para a formaode todos os jovens, que contribui para a construo de uma viso de mundo, paraler e interpretar a realidade e para desenvolver capacidades que deles sero exigi-das ao longo da vida social e profissional."(BRASIL2, 2002, pp. 108)
importante destacar que a Teoria dos grafos pode ser utilizada como uma alternativa para o
ensino de vrios assuntos dentro da rea de Matemtica. Um exemplo j ilustrado, o ensino de
matrizes, contedo esse que , constantemente, questionado quanto a sua funo pelos alunos.
Sendo assim, a Teoria dos Grafos passa a ser uma poderosa ferramenta de auxlio no processo
Ensino/Aprendizagem de outros contedos matemticos.
Ao se analisar com ateno os diversos artigos contidos na LDB pode-se perceber que v-
rios deles servem como amparo a introduo da Teoria dos Grafos no ensino fundamental e,
principalmente, no que diz respeito ao ensino mdio. A prpria interdisciplinaridade entre a
Matemtica, especificamente a Teoria dos Grafos, com outras reas do conhecimento, pode ser
justificada atravs do seguinte artigo da LDB:
a compreenso dos fundamentos cientfico-tecnolgicos dos processos produtivos, relacio-
nando a teoria com a prtica, no ensino de cada disciplina (REPBLICA, 1996, Art. 35, Inc.
IV).
Qualquer contedo matemtico que possa auxiliar o educando para na assimilao de outros
saberes, matemticos ou no, devem ser utilizados como instrumento de facilitao da aprendi-
zagem. Nesse ponto, a Teoria dos Grafos atende em vrios aspectos, pois os problemas lgicos,
computacionais, cientficos podem e so, em muitos casos, tratados atravs do estudo de grafos.
Outra fonte ser consultada, so as Orientaes Curriculares para o Ensino Mdio, que
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
49/119
5.2 O que diz a Lei? 48
trazem no seu contedo informaes muito importantes, que podem ser decisivas para a amparar
a utilizao da Teoria dos Grafos no Ensino Mdio.
importante frisar que com o advento da popularizao dos computadores e da Internet, o
ensino da Matemtica precisa se adaptar a uma nova realidade. Como pode-se ver:
A maior parte dos contedos de Matemtica do ensino mdio est vinculada amodelos matemticos de natureza contnua: os nmeros reais e os espaos geom-tricos (reta, plano e espao tridimensional). O estudo da geometria e das funesde varivel real inserem-se nesse contexto, refletindo o papel fundamental do Cl-culo (esse assunto objeto de estudo na universidade) no desenvolvimento dasaplicaes da Matemtica nas Cincias. No entanto, no decorrer do sculo XX,
novas necessidades tecnolgicas advindas da introduo dos computadores - quetm uma Matemtica Discreta no seu funcionamento - provocaram um grandedesenvolvimento dos modelos matemticos discretos(EDUCAO, 2006, pp. 94).
Isso deixa claro a necessidade da insero de novos saberes no ensino da Matemtica, prin-
cipalmente no que diz respeito ao ensino mdio.
Ainda sobre as Orientaes Curriculares para o Ensino Mdio, podemos ver:
No ensino mdio, o termo "combinatria"est usualmente restrito ao estudo deproblemas de contagem, mas esse apenas um de seus aspectos. Outros tipos deproblemas poderiam ser trabalhados na escola - so aqueles relativos a conjuntosfinitos e com enunciados de simples entendimento relativo, mas no necessaria-mente fceis de resolver. Um exemplo clssico o problema das pontes de Knis-berg, tratado por Euler: dado um conjunto de sete ilhas interligadas por pontes,a pergunta que se coloca : "Partindo se de uma das ilhas, possvel passar pelasdemais ilhas e voltar ao ponto de partida, nisso cruzando-se cada uma das pontesuma nica vez? Problemas dessa natureza podem ser utilizados para desenvol-ver uma srie de habilidades importantes: modelar o problema, via estrutura degrafo...
Isso mostra que a Teoria dos Grafos j vista, hoje, como um ferramenta para a Educao.
Devido a sua grande diversidade, e possvel se aplicar inmeras situaes-problema onde sua
utilizao seria justificada. Ainda conforme as Orientaes Curriculares: Muitos outros exem-
plos de problemas combinatrios podem ser tratados de modo semelhante, tais como determinar
a rota mais curta em uma rede de transportes ou determinar um eficiente trajeto para coleta de
lixo em uma cidade.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
50/119
5.2 O que diz a Lei? 49
Essas informaes do uma certeza a mais da importncia da Teoria dos Grafos na Educao
Bsica.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
51/119
50
6 Relato da pesquisa
Neste captulo sero descritas as experincias realizadas no ensino fundamental e mdio,
com o intuito de propor a aplicao dos conceitos da Teoria dos Grafos na educao. Sendo
assim, as oficinas foram elaboradas conforme a srie que seriam aplicadas.
Foram aplicadas 3 oficinas, uma no Ensino Mdio, outra no Ensino Fundamental e uma
mesclada com as duas categorias.
6.1 Oficina no Ensino Mdio
A oficina aplicada no Ensino Mdio foi a de cdigo OEM001, vide Apndice, e foi realizada
em uma turma do terceiro ano do curso de Processamento de Dados, do Colgio de Aplicao
do UBM, no dia 15/09/2007. Nessa oficina, foram explorados principalmente o conceito de
caminhos e ciclos, e a representao matricial de um grafo. Por se tratar de uma turma que
possua o pr-requisito de matrizes, e por ser uma turma com o foco voltado para informtica,
foi mais fcil a abordagem do tema, principalmente a ultima atividade da oficina, Caminho de
Custo Mnimo. A teoria dos Grafos, como mensionado anteriormente, tem profunda ligao com
a Computao e exatamente por isso uma abordagem mais rica em detalhes se tornou possvel.
Nessa oficina, ao contrrio das outras, pelo menos 2 alunos j tinham ouvido alguma coisa
sobre grafos, o que tambm foi mais um fator que comprova a relao entre os grafos e a com-
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
52/119
6.1 Oficina no Ensino Mdio 51
putao.
Foi aplicado, antes da oficina um pr-teste, bem simples, que objetivava saber se os alunostinham algum conhecimento sobre grafos. Alm disso, como o foco da oficina era a aplicao
da atividade de Caminho de Custo Mnimo, AEM001, procurou-se saber qual a relao que eles
viam entre a Matemtica e o Transporte.
Aps o pr-teste, aplicou-se a oficina onde os alunos receberam a parte terica e conceitual,
e tambm a parte prtica da oficina, em folhas separadas. A medida que eram discutidos os
assuntos, as atividades eram realizadas e comentadas. Ao final, a turma foi dividida em grupos,
onde cada um dos grupos recebeu um mapa, feito em lona, do grafo utilizado para a Busca do
Caminho de Custo Mnimo.
Figura 6.1: Mapa utilizado na atividade: Buscando o Caminho de Custo Mnimo
Para fins de uma anlise mais objetiva dos resultados nas oficinas, foram elaborados alguns
grficos comparativos relacionados algumas questes do pr-teste e do ps-teste.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
53/119
6.1 Oficina no Ensino Mdio 52
Figura 6.2: Grfico da 1a questo pr-teste: J estudou matriz em Matemtica ou em outradisciplina
Figura 6.3: Grfico da 2a questo pr-teste: J ouviu falar sobre a Teoria dos Grafos
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
54/119
6.1 Oficina no Ensino Mdio 53
Figura 6.4: Grfico da 3a questo pr-teste: Conhece alguma funo para matrizes
Figura 6.5: Grfico da 4a questo pr-teste: J ouviu falar sobre algum dos assuntos
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
55/119
6.1 Oficina no Ensino Mdio 54
interessante destacar alguns aspectos interessantes levantados nessa oficina, mediante as
questes apresentadas aos alunos:
Figura 6.6: Grfico da 5a questo pr-teste: Quais dos assuntos esto relacionados com a Mate-mtica
Ligao da Matemtica com os transportes: na ltima pergunta do pr-teste, Apndice
D p. 77, os alunos foram indagados sobre a ligao da Matemtica com diversas outras
reas do conhecimento, como Economia, Contabilidade, Computao e Transporte. Todos
os alunos afirmaram que existe ligao com as trs primeiras reas, mas apenas 2 deles
via uma relao da Matemtica com o Transporte. Isso j era esperado, por isso a ltima
atividade da oficina foi exatamente a Busca pelo caminho de custo mnimo. Assim eles
puderam ver uma relao direta da duas reas do conhecimento.
Aplicao para matrizes: apesar de ser uma parte obrigatria do curso, pela qual os
alunos j passaram, ou deveriam ter passado, alguns alunos afirmam que nunca estudaram
matrizes. Isso reflete o porqu da maioria no ver uma aplicao direta para sua utilizao
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
56/119
6.1 Oficina no Ensino Mdio 55
Realizando a anlise dos resultados do ps-teste, pode-se destar os seguintes aspectos:
Figura 6.7: Grfico da 1a questo ps-teste: Conhece pelo menos uma aplicao para a Teoriados Grafos
Conhecimento de aplicaes para a Teoria dos Grafos: a maioria dos alunos tournou-
se capaz de apresentar pelo menos uma situao onde o conceito de grafos pudesse ser
utilizado. Isso uma informao relavante, levando em considerao que a maioria dos
alunos nunca havia ouvido falar sobre o assunto.
O conceito de grafo: possvel notar pelos ps-testes, que apesar de algumas idias sobre
grafos e sua utilidade terem mudado, o conceito de grafos ainda no ficou claro para os
alunos. Isso tambm pode ser notado no Anexo A, p. 89 e 90. O que demonstra que essas
idias bsicas devem ser melhor trabalhadas futuramente.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
57/119
6.1 Oficina no Ensino Mdio 56
Figura 6.8: Grfico da 3a questo ps-teste: A Teoria dos Grafos tem alguma relevncia nocotidiano
Figura 6.9: Grfico da 4a questo ps-teste: Gostou da oficina
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
58/119
6.2 Oficina no Ensino Fundamental 57
A atividade preferida:fica claro na anlise do grfico da 4a questo, que a atividade mais
elogiada pelos participantes foi a Busca Pelo Caminho de custo Mnimo. Acreditamos que
isso se deva ao fato de ser essa atividade a mais interativa das atividades aplicadas na ofi-
cina. Alm disso, a parte ldica se faz muito mais presente nessa atividade, no s devido
ao material no qual foi confeccionada, como tambm pela praticidade da mesma.
Figura 6.10: Grfico da 5a questo ps-teste: Problema mais interessante
6.2 Oficina no Ensino Fundamental
No Ensino Fundamental, foram aplicadas as oficinas OEF001 e OEF002. A primeira oficina
explora os conceitos de caminho e ciclos, e a segunda trata dos conceitos de regioes e colorao.
Essas oficinas foram aplicadas em dois dias, em situaes bem diferentes.
No dia 25/10/2007, em uma turma da 6a srie do Ensino Fundamental, da Escola Municipal
Prof. Delci Horta, no municpio de Volta Redonda, onde foi trabalhada apenas a primeira oficina.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
59/119
6.2 Oficina no Ensino Fundamental 58
Figura 6.11: Oficina OEF001 - 6a srie do Ensino Fundamental
No dia 01/11/2007, num evento aberto, tambm da mesma escola, juntamente com outras
atividades matemticas, para vrias sries do Ensino Fundamental, onde as duas oficinas foram
aplicadas em conjunto.
Na primeira oficina do Ensino Fundamental, a aplicao foi bem semelhante aplicada no
Ensino Mdio, pois se realizou dentro da sala de aula, e permitiu uma abordagem mais metdica,
pois havia o momento dos comentrios e o momento da realizao das atividades.
Na segunda oficina, apesar de algumas atividades serem as mesmas, a aplicaes da oficinas
se desenvolveu de forma mais solta, pois no havia explanaes gerais para todos os participan-
tes. Como era um evento livre, cada aluno participante poderia estar realizando uma atividade
diferente por ter comeado num momento diferente. Assim uma ateno pessoal tinha que ser
dada no caso das dvidas, uma vz que no era possvel o exclarecimento das dvidas de uma
forma geral, num quadro por exemplo, como seria feito em sala de aula.
Apesar de aplicadas em circunstncias diferentes, para alunos de sries diferentes, essas
oficinas tambm mostraram aspectos interessantes.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
60/119
6.2 Oficina no Ensino Fundamental 59
Figura 6.12: Oficinas OEF001 e OEF002 - aplicadas num evento livre
Na primeira oficina, foi interessante perceber como os alunos tiravam suas prprias conclu-
ses sobre as atividades. Por exemplo quando estavam estudando o problema das pontes, alguns
chegaram a concluso, num determinado momento, que se o nmero de pontes em cada ilha
fosse par, eles poderiam realizar o trajeto das cidades sem repetir nenhuma das pontes. Depois
eles acabam percebendo, que existem alguns casos onde possvel percorrer um caminho sem
repetir as pontes, mesmo que no existissem apenas ilhas com um nmero par de pontes. Porm
nenhum deles percebeu que essa situao s aconteceria se existissem apenas duas ilhas com um
nmero mpar de pontes.
Na segunda oficina, as concluses no foram muito diferentes da primeira oficina, mesmo setratando de sries diferentes. Porm uma outra observao interessante foi em uma das atividas,
que no foi aplicada na primeira oficina, a Colorao de Mapas. Todos os participantes chegaram
a concluso que poderiam colorir o mapa com apenas quatro cores. Os resultados do questionrio
aplicado podem ser verificados nos grficos abaixo.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
61/119
6.2 Oficina no Ensino Fundamental 60
Figura 6.13: Grfico da 1a questo oficna em sala: Gostou da oficina
Figura 6.14: Grfico da 2a questo oficna em sala: Fez atividades semelhantes a essa oficina
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
62/119
6.2 Oficina no Ensino Fundamental 61
Figura 6.15: Grfico da 3a questo oficna em sala: Atividade que mais gostou
Figura 6.16: Grfico da 4a questo oficna em sala: Gosta das aulas tradicionais de Matemtica
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
63/119
6.2 Oficina no Ensino Fundamental 62
Figura 6.17: Grfico da 5a questo oficna em sala: Mais oficinas como essa no ensino da Mate-mtica
Figura 6.18: Grfico da 1a questo evento livre: Gostou da oficina
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
64/119
6.2 Oficina no Ensino Fundamental 63
Figura 6.19: Grfico da 2a questo evento livre: Fez atividades semelhantes a essa oficina
Figura 6.20: Grfico da 3a questo evento livre: Atividade que mais gostou
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
65/119
6.2 Oficina no Ensino Fundamental 64
Figura 6.21: Grfico da 4a questo evento livre: Gosta das aulas tradicionais de Matemtica
Figura 6.22: Grfico da 5a questo evento livre: Consegue ver relao do contedo no cotidiano
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
66/119
6.2 Oficina no Ensino Fundamental 65
Em ambas as oficinas, pode-se perceber que todos os alunos gostaram das atividades e,
tambm nas duas oficinas, a atividade Passando o Lpis Apenas Uma Vz foi a preferida pelos
participantes.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
67/119
66
7 Concluso e Trabalhos Futuros
A aplicao de atividades relacionadas a Teoria dos Grafos na Educao Bsica se mostrou,
ao nosso entender, muito proveitosa. E esse sentimento o mesmo tanto para o Ensino Funda-
mental quanto para o Ensino Mdio.
No Ensino Fundamental, apesar de no abordar definies mais formais da Teoria dos gra-
fos, a experincia com os alunos demonstrou existir um interesse pela investigao dos proble-
mas apresentados, geralmente relacionados com anlise combinatria. interessante notar que
os alunos, enquanto no sabem da impossibilidade de soluo de alguns dos problemas apresen-
tados, como o Problema das Sete Pontes, procuram avidamente por sua soluo. Durante essa
busca pela soluo, no foi incomum ver os alunos proporem alternativas, como por exemplo, a
construo de uma nova ponte, ou ento, a retirada de uma existente, ou ainda, atravessar o rio
nadando.
Apesar de muitas das solues irem contra as regras definidas para o problema, curioso
ver como essas seriam, em muitos casos, a soluo para o problema real. Isso demonstra que osalunos conseguiram, pelo menos em parte, se verem naquela situao-problema, e devido a isso,
conseguiram propor uma gama bem diversificada de alternativas para a soluo do problema.
Outra observao interessante, que os alunos de sries diferentes do Ensino Fundamental
apresentaram, em sua maioria, as mesmas dificuldades, o que indica que a proposta de atividades
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
68/119
7 Concluso e Trabalhos Futuros 67
relacionadas a Teoria dos Grafos no precisa ser to diversificada dentro dessa fase do ensino.
No Ensino Mdio, apesar do desconhecimento da maioria dos alunos sobre as aplicaes comgrafos, muitos j haviam ouvido falar de problemas onde existe a aplicao deste tema, como por
exemplo o Problema do Carteiro Chins e o Problema do Caixeiro Viajante. Isso at esperado,
haja visto que a oficina foi aplicada numa turma de curso Tcnico de Processamento de Dados,
assim a familiarizao com temas como esses no incomum. Apesar disso, a maioria dos
alunos tiveram dificuldades no momento de definirem a palavra grafo. Isso demonstra que apesar
de alguns conhecimentos terem sido absorvidos, importante um trabalho mais metdico comalunos com essa caracterstica. Um fator que merece destaque foi o fato de alguns alunos, apesar
de estarem num curso de Computao, no conseguirem ver uma aplicao para a utilizao de
matrizes. Esse foi um resultado inexperado, pois se tratando da rea de estudo dos alunos, eles
deveriam ter exemplos bem claros para essas aplicaes.
Apesar das dificuldades encontradas para relacionar o tema com a educao, a falta de refe-
rncias sobre o tema e o tempo para uma pesquisa mais aprofundada, o tema se mostrou vivel.
No apenas pelos aspectos matemticos, mas tambm pelo efeito causado nos alunos.
A existncia de um documento sugerindo a utilizao da Teoria dos Grafos um importante
passo para a adeso desse tema dentro da educao.
importante deixar claro, que o tema muito abrangente, muitos aspectos podem ser tra-
tados, muitas atividades podem ser elaboradas mediante a explorao desses diferentes aspectos
da Teoria dos Grafos, como por exemplo planalidade de grafos. Isso deixa claro a importncia
da continuidade da pesquisa, para que uma fundamentao mais slida possa ser dada e, quem
sabe assim, futuramente, possamos publicar outras pesquisas relacionadas ao tema.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
69/119
68
Referncias Bibliogrficas
ABREU, N. M. M. d. Introduo Teoria Espectral de Grafos com Aplicaes.So Carlos, SP:SBMAC, 2007.
BOAVENTURA, P. O. N.Grafos - Teoria, Modelos, Algoritmos. Rio de Janeiro, RJ: Blucher,
2006.BRASIL1, M. d. E. e. C. S. d. E. F. Parmetros curriculares nacionais. Matemtica: Ensino dequinta oitava srie. Braslia: MEC/SEF, 2002.
BRASIL2, M. d. E. e. C. S. d. E. F. Parmetros curriculares nacionais. Matemtica: EnsinoMdio. Braslia: MEC/SEF, 2002.
BRIA, J. Grafos no Ensino Mdio e Fundamental:Matemtica, Interdisciplinaridade eRealidade. Dissertao (Mestrado) DEP/UFRJ, 1999.
EDUCAO, S. d. B. Orientaes Curriculares para o Ensino Mdio. Cincias da Natureza,
Matemtica e suas Tecnologias.Braslia: MEC, 2006.
FREITAS, A. E. S. Teoria dos Grafos - O problema do carteiro Chins. 2007. URL:http://www.allanedgard.eti.br/grafos/. Acessado em: 28 set. 2007.
GOULART, I. B. Piaget: experincias bsicas para utilizao pelo professor. 3a edio. ed.Petrpolis, RJ: Editora Vozes, 1983.
GREVE, F. G. P. Teoria dos Grafos e Algoritmos. 2007. URL:http://twiki.im.ufba.br/bin/view/MAT156/WebHome. Acessado em: 19 set. 2007.
INPE, S. d. p. d. i. g. Tutorial de Geoprocessamento. 2007. URL:http://www.dpi.inpe.br/spring/portugues/tutorial/estrutura.html. Acessado em: 13 out.2007.
LIMA, E. L.Revista do professor de matemtica: Alguns problemas clssicos sobre grafos. 12aedio. ed. So Paulo, SP: Sociedade Brasileira de Matemtica, 1988.
NASCIMENTO, R. A. d.; SILVA, M. L. d. Mini-curso atividades com grafos para a educaobsica. IX ENEM - Encontro Nacional de Educao Matemtica, 2007.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
70/119
Referncias Bibliogrficas 69
PENHA, G. M. d. L. Revista do professor de matemtica: Euler e a Topologia. 1a edio. ed.So Paulo, SP: Sociedade Brasileira de Matemtica, 1983.
REPBLICA, P. d. S. d. E. F. LDB - Lei das Diretrizes e Bases da Educao. Braslia:Congresso Nacional, 1996.
SANTOS, J. P. de O.; MELLO, M. P.; MURARI", I. T. C. Introduo a anlise combinatria.2a edio. ed. Campinas, SP: Editora da Unicamp, 1998.
SCHEINERMAN, E. R.Matemtica Discreta : uma introduo. 1a edio. ed. So Paulo, SP:Thomson Learning Edies, 2004.
Seara da cincia. O mapa das quatro cores. 2007. URL:http://www.seara.ufc.br/especiais/matematica/problemasfamosos/matematica4.htm. Acessado
em: 28 set. 2007.
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
71/119
70
APNDICE A -- Atividades para o ensino
fundamental
Cada atividade possui alguns dados para facilitar seu entendimento e aplicao, como a srie
aplicada, o objetivo, material utilizado, entre outras informaes. Devido a serem atividades
voltadas para o ensino fundamental, no existe a inteno de conceituar os grafos ou qualquer
elemento de sua teoria. A idia central despertar o interesse e familiarizar os alunos com os
problemas existentes no estudo da Teoria dos Grafos. Outro dado que importante destacar
que muitas outras atividades foram sugeridas, porm s ser tratado nessa pesquisa as atividades
que foram aplicadas.
Para facilitar a organizao, optou-se por utilizar uma nomeclatura prpria para cada ativi-
dade, veja um exemplo:
AEF001
Onde:
A indica que uma Atividade;
EF indica que essa atividade para o Ensino Fundamental, podendo ser tambm EM para o
Ensino Mdio;
001 nmero seqncial que diferencia uma atividade de outra dentro de cada tipo de ensino;
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
72/119
A.1 Os trs servios 71
Vejamos algumas dessas atividades:
A.1 Os trs servios
Cdigo:AEF001;
Srie aplicada:De 5a a 8a sries do ensino fundamental;
Objetivo:abordar o problema Agua Luz e Telefone (LIMA, 1988, pp. 42) de uma forma
concreta, despertando nos alunos o interesse pela investigao e pela resoluo de problemas;
Descrio: os alunos, reunidos em grupo, recebero um kit de materiais contendo a re-
presentao das trs casas, das trs companhias, e os fios de l, de cores diferentes, que sero
utilizados para levar os servios das companhias para as casas, de forma que os fios no se cru-
zem;
Material:Trs casas e trs companhias (que podem ser representadas por caixas de papelo,
madeira, montadas em cartolina, etc), trs fios de l de cores diferentes e folhas de papel para o
desenho das solues obtidas;
OBS:esse material pode ser substituido pelo desenho das casas e das companhias no papel, e
utilizando um lpis para realizar as ligaes. Alm disso, o problema pode ser adaptado para
outos elementos como, por exemplo, os trs carros e os trs tipos de combustvel.
Como aplicar:
1.Distribua os kits para os alunos juntamente com as folhas para anotao;
2.Defina os objetivos: levar os trs servios para as trs casas sem deixar os fios se cruzarem;
3.Pedir para os alunos anotarem suas solues;
4.Comente o resultado;
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
73/119
A.1 Os trs servios 72
No de participantes:no definido;
Pr requisitos:Nenhum
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
74/119
A.2 As sete pontes 73
A.2 As sete pontes
Cdigo:AEF002;
Srie aplicada:De 5a a 8a sries do ensino fundamental;
Objetivo: apresentar o problema das Sete Pontes para demonstar os conceitos iniciais da
Teoria dos Grafos;
Descrio:os alunos, reunidos em grupo, recebero uma folha com a configurao original
da cidade de Konigsberg, e com outras configuraes, para que os alunos possam abordar os
conceitos envolvendo o problema e chegando a conclusao prpria do porqu da falta de resoluo
do mesmo;
Material:folha contendo vrias configuraes da cidade de Konigsberg, lpis para traar os
caminhos encontrados e para anotar as observaes necessrias;
Como aplicar:
1.Distribua o material para os grupos;
2.Defina os objetivos: encontrar um caminho passando por todas as pontes, sem repetio
das mesmas;
3.Realize intervenes regulares, aps cada etapa, aproveitando para definir algumas carac-
tersticas dos grafos;
4.Pedir para os alunos mostrarem suas solues e concluses;
5.Comente os resultados;
No de participantes:no definido;
7/25/2019 Uso da Teoria dos Grafos na Educao Bsica
75/119
A.2 As sete pontes 74
Pr req