Mathematics">
Jogos1 0
Jogos1 0
Jogos1 0
Orientadora
Profa. Dra. Érika Capelato
2017
511.5 Favaro, Flavia Fernanda
F272t A teoria dos grafos e sua abordagem na sala de aula com
recursos educacionais digitais / Flavia Fernanda Favaro. - Rio
Claro, 2017
56 f. : il., figs., tabs.
À Deus, por nos conceder o dom a vida, por nos dar inteligência para aprender e
vontade de atingir um conhecimento maior.
À orientadora Érika Capelato, por ter me orientado e instruído com tanta paciência
durante o caminhar desse trabalho.
"A Matemática é o alfabeto com que Deus escreveu o universo".
Galileu Galilei
Resumo
Neste trabalho estudamos a Teoria dos Grafos compreendendo suas definições, resul-
tados e algumas aplicações como O Problema das Pontes de Köningsberg, O Problema
Chinês do Carteiro, O Problema do Caixeiro Viajante e O Teorema das Quatro e das
Cinco Cores. Com o uso da Coleção M 3 - Matemática Multimídia, que contém recur-
sos educacionais em formatos digitais, aplicamos as atividades sugeridas aos alunos do
segundo ano do Ensino Médio de uma escola particular localizado na cidade de São
Pedro - SP. As atividades mostraram que, apesar da Teoria dos Grafos não constar no
currículo regular do Ensino Médio, sua aplicação para este grupo de alunos foi posi-
tiva, uma vez que os alunos sentiram-se motivados com o conteúdo abordado na forma
digital e com sua aplicação ao estudo de Matrizes. Concluímos assim que, nos dias
atuais a ligação do processo de ensino aprendizagem com os softwares educacionais
podem proporcionar, tanto para os professores quanto para os alunos, uma forma mais
prazerosa e eficaz de obter conhecimento em Matemática.
In this work, we study Graph Theory, meaning its definitions, results e some ap-
plications such as the Köningsberg bridge problem, the chinese postman problem, the
travelling salesman problem and the four color theorem as well as the five color the-
orem. By using the M 3 - Matemática Multimídia Series, which contains educational
resources in digital form, we applied the suggested activities to second year high school
students form a private school located at the city of São Pedro – São Paulo State. The
activities showed that, although Graph Theory is not part of the high school regular
curriculum, its application to this group of students was positive, since the students
felt themselves motivated by the digital approach to its contents and its applications
to the study of Matrices. We conclude that, nowadays, the connection between the
teaching processes and educational softwares can provide, to the teachers as well as to
the students, a more pleasurable and efficient way to obtain knowledge in Mathematics.
1 Introdução 10
2 Primeiras Noções 13
2.1 Alguns tipos de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Representação de grafos por Matrizes . . . . . . . . . . . . . . . . . . . 18
5 Coloração de Grafos 32
5.1 O teorema das Quatro e Cinco Cores . . . . . . . . . . . . . . . . . . . 35
7 Considerações Finais 53
Referências 55
Referências 55
1 Introdução
A resolução desse desafio, que hoje é conhecido como O Problema das Pontes de
Königsberg, foi feita em 1736 num artigo de considerável importância para a Teoria
dos Grafos escrito pelo matemático suíço, Leonardo Euler1 . Ao resolver este problema,
Euler mostrou que a resposta para a pergunta do desafio era “não” e assim determinou
um método geral para resolução de problemas deste tipo. No capítulo 4 voltaremos a
falar deste problema mostrando o resultado encontrado por Euler.
Vale ressaltar que, inicialmente, a Teoria dos Grafos foi considerada irrelevante
e caiu no esquecimento durante muito tempo até ser aproveitada por A. Cayley na
1
Leonardo Euler viveu em Basiléia, norte da Suíça (1707 - 1783).
10
11
Muitos autores vêm discutindo este tema em suas dissertações do Mestrado. Por
exemplo, Lima [11] apresenta o Teorema das Quatro Cores, desde o seu surgimento
com Francis Guthrie, explorando a demonstração feita por Alfred Bray Kempe e sua
refutação através do contraexemplo de Percy John Heawood, além da demonstração
do Teorema das Quatro Cores feita com o auxílio do computador.
Em Nogueira [14] o autor propõe a aplicação, através de um caderno de atividades,
do problema das pontes de Königsberg, das trilhas eulerianas e dos caminhos hamilto-
nianos. Nesta linha, Costa [5] estuda os problemas clássicos da Teoria dos Grafos, como
o problema das pontes de Königsberg, o problema do caixeiro viajante, a classificação
dos poliedros regulares e a coloração de mapas.
No que se refere às aplicações sugeridas para o Ensino Médio, pudemos encontrar,
por exemplo, o trabalho de Guedes [9] que abordou os grafos Eulerianos e Semieuleri-
anos como estratégias para resolver situações problemas e o trabalho de Farias [7] que
propõe modelar conteúdos, já inseridos no programa do Ensino Médio, que permitem
a abordagem da Teoria dos Grafos dando enfoque especial ao estudo de Matrizes.
Na literatura internacional encontramos, por exemplo os trabalhos de Quinn [15] e
[16] onde a autora usa o aplicativo Graphing, gratuito para smartphone, como proposta
12
para visualizar a Teoria dos Grafos na sala de aula. Por exemplo, na Figura 1.3 a autora
usa o aplicativo para mostrar que há um isomorfismo entre os grafos dados por uma
estrela e por um pentágono.
Estes termos advém da representação do grafo por seu diagrama. Por exemplo, o
diagrama da Figura 2.1 tem os vértices A, B, C e D e as arestas 1, 2, 3, 4, 5, 6 e 7. O
vértice B é chamado nó, pois a aresta 2 liga este vértice a ele mesmo, neste caso, esta
aresta recebe o nome de laço.
Exemplo 2.1. Considere o diagrama da Figura 2.1, onde cada vértice é representado
por um ponto e cada aresta por uma linha ligando os pontos que representam os seus
extremos. Desta forma, a função de incidência ψ é dada por:
13
14
aresta = α ψ(α)
1 {A, B}
2 {B}
3 {B, C}
4 {A, C}
5 {A, D}
6 {C, D}
7 {C, D}
Caso todos os vértices de um grafo tenham o mesmo grau, dizemos que o grafo é
regular. Se o grau de todos os vértices for k vamos escrever que o grafo é k-regular.
Definição 2.3. Um vértice é dito isolado quando seu grau é igual a 0 e pendente
quando seu grau é 1. O menor grau de um vértice em um grafo G, é chamado de grau
mínimo e denotado por δ(G) e o maior grau de um grafo G é chamado de grau máximo
e denotado por ∆(G)
Exemplo 2.2. Considerando a Figura 2.1. Este grafo tem 7 arestas e 4 vértices, logo
seu tamanho é 11. Os vértices A e D são exemplos de vértices adjacentes e a aresta 5
é incidente aos vértices A e D. Quanto ao grau temos: d(A) = 3, d(B) = 4, d(C) = 4 e
d(D) = 3. A soma dos graus de todos os vértices é duas vezes o número de arestas, 14.
Teorema 2.1. Dado um grafo G, com m arestas, a soma do grau dos vértices de G é
sempre o dobro do número de arestas, ou seja,
X
d(v) = 2 · m.
v∈V (G)
Corolário 2.1. Todo grafo G possui um número par de vértices de grau ímpar.
15
Assim temos, por exemplo, N (7B) = {6A, 8A, 8B} e N [7B] = {6A, 7B, 8A, 8B}.
Além disso, temos a sequência decrescente dos graus dos vértices formada por {4,3,3,
3, 3, 2} com ∆(G) = 4 e δ(G) = 2.
Quando temos dois grafos que representam a mesma situação, ou seja, suas carac-
terísticas são as mesmas: graus, número de vértices, etc, podemos chamá-los de grafos
isomorfos. Utilizando uma definição mais formal, podemos dizer que:
Definição 2.5. Dois grafos G1 e G2 são ditos isomorfos se entre eles é possível es-
tabelecer uma correspondência biunívoca entre o conjunto de seus vértices que preserve
as adjacências.
Exemplo 2.4. Considere os grafos da Figura 2.3. A função f que estabelece uma
correspondência biunívoca entre os conjuntos de vértice está definida abaixo.
Esta função existe, pois se tomarmos a aresta {a, d} no grafo da esquerda, na Figura
2.3, a função fará correspondência com o vértice {w, y} no grafo à direita.
Alguns tipos de grafos 16
Figura 2.4: À esquerda exemplo de grafo simples e à direita exemplo de grafo completo
Fonte: Jurkieiwicz [10], p. 20.
Figura 2.5: À esquerda exemplo de grafo regular os demais são exemplos de ciclo
Fonte: Jurkieiwicz [10], p. 20.
Alguns tipos de grafos 17
estamos unindo duas faces). Assim, aplicando a hipótese de indução sobre G − a temos
(f − 1) − (m − 1) + n = 2 e, portanto f − m + n = 2.
• Como cada aresta é ligada a dois vértices, cada linha possui dois números 1;
• Num grafo que não possui laço a diagonal principal é composta somente pelo
número 0;
Na Figura 3.1 temos exemplo de um grafo 3-conexo, pois podemos escolher dois
vértices quaisquer para retirar, e ainda teremos um grafo conexo.
Já sabemos da definição que o conjunto dos vértices de um grafo bipartido é dividido
em dois subconjuntos V1 e V2 , que são chamados de conjuntos independentes, isto é, se
w e t forem ambos vértices de V1 eles não são adjacentes.
Teorema 3.1. Seja G um grafo com no mínimo dois vértices. G é bipartido se, e
somente se, não contém ciclos de comprimento ímpar.
20
O problema do menor caminho 21
O algorítimo que dá a solução desse tipo de problema foi dado em 1952, por Eds-
ger Wybe Dijkstra, que era cientista da computação, viveu de 1930 à 2002 e em 1972
recebeu o Turing Award devido às suas contribuições na área de linguagens de progra-
mação.
Para a resolução do problema apresentado na Figura 3.2, trabalharemos com grafos
valorados, ou seja, será atribuído um valor à aresta. Estes valores podem ser distância,
tempo gasto no trajeto ou custo gasto no trajeto, entre outras coisas. Na Figura 3.2
notamos que foi atribuído o valor 11 para a distância entre a Praça e a Banca de Jornal,
pois entre elas está um cachorro que parece ameaçador, entre a Quitanda e a Cancela a
distância é 4 pois há ali uma pessoa que nos chama a atenção. Usaremos este exemplo
para compreender o algoritmo desenvolvido por Dijkstra.
Para iniciar a resolução calcula-se todas as distâncias possíveis a partir da casa de
João até a escola, computando também que a distância da casa de João até ela mesma
é zero. Para o início dessa contagem devemos ter em mente as seguintes questões: Até
onde posso chegar a partir da casa de João em uma única etapa? Qual o custo?
Para facilitar a compreensão utilizaremos as seguintes siglas J para a Casa de João,
A para o Armazém, P para a Pracinha, Q para a Quitanda, C para a Cancela, B para
a Banca de Jornal e E para a Escola.
Tendo como ponto de partida sempre a Casa de João, analisaremos cada um dos
caminhos que podem ser tomados. Se optarmos pelo caminho do Armazém a distância
será igual a 5, se optarmos pelo caminho da Quitanda, a distância será igual a 10 e se
optarmos pelo caminho da Pracinha, a distância será igual a 6. Ao compararmos essas
três possibilidades é fácil notar que a opção do caminho que passa pelo Armazém é a
melhor, e a partir do Armazém só podemos ir pelo caminho que passa pela Banca de
Jornal. Assim,
• J → A → B = 18
Analisando agora o caminho que passa pela Pracinha, a partir dela temos três
opções de caminhos que são: Quitanda, Banca de Jornal e Cancela, estudando cada
uma delas chegamos em:
• J → P → C = 12
• J→P→Q=9
• J → P → B = 17
Comparando esses resultados temos que a melhor escolha é o caminho até a Qui-
tanda, analisaremos agora, se através dela temos uma menor distância. Da Quitanda
temos duas opções de caminho, uma que passa pela Banca de Jornal e outra que passa
Cancela, sendo assim:
• J → P → Q → B = 15
• J → P → Q → C = 13
Comparando com os resultados anteriores vemos que não é vantagem, pois o per-
curso:
• J → P → C = 12
O problema do menor caminho 23
• J → P → C → E = 20
Mas voltando a opção anterior e acrescentando à ela o caminho até a escola teremos:
• J → P → Q → B → E = 18
Sendo assim, o menor percurso entre os vértices Casa do João e Escola, será através
da Pracinha, da Quitanda e da Banca de Jornal.
Definição 4.1. Um grafo G com m arestas é dito euleriano se existe uma trilha
fechada de comprimento m em G; em outras palavras, se podemos percorrer cada aresta
uma e só uma vez partindo de um vértice e a ele retornando. Se o grafo não é euleriano,
mas tem uma trilha aberta de comprimento m, ele é dito semieuleriano.
Na Figura 4.2, G1 é um grafo euleriano e a trilha pode ser a − b − c − d − e − f − a −
d−b−e−a. O grafo G2 é semieuleriano e a trilha pode ser a−e−b−d−c−b−a−d−e
e o grafo G3 não é euleriano nem semieuleriano.
24
O problema das Pontes de Königsberg 25
Os resultados abaixo são dados para mostrar que não é possível atravessar as sete
pontes do Problema das Pontes de Köningsberg passando por todas elas uma única vez
e retornar ao ponto de partida.
Lema 4.1. Se todo vértice de um grafo (não necessariamente simples) G tem grau
maior ou igual a 2, então G contém um ciclo.
O Problema Chinês do Carteiro 26
De acordo com o Teorema 4.1 o grafo resultante do Problema das Pontes de Kö-
nigsber (veja a Figura 4.1) não é euleriano, pois todos os seus vértices são ímpares.
Isto responde o desafio proposto.
Os grafos eulerianos também são aplicados na resolução de outros problemas de
atendimentos sequenciais, como entregas ou recolhimentos (correios, luz, gás, telefone).
Nestes casos os vértices são os pontos a serem atendidos e as arestas os caminhos entre
estes pontos. O desafio é percorrer cada caminho uma única vez, se possível, ou o menor
número de vezes possível. O interesse, na maioria dos casos, é obter esse caminho de
forma fechada. Um exemplo, é o seguinte problema:
Vamos ilustrar o caso mais simples dado pela Figura 4.3 que apresenta um grafo
semieuleriano, onde temos apenas dois vértices de grau ímpar (vértices a e b) e calcular
O Problema do Caixeiro Viajante 27
Assim como no Problema das Pontes de Königsberg, buscamos a solução por meio
da construção de um ciclo que contém todos os vértices do seu grafo, veja Figura 4.4.
Definição 4.2. Seja G um grafo. Uma trilha fechada que passe por todos os vértices
uma única vez (exceto o inicial e final) é chamada de ciclo ou circuito hamiltoni-
ano. Se G contém um circuito hamiltoniano dizemos que G é um grafo hamiltoni-
ano.
Estes resultados são usados para resolver um problema muito estudado em Pesquisa
Operacional e conhecido como O Problema do Caixeiro Viajante que diz: Dado um
grafo G completo e valorado, como determinar o menor ciclo hamiltoniano de G? Ou
seja, como partir de uma determinada cidade, visitar todas as outras uma única vez
e retornar para a cidade de origem, de modo que o custo total desta viagem seja o
O Problema do Caixeiro Viajante 29
Definição 4.3. Um grafo G conexo que não contém ciclos é chamado de árvore. Um
grafo que não contém ciclos é uma floresta, ou seja, uma floresta é a união disjunta
de uma ou mais árvores. Uma aresta ab é uma ponte se o grafo G − ab possui mais
componentes que G. Um vértice com grau 1 é chamado folha.
Na Figura 4.6 temos um exemplo no item (a) de uma árvore e no item (b) de uma
floresta formada por duas árvores. No item (a) a aresta xy é uma ponte e o vértice z
uma folha. O próximo resultado categoriza as árvores:
Teorema 4.3. Seja T um grafo com n vértices. As seguintes afirmações são equiva-
lentes:
1. T é uma árvore.
6. T não contém ciclos, mas a adição de uma aresta produz um único ciclo.
Demonstração:
1 ⇒ 2: Por definição, T não possui ciclos, sendo assim, ao retirarmos a aresta que
liga o vértice u ao vértice v, separamos o grafo em um par de árvores T 0 e T 00 com n0 e
n00 vértices respectivamente, onde n = n0 + n00 . Por indução em n, temos que T 0 possui
n0 − 1 aresta e T 00 possui n00 − 1 , ao acrescentarmos a aresta que liga u a v, teremos o
número de arestas de T dado por (n0 − 1) + (n00 − 1) + 1 = n − 1.
2 ⇒ 3: Supondo T desconexo, teríamos que cada componente seria uma árvore,
então, por indução, o número de arestas de cada uma de suas componentes, é uma
O Problema do Caixeiro Viajante 30
unidade menor que o número de vértices, sendo assim o número de arestas seria menor
que n − 1.
3 ⇒ 4: Ao retirarmos qualquer aresta separamos o grafo, pois n − 2 arestas não
conectam dois grafos.
4 ⇒ 5: Quando temos mais de um caminho entre dois vértices isso caracteriza um
ciclo, e existiria uma aresta que não separaria o grafo.
5 ⇒ 6: Se o grafo T possuísse um ciclo, teríamos um par de vértices ligados por mais
de um caminho . Ao adicionarmos uma aresta ligando os vértices u e v produziríamos
um ciclo. Se esse ciclo não fosse único, ao retirarmos a aresta uv teríamos dois caminhos
diferentes entre essas arestas.
6 ⇒ 1: Supondo T desconexo , uma aresta que liga dois vértices não produziria um
ciclo.
Exemplo 4.1. Dado o grafo G valorado representado na Figura 4.8, qual sua árvore
geradora de menor valor?
O algoritmo acima pode ser usado para obtermos um limitante inferior para o
Problema do Caixeiro Viajante. Para isto, adicionamos à árvore geradora mínima o
menor valor de uma aresta não usada na árvore e obtemos um limitante inferior para
o peso mínimo de um ciclo hamiltoniano.
5 Coloração de Grafos
32
33
Exemplo 5.2. Suponhamos que num parque, representado pelo grafo da Figura 5.2,
será feito a instalação de barracas para venda de sorvetes seguindo as restrições:
Definição 5.3. O menor número de cores usado para colorir os vértices de um grafo
G (depois de alguma restrição) é chamado número cromático de G e será denotado
por χ(G).
Se atribuirmos cores aos vértices da Figura 5.1 de forma que vértices adjacentes
tenham necessariamente cores diferentes vamos precisar, no mínimo, de 4 cores. Assim,
χ(G) = 4.
Lembrando da definição que ∆(G) é o maior grau de um grafo G, podemos enunciar
o seguinte teorema:
Exemplo 5.3. Tomemos novamente o problema do parque, Exemplo 5.2, mas agora,
além de instalarmos barracas de sorvete, também queremos instalar barracas de pipoca,
cachorro-quente, etc., sendo que essas instalações terão as seguintes restrições:
alternada, são coloridas as faces exteriores ao circuito e em (d) temos o tabuleiro com
sua coloração final, sendo que foram utilizadas o mínimo de quatro cores.
Lema 5.1. Num grafo planar há pelo menos um vértice com grau menor ou igual a 5.
Demonstração: Já sabemos que Σv⊂V (G) d(v) = 2m. Se d(v) > 5 para todo v ∈ V ,
então
6n ≤ Σv⊂V (G) d(v) = 2m.
Mas num grafo planar temos m ≤ 3m − 6, isto é, 2m ≤ 6n − 12. Ficamos com
6n ≤ 6n − 12, o que é impossível.
Teorema 5.5. (Teorema das 5 cores) Num grafo planar simples G, tem-se χ(G) ≤ 5.
Demonstração: Em todo grafo planar existe um vértice com grau menor ou igual
a 5. Podemos decompor o grafo retirando sempre um vértice de grau menor que 5
O teorema das Quatro e Cinco Cores 38
e recompô-lo colorindo, vértice a vértice. Dessa forma podemos sempre supor que
estamos colorindo um vértice v de grau menor ou igual 5. Se os vértices em N (v)
estão coloridos com menos de 5 cores, basta colorir o vértice v. Podemos então supor
que o vértice está cercado por 5 vértices coloridos cada um com uma cor do conjunto
{a, b, c, d, e}.
Consideremos o subgrafo induzido pelos vértices coloridos com as cores a e c. Se a
componente que contém o vértice N (v) colorido com a não contiver o vértice colorido
com c, podemos trocar as cores desta componente: quem está colorido com a fica
colorido com c e vice-versa. Podemos então colorir o vértice v com a cor a.
Se a componente que contém o vértice de N (v), colorido com a, for o mesmo do
vértice c, existe um caminho de vértices que “cerca” o vértice b (veja Figura 5.8).
Então, tomamos a componente do grafo induzido por vértices coloridos com b e d,
que contém o vértice de N (v) colorido com b. Depois de trocar as cores b e d nesta
componente, podemos colorir o vértice v com a cor b.
6 Atividades na Sala de Aula
39
40
6.1.1 Parte I
Na sala de aula iniciamos a atividade dividindo os alunos em duplas e entregando
a eles uma folha com a ilustração do desafio das Pontes de Könisgsberg (Figura 6.1).
Para explicar do que se tratava o problema colocamos o primeiro módulo do áudio2 que
possui aproximadamente 8 minutos de duração, onde é narrado o problema de forma
bastante clara e contextualizada, uma vez que foi narrado a localização da cidade e um
pouco da história da época.
Em seguida os alunos foram incentivados a resolverem o desafio. As duplas fizeram
as tentativas e depois de alguns minutos comunicamos que o problema não possui
solução e, a explicação do porque não ter solução, eles chegariam a conclusão nas
próximas atividades.
Problema para a Figura 6.4: Observe agora a segunda planta. Neste caso, seria
possível criar um caminho com as mesmas regras? Se sim, encontre uma solução.
Para a resolução desse problema os alunos fizeram várias tentativas, veja por exem-
plo a da Figura 6.5, até concluírem que não seria possível encontrar tal caminho, que
chamamos de caminho fechado. Notamos que durante a realização da atividade os
alunos se empenharam para resolvê-la, mas ainda não se atentaram em comparar os
grafos da primeira atividade com o grafo da segunda atividade.
Para garantir que os alunos concluíssem de forma conceitual, quando um grafo
possui caminho fechado e quando não possui, propomos ainda outras duas atividades.
Atividade 1: Caminho fechado e grafos 43
Os alunos receberam mais dois desafios que estão na Figura 6.6 que foram trabalhados
com o seguinte problema:
Agora vamos pensar no trabalho de um entregador de jornais. Ele deve passar por
várias ruas até que abasteça todos os assinantes. A gráfica é seu ponto de partida e deve
ser seu ponto de chegada, após entregar todos os jornais. Em cada uma das 2 situações,
veja se é possível encontrar um trajeto pelo qual ele entregue todos os jornais, passando
apenas uma vez em cada rua. Explique como pensou em cada uma delas.
vértice passando por todos os outros vértices, sem passar pela mesma aresta mais de
uma vez.
As discussões entre as duplas foram muito proveitosas, até que um dos participantes
sugeriu que, "para eu entrar em um vértice teremos que ter um caminho novo para
pode sair". Esse foi o ponto de partida para uma conclusão parcial do conceito em
questão.
Como os alunos não conseguiram se expressar de forma correta, apesar de terem
formado o conceito em suas mentes, foi colocado o segundo módulo do áudio para que
escutassem e assim pudessem concluir que: Um grafo admite caminho fechado se, e
somente se, todos os seus vértices forem pares.
Todas estas atividades foram realizadas em uma hora e trinta minutos. Para finali-
zar a aula, uma observação interessante foi feita por um dos alunos que associou estas
atividades a outra desenvolvida no Fundamental I como "Desafios Matemáticos", de-
safio este, segundo a narração do mesmo, consistia em fazer a ligação de água, energia
e telefone em três casas, uma do lado da outra, sem que houvesse cruzamento entre
essas ligações.
6.1.2 Parte II
Na segunda parte desta atividade as duplas de alunos foram retomadas e cada dupla
recebeu uma folha de sulfite com a seguinte instrução:
Crie dois grafos para que seus colegas busquem por caminhos fechados. Apenas
um dos grafos deve possuir tal caminho. Identifique a folha com os seu nome, pois o
professor irá recolhê-la e passar para outro grupo analisar os grafos propostos.
durante a realização do que foi solicitado. As duplas com maior facilidade de raciocí-
nio acabaram criando caminhos mais elaborados, outras duplas preferiram seguir pela
lógica de desenhos mais simples, para que seus colegas tivessem menos trabalho para
resolução. Na Figura 6.8 temos o exemplo de grafos criados pelos alunos durante esta
atividade.
6.2.1 Parte I
Os alunos foram levados ao laboratório de informática da Escola e organizados em
duplas, ou seja, em cada computador havia dois alunos. Eles foram motivados a iniciar
o software, ler as instruções que trazia informações sobre uma malha aérea formada
pelos principais aeroportos da América do Sul e começar as atividades propostas pelo
software. Orientamos que a resolução das atividades deveriam ser feitas através da
representação de grafos onde os aeroportos seriam os vértices e os voos, que ligam esses
aeroportos, seriam as arestas.
Primeiro Problema (ver Figura 6.9): Elabore uma malha aérea conectando todas
as cidades (numeradas de 1 a 6) e que possibilite ir de uma cidade a outra com, no
máximo, dois voos (isto é, fazendo no máximo uma escala). Essa malha não poderá
ter mais que 9 voos.
Na figura 6.9 podemos observar as instruções dadas pelo software e uma das possí-
veis soluções propostas pelos alunos. Nosso papel na condução da atividade foi fazer as
duplas chegarem a conclusão de que o menor número possível de voos só seria possível
se estabelecessem uma cidade fixa para escala de onde sairiam os voos.
A próxima atividade associa os grafos à matrizes. Para isso as instruções dadas
foram as seguintes: se há n cidades numeradas de 1 a n construir uma matriz de ordem
n × n em que a entrada (i, j) é igual a 1 se existe voo entre as cidades i e j, ou igual a
0 se não existe voo entre elas.
3
http://m3.ime.unicamp.br/recursos/1221
Atividade 2: Aviões e Matrizes 46
Para a fixação da relação entre grafo e matrizes o software propõe mais alguns
grafos para serem transformados em matrizes. Os alunos demonstraram facilidade
nesta atividade, e quando notaram a simetria existente na matriz que representa o
grafo a atividade se tornou ainda mais simples, pois faziam a interpretação de um lado
da diagonal principal e espelhavam o outro lado. A Figura 6.11 traz as matrizes feitas
por um dos alunos.
6.2.2 Parte II
A segunda parte das atividades do software tem como título no software Voos com
mais escalas, onde o uso de matrizes para a representação das malhas aéreas começa a
ter sentido. As instruções são para que o aluno observe que, se M1 é a matriz adjacência
de um determinado grafo, seu quadrado, a matriz M12 , representa, em cada uma das
células, o número de ligações entre as cidades correspondentes com exatamente dois
voos.
Primeiro Problema (ver Figura 6.13): Seguindo esse raciocínio, preencha cada célula
da tabela abaixo com o número de voos com exatamente uma escala que podem ser
utilizados para ir de uma cidade a outra.
A compreensão do enunciado não foi tão simples para os alunos, ocorreram muitas
tentativas até que uma das duplas chegou no resultado esperado, ilustrado na Figura
6.13 e explicou a atividade para os outros colegas.
Atividade 2: Aviões e Matrizes 48
Segundo Problema (ver Figura 6.14): Agora, para entender a relação entre a matriz
com voos diretos (M1 , indicada ao lado do malha) e a matriz com voos de uma escala
(M2 , que você obteve na questão anterior),calcule no seu caderno a matriz M12 , ou seja,
M1 × M1 .
resposta é 4 voos.
Quarto Problema (ver 6.15): Qual é a matriz que representa as conexões com uma
escala?
referir a malha com o menor número possível de voos, ou seja, um grafo com a menor
quantidade possível de arestas.
Primeiro Problema (ver Figura 6.16): Construir uma malha aérea pequena,
mas que ainda assim atenda às exigências de um país, é um grande desafio. Tente
montar a menor malha possível para um país com aeroportos em oito cidades, e cuja
forma seja tal que se possa ir de uma cidade a outra com, no máximo, dois voos.
Os alunos não tiveram muita dificuldade para solucionar essa atividade, ao percebe-
rem que se centralizassem os voos em uma única cidade a construção da malha estava
pronta. Matematicamente falando, a quantidade de voos mínimos está relacionada a
quantidade n de aeroportos existentes. Ao centralizarmos as escalas na cidade A, como
fez uma das duplas de alunos que participou da atividade, veja Figura 6.16, teremos
n − 1 rotas que satisfazem o enunciado dado.
Segundo Problema (ver Figura 6.17): Modifique os trajetos de tal modo que
cada cidade tenha no máximo quatro voos. Além disso, o número total de voos não
pode passar de onze, e é imprescindível que se possa ir de uma cidade a outra com, no
máximo, três voos.
Após as duplas trocarem ideias entre si, e realizarem algumas tentativas que não
tiverem sucesso como solução, chegaram a seguinte conclusão: já que não podiam
centralizar os voos em uma única cidade, seria possível então fazer essa centralização
em duas cidades distintas e essas que tiveram os voos centralizados, seriam então
ligadas entre si, como nos mostra a Figura 6.18, que foi a solução encontrada por uma
das duplas. Nesse momento, explicamos aos alunos que, no sistema de aviação, essas
cidades que concentram um grande número de voos são chamadas de hubs.
Atividade 2: Aviões e Matrizes 51
Terceiro Problema: Discuta com seus colegas e tente determinar quantas soluções
existem para a Primeira atividade, ou seja, com essa configuração (respeitando todas
as condições impostas no enunciado e considerando um número máximo de sete voos).
Quarto Problema: Construa uma malha para o país representado na Figura 6.19
de tal modo que todas as cidades estejam conectadas por, no máximo, três voos. Porém,
como a dupla formada pelas cidades 4 e 9, 3 e 8, e 2 e 7 estão muito distantes uma da
outra, as viagens entre elas devem ser feitas com, pelo menos, dois voos.
A solução também é dada pela escolha de hubs que separem as cidades em grupos,
onde só existam as conexões permitidas. A demora em solucionar essa atividade ficou
vinculada ao tempo que as duplas levaram para concluir que as cidades 2, 3 e 4 deveriam
Atividade 2: Aviões e Matrizes 52
O objetivo geral deste trabalho foi, além de estudar a Teoria dos Grafos, verificando
seus principais resultados e suas aplicações clássicas, verificar como se daria o processo
de ensino-aprendizagem utilizando software para explorar conceitos matemáticos.
Na literatura, encontramos muitos trabalhos que exploram as potencialidades dos
recursos multimídia como elementos para o ensino de matemática, como Amaral [1],
Cyruno [4], suas referências, entre outros. Neste trabalho utilizamos as atividades da
temática que envolve a Teoria dos Grafos do Projeto M 3 - Matemática Multimídia que
vemos como um material bem elaborado para a realidade dos conteúdos abordados nas
escolas brasileiras.
Escolhemos uma escola particular da cidade de São Pedro - SP para o desenvol-
vimento de nosso trabalho, pois além de encontrarmos nela uma estrutura física com
sala de informática onde os computadores tinham as configurações exigidas para que
o software pudesse ser utilizados, também tínhamos livre acesso às salas de aula e co-
nhecíamos o nível de aprendizado que se encontravam os alunos, pois é o ambiente que
trabalhamos diariamente.
Para a realização destas atividades nas escolas públicas deste município poderíamos
encontrar os seguintes obstáculos: laboratório de informática não adequado para a
realização da atividade, indisponibilidade de aulas extras para as atividades e como
nestas escolas não conhecíamos o perfil de aprendizado dos alunos não tínhamos certeza
que eles estavam aptos para tais atividades no momento escolhido para a sua aplicação.
Os dezoito alunos que realizaram estas atividades estão atualmente cursando o se-
gundo ano do Ensino Médio e no momento que a atividade foi desenvolvida eles já
haviam estudado o conteúdo de Matrizes. Durante as atividades pudemos observar
nestes alunos uma motivação muito grande, pois o envolvimento na discussão e con-
clusão das soluções foi notado durante todas as aulas, sejam nas atividades individuais
ou em duplas.
Acreditamos que as dificuldades apresentadas por estes alunos durante as atividades
se deu por alguns motivos como, falta de concentração para realizá-la e dificuldade de
compreensão do enunciado dos exercícios propostos.
Observamos que o fato destes alunos estarem em um ambiente digital ajudou a
despertar neles a motivação e curiosidade pela aula, pois eles não estavam habituados
a ver a matemática na escola pela tela do computador. Outro ponto de interesse
dos alunos foi pelo fato das atividades apresentarem situações práticas aplicadas a
problemas do dia a dia.
Apesar de algumas escolas públicas não possuírem uma estrutura física com labo-
ratório de informática e as que possuem ter computadores ultrapassados, sucateados
ou desatualizados, outros recursos educacionais digitais como áudio e vídeo podem
53
54
[3] CARRAHER,T.N.et al. Na vida dez na escola zero - 6a. edição - São Paulo: Cor-
tez, 1991.
[5] COSTA, Polyanna Possani da. Teoria de Grafos e suas Aplicações. 2011. Disserta-
ção apresentada ao Programa de Mestrado Profissional em Matemática, UNESP,
Rio Claro, 2011.
[8] FEOFILOFF, Paulo. Exercícios de teoria dos grafos. Notas de aula da disciplina
ciência da computação proferida no IME - USP, 2012.
[9] GUEDES, Victor Emanuel Pinto. Uma abordagem para o ensino de teoria dos
grafos no ensino médio. Dissertação. Universidade Federal de Juiz de Fora, 2014.
[11] LIMA, Carlos Laercio Gomes de. Um estudo sobre teoria dos grafos e o teorema
das quatro cores. Dissertação. Universidade de São Paulo, 2016.
[12] LUCCHESI, Cláudio Leonardo. Introdução à Teoria dos Grafos. 12o. Colóquio
Brasileiro de Matemática. IMPA (Instituto de Matemática Pura e Aplicada), 1979.
[13] MALTA, Gláucia Helena Sarmento. Grafos no Ensino Médio : Uma Inserção
Possível. Dissertação (Mestrado em Ensino de Matemática) . Programa de Pós-
Graduação em Ensino de Matemática, UFRGS, Porto Alegre, 2008. Disponível
em: <http:// hdl.handle.net/10183/14829>. Acesso em: 14 set. 2016.
55
Referências 56
[14] NOGUEIRA, Daniel Klug. Introduçao a Teoria dos Grafos: Proposta para o En-
sino Médio. Dissertação (Mestrado Profissional em Matemática)-Universidade Fe-
deral de Brasíia, Brasília, 2015.
[15] QUINN, Anne. Using apps to visualize graph theory. Mathematics Teacher, v.
108, n. 8, p. 626-631, 2015.
[16] QUINN, Anne. Technology Review: Graph Theory Smartphone Apps. The College
Mathematics Journal, v. 47, n. 1, p. 67-72, 2016.
[18] SAMPAIO, João Carlos V. Quatro Cores e Matemática. - BA: II Bienal de SBM,
2004
[19] SOUSA, Lurdes. O Teorema das Quatro Cores. Millenium - Revista do ISPV, 24,
2001.