Universidade Estadual Paulista “Júlio de Mesquita Filho” Instituto de Geociências e Ciências Exatas Câmpus de Rio Claro A teoria dos grafos e sua abordagem na sala de aula com recursos educacionais digitais Flavia Fernanda Favaro Dissertação apresentada como parte dos requisitos para obtenção do título de Mestre em Matemática, junto ao Programa de Pós-Graduação – Mestrado Profissional em Matemática em Rede Nacional, do Instituto de Geociên- cias e Ciências Exatas da Universidade Estadual Paulista “Júlio de Mesquita Filho”, Câmpus de Rio Claro. Orientadora Profa. Dra. Érika Capelato 2017 Favaro, Flavia Fernanda 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. Dissertação (mestrado) - Universidade Estadual Paulista, Instituto de Geociências e Ciências Exatas Orientadora: Érika Capelato 1. Teoria dos grafos. 2. Matriz. 3. Software. 4. Recursos educacionais. I. Título. 511.5 F272t Ficha Catalográfica elaborada pela STATI - Biblioteca da UNESP Campus de Rio Claro/SP - Adriana Ap. Puerta Buzzá / CRB 8/7987 TERMO DE APROVAÇÃO Flavia Fernanda Favaro A teoria dos grafos e sua abordagem na sala de aula com recursos educacionais digitais Dissertação aprovada como requisito parcial para a obtenção do grau de Mestre no Curso de Pós-Graduação – Mestrado Profissional em Matemática em Rede Nacional, do Instituto de Geociências e Ciências Exatas da Uni- versidade Estadual Paulista “Júlio de Mesquita Filho”, pela seguinte banca examinadora: Profa. Dra. Érika Capelato Orientadora Prof. Dr. Thiago de Melo Departamento de Matemática Universidade Estadual Paulista “Júlio de Mesquita Filho” Profa. Dra. Camila Fernanda Bassetto Departamento de Ciências da Educação Universidade Estadual Paulista “Júlio de Mesquita Filho” Rio Claro, 18 de dezembro de 2017 Dedico este trabalho ao meu amado marido Taio, por estar sempre ao meu lado, me apoiando e me incentivando, e ao meu amado filho Lorenzo, que mesmo na ingenuidade de sua infância soube respeitar meus longos momentos de estudos. Agradecimentos À 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 M3 - 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. Palavras-chave: Teoria dos Grafos, Matriz, Software, Recursos Educacionais. Abstract 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 M3 - 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. Keywords: Graph Theory, Matrix, Software, Educational Resources. Lista de Figuras 1.1 Desafio das Pontes de Königsberg . . . . . . . . . . . . . . . . . . . . . 10 1.2 Desafio da coleta de lixo. . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Grafos isomorfos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1 Diagrama representativo de um grafo. . . . . . . . . . . . . . . . . . . . 13 2.2 Grafo do campeonato de vôlei . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Grafos isomorfos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 À esquerda exemplo de grafo simples e à direita exemplo de grafo completo 16 2.5 À esquerda exemplo de grafo regular os demais são exemplos de ciclo . 16 2.6 À esquerda exemplo de Grafo bipartido e à direita de um grafo nulo. . 17 2.7 Poliedros e seus Grafos. . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.8 Exemplo de Grafo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.9 Exemplo de Grafo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1 Grafo 3-conexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Qual o menor caminho até a escola? . . . . . . . . . . . . . . . . . . . . 21 4.1 Grafo das Pontes de Königsberg. . . . . . . . . . . . . . . . . . . . . . 24 4.2 Grafo euleriano e semieuleriano . . . . . . . . . . . . . . . . . . . . . . 25 4.3 Diagrama Carteiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.4 Dodecaedro e o seu grafo associado . . . . . . . . . . . . . . . . . . . . 27 4.5 Circuito Hamiltoniano . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.6 (a) Árvore (b) Floresta . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.7 Grafo e sua Árvore Geradora . . . . . . . . . . . . . . . . . . . . . . . . 30 4.8 Grafo G valorado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.1 Grafo para horário do exame final . . . . . . . . . . . . . . . . . . . . . 32 5.2 Grafo do parque. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.3 Grafo do parque. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.4 Grafo do parque. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.5 Tabuleiro Icosiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.6 Grafo para colorir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.7 Grafo colorido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.8 Cinco cores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.1 Atividade Pontes de Könisgsberg . . . . . . . . . . . . . . . . . . . . . 41 6.2 Planta simples de um Museu . . . . . . . . . . . . . . . . . . . . . . . . 42 6.3 Resolução da planta simples de um Museu . . . . . . . . . . . . . . . . 42 6.4 Planta de um museu sem um caminho fechado . . . . . . . . . . . . . . 42 6.5 Planta de um Museu sem o caminho fechado . . . . . . . . . . . . . . . 43 6.6 Ruas para entrega de jornais . . . . . . . . . . . . . . . . . . . . . . . . 43 6.7 Ruas para entrega de jornais . . . . . . . . . . . . . . . . . . . . . . . . 44 6.8 Grafos propostos pelos alunos . . . . . . . . . . . . . . . . . . . . . . . 44 6.9 Resolução e enunciado do Primeiro Problema - Parte II . . . . . . . . . 46 6.10 Resolução do Segundo Problema - Parte II . . . . . . . . . . . . . . . . 46 6.11 Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.12 Enunciado e resolução do Terceiro Problema - Parte II . . . . . . . . . 48 6.13 Enunciado e resolução do Primeiro Problema - Parte II . . . . . . . . . 48 6.14 Resolução do Segundo Problema - Parte II . . . . . . . . . . . . . . . . 49 6.15 Resolução do Quarto Problema - Parte II . . . . . . . . . . . . . . . . . 49 6.16 Resolução Primeiro Problema - Parte III . . . . . . . . . . . . . . . . . 50 6.17 Malha do segundo problema - Parte III . . . . . . . . . . . . . . . . . . 50 6.18 Solução do segundo problema - Parte III . . . . . . . . . . . . . . . . . 51 6.19 Malha para o Quarto Problema - Parte III . . . . . . . . . . . . . . . . 52 6.20 Solução do Quarto Problema - Parte III . . . . . . . . . . . . . . . . . 52 Sumário 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 3 Ciclo, Caminho e Conexidade 20 3.1 O problema do menor caminho . . . . . . . . . . . . . . . . . . . . . . 21 4 Grafos Eulerianos e Hamiltonianos 24 4.1 O problema das Pontes de Königsberg . . . . . . . . . . . . . . . . . . 24 4.2 O Problema Chinês do Carteiro . . . . . . . . . . . . . . . . . . . . . . 26 4.3 O Problema do Caixeiro Viajante . . . . . . . . . . . . . . . . . . . . . 27 5 Coloração de Grafos 32 5.1 O teorema das Quatro e Cinco Cores . . . . . . . . . . . . . . . . . . . 35 6 Atividades na Sala de Aula 39 6.1 Atividade 1: Caminho fechado e grafos . . . . . . . . . . . . . . . . . . 41 6.1.1 Parte I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.1.2 Parte II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.2 Atividade 2: Aviões e Matrizes . . . . . . . . . . . . . . . . . . . . . . . 45 6.2.1 Parte I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.2.2 Parte II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.2.3 Parte III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7 Considerações Finais 53 Referências 55 Referências 55 1 Introdução De acordo com Jurkieiwicz [10] a Teoria dos Grafos nasceu da resolução de um desafio lançado pelos moradores de Königsberg, uma cidade da extinta Prússia, que hoje é chamada Kaliningrado e se localiza na atual Rússia. No centro desta cidade haviam vertentes do Rio Pregel, que formavam duas ilhas. Havia ainda sete pontes, seis que ligavam essas ilhas à cidade e uma ponte fazia a ligação entre as duas ilhas, conforme vemos na Figura 1.1. O desafio lançado pelos moradores da cidade era o seguinte: "Seria possível atraves- sar as sete pontes do rio, passando por todas elas uma única vez, e retornar ao ponto de partida?" Figura 1.1: Desafio das Pontes de Königsberg Fonte: http://cmup.fc.up.pt/cmup/Euler. Acesso em agosto de 2016 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 1Leonardo Euler viveu em Basiléia, norte da Suíça (1707 - 1783). 10 11 Química e por G. Kirchoff na Engenharia Elétrica, mas as suas aplicações se esten- dem a outras áreas do conhecimento. Em nosso cotidiano, muitas vezes, recorremos a diagramas como estes para solucionarmos problemas deste tipo, por exemplo: Exemplo 1.1. Na Figura 1.2 temos duas situações, G1 e G2. Cada ponto a, b, c, d, e e f nestas situações representa um ponto de coleta de lixo em uma cidade e, as linhas ligando estes pontos, representam as ruas pelas quais o caminhão que recolhe o lixo, irá passar. Para evitar desperdício de combustível é possível o caminhão passar (em cada situação) uma única vez por cada rua, coletar o lixo em cada ponto, e retornar ao ponto de partida? Figura 1.2: Desafio da coleta de lixo. Fonte: Jurkieiwicz [10], 2009, p. 52. Cada estrutura G1 e G2 na Figura 1.2 é constituída de um conjunto de pontos e um conjunto de ligações entre eles. Esta estrutura é que chamamos de grafo. Para resolver o problema em G1 apresentado na Figura 1.2 podemos fazer o seguinte percurso: a− b− c− d− e− f − a− d− b− e− a. Para o problema G2 podemos fazer o seguinte percurso: a− e− b− d− c− b− a− d− e. Observamos com estas soluções que, no caso do problema G1, é possível sair de um ponto, fazer o percurso passando uma única vez por cada rua e, retornar ao mesmo ponto. No problema G2, começamos num ponto e terminamos em outro. Chamamos o grafo da situação G1 de euleriano e o da situação G2 de semieuleriano. Vamos discutir mais sobre os tipos de grafos durante este texto. 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. Figura 1.3: Grafos isomorfos Fonte: [15], p. 627. Assim, para contribuir com a literatura, neste trabalho estudamos os principais resultados e definições da teoria dos grafos. Além disso, trabalhamos na sala de aula do segundo ano do Ensino Médio de uma escola particular da cidade de São Pedro - SP a abordagem deste tema com os recursos educacionais digitais propostos na coleçãoM3 - Matemática Multimídia. Nesta coleção há mais de 350 mídias como: vídeo, áudio, software e experimento, em formato digital como material didático para o ensino de Matemática no Ensino Médio. O projeto que criou este material foi desenvolvido por uma equipe de professores e estudantes da Unicamp e profissionais externos, e todo o material está disponível no site http://m3.ime.unicamp.br/ e também no portal do professor http://portaldoprofessor.mec.gov.br/index.html para livre utilização dos professores. Este trabalho está organizado da seguinte forma: No capítulo 2 descrevemos as primeiras noções de grafos abordando os conceitos iniciais da teoria, como por exemplo, grafo simples, planar, conexo, grau de um grafo, grafos isomorfos, representação de grafos por matrizes, entre outros. No capítulo 3 fazemos um breve estudo sobre ciclo, caminho, conexidade e gra- fos valorados, estas definições serão importantes para discutirmos os resultados dos capítulos seguintes. No capítulo 4 apresentamos definições e resultados de grafos eulerianos e hamiltoni- anos, os quais são necessários para a resolução do Problema das Pontes de Königsberg, do Problema Chinês do Carteiro e do Problema do Caixeiro Viajante. No capítulo 5 fazemos um breve estudo sobre coloração de grafos e apresentamos O Problema das Cinco Cores, o qual foi obtido a partir de tentativas de se resolver O Problema das Quatro Cores. No capítulo 6, com objetivo de apresentarmos uma aplicação da temática deste estudo à Educação Básica descrevemos, além dos exercícios escolhidos da coleção M3 - Matemática Multimídia para serem aplicados à sala de aula, os resultados obtidos pelos alunos que participaram das atividades. 2 Primeiras Noções Neste capítulo vamos abordar as noções preliminares sobre a Teoria de Grafos. O objetivo é apresentar resultados sobre o grau de um vértice, os tipos de grafos e isomorfismos entre eles, bem como a sua representação através de matrizes. Os resultados foram retirados de Jurkieiwicz [10] e Lucchesi [12]. Definição 2.1. Um grafo G consiste em um conjunto finito V de elementos cha- mados vértices, um conjunto finito A de elementos chamados arestas e uma função de incidência que associa a cada aresta de A um par não ordenado de vértices (não necessariamente distintos) de V, chamado de extremos desta aresta. 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. Figura 2.1: Diagrama representativo de um grafo. Fonte: Lucchesi [12], p. 02. 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} Definição 2.2. Chamaremos vértices adjacentes quando estes são extremidades de uma aresta. Neste caso diremos que a aresta é incidente a estes vértices. O tamanho de um grafo é dado pela soma do número de vértices com seu número de arestas. O grau de um vértice v é dado pelo número de arestas que incidem sobre ele e será denotado por d(v). Por convenção, um grafo sem arestas e sem vértices é chamado de vazio e seu tamanho é zero. Para determinar o grau de um nó contamos o laço duas vezes. 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. Os próximos resultados formalizam algumas observações apresentadas no exemplo acima. 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,∑ v∈V (G) d(v) = 2 ·m. Demonstração: Quando contamos os graus dos vértices de um grafo G, esta- mos contando as extremidades de suas arestas uma vez, só que cada aresta tem duas extremidades, logo cada aresta é contada duas vezes. � Corolário 2.1. Todo grafo G possui um número par de vértices de grau ímpar. Demonstração. Se tivéssemos um número ímpar de vértices de grau ímpar a soma dos graus seria ímpar. Mas a soma dos graus é o dobro do número de arestas e, portanto é sempre um número par. � 15 Definição 2.4. Chamamos de vizinhança aberta de v, o conjunto de vértices adja- centes a v e denotamos esse conjunto por N(v). Chamaremos de vizinhança fechada de v a união do conjunto de vértices adjacentes com o próprio vértice, sendo denotada por N [v] = N(v) ∪ {v} Exemplo 2.3. Considere que um campeonato de vôlei será disputado pelas equipes 6A, 6B, 7A, 7B, 8A e 8B. Os jogos ocorrerão segundo o grafo da Figura 2.2: Figura 2.2: Grafo do campeonato de vôlei Fonte: Jurkieiwicz [10], p. 06. 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. Figura 2.3: Grafos isomorfos. Fonte: Jurkieiwicz [10], p. 06. 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 2.1 Alguns tipos de grafos Definição 2.6. Chamamos de subgrafo de um grafo G, qualquer grafo H quando este é constituído de um subconjunto de vértices e arestas de G, ou seja V(H) ⊆ V(G) e A(H) ⊆ A(G). Caso V(H) 6= V(G) ou A(H) 6= A(G) o subgrafo H é chamado de próprio. Definição 2.7. Um grafo G é conexo se G = G1 ∪G2, onde G1 e G2 são grafos com G1 ∩ G2 = ∅, implicar G1 = ∅ ou G2 = ∅. Sejam G um grafo e v ∈ V. O maior subgrafo conexo de G que contém v é a componente conexa de G contendo v. Definição 2.8. Grafo Simples (veja o exemplo à esquerda na Figura 2.4): É aquele que não contém laços nem múltiplas arestas. Grafo Completo (veja o exemplo à direita na Figura 2.4): É um grafo, onde todo par de vértice é ligado por uma aresta. Um grafo completo com n vértices é denotado por Kn. Por exemplo, o grafo à direita na Figura 2.4 é K5. Grafo Regular (veja o primeiro grafo à esquerda na Figura 2.5): é aquele que todos os seus vértices possuem o mesmo grau. Ciclo (veja o primeiro e segundo grafo, à partir da direita na Figura 2.5): Um ciclo é um grafo regular de grau 2. Grafo Bipartido (veja o grafo à esquerda na Figura 2.6): um grafo G é bipartido se o conjunto V de vértices pode ser dividido em subconjuntos disjuntos V1 e V2 tal que toda aresta de G tem uma extremidade em V1 e outra em V2. Grafo Nulo (veja o grafo à direita na Figura 2.6): temos um grafo nulo quando não existem arestas ligando seus vértices. 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 Figura 2.6: À esquerda exemplo de Grafo bipartido e à direita de um grafo nulo. Fonte: Jurkieiwicz [10], p. 20. Definição 2.9. Um grafo é planar se é possível desenhá-lo em um plano π sem que suas arestas se cruzem. Alguns exemplos de grafos planares são as representações no plano dos sólidos platônicos: tetraedro, octaedro, cubo, dodecaedro e icosaedro, veja a Figura 2.7. Assim, se um grafo G é planar, sua representação divide o plano π em regiões chamadas faces. Uma face F de um grafo G é uma componente conexa de π−G. Se esta componente é ilimitada dizemos que F é uma face infinita. Cada um dos grafos que são ciclos na Figura 2.5 dividem o plano em duas regiões, ou seja, possuem duas faces (ou seja, duas componentes conexas) e uma delas é infinita. Figura 2.7: Poliedros e seus Grafos. Fonte: Jurkieiwicz [10], p.95. A relação entre o número de arestas, vértices e faces de um grafo planar conexo demonstrada por Euler em 1752 é conhecida como a fórmula de Euler e é uma das mais conhecidas da matemática. Se o número de arestas é designado por m, o de vértices por n e o de faces por f , podemos enunciar a fórmula de Euler por: Teorema 2.2. Num grafo planar conexo vale f −m+ n = 2. Demonstração: Faremos a demonstração por indução sobre m. Suponhamos G um grafo planar conexo, se m = 0, então G é um grafo nulo, como G é conexo devemos ter n = 1 e assim f = 1, portanto a fórmula é válida. Suponha agora que a fórmula seja válida para todo grafo planar conexo com m− 1 arestas. Seja G um grafo conexo com m arestas. Se G não contém ciclos, temos m = n− 1, pois G possui n vértices. Como G não possui ciclos π −G é uma componente conexa, ou seja, G possui uma face. Assim, f −m+ n = 1− (n− 1) + n = 2, como queríamos. Caso G possua um ciclo, seja C este ciclo e a uma aresta de C. Então o grafo G − a é conexo com n vértices, m − 1 arestas e f − 1 faces (pois ao retirarmos uma aresta Representação de grafos por Matrizes 18 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. � 2.2 Representação de grafos por Matrizes Uma das formas mais comuns de descrever a estrutura de um grafo para o com- putador é usando matriz. A seguir, vamos apresentar duas formas de representar matricialmente um grafo. Definição 2.10. Seja G um grafo de n vértices v1, v2, · · · , vn, e m arestas a1, a2, ... , am e nenhum laço. A matriz de incidência é uma matriz de ordem m× n, onde o valor de cada elemento ejk da matriz é determinado da seguinte forma: ejk = { 1, se a aresta aj incide no vértice vk 0, caso contrário Exemplo 2.5. Faça a representação, usando a matriz de incidência, do grafo da Figura 2.8. Figura 2.8: Exemplo de Grafo. A matriz resultante será  1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 1  Nas matrizes de incidência podemos identificar algumas propriedades: • Como cada aresta é ligada a dois vértices, cada linha possui dois números 1; • A quantidade de número 1 em cada coluna é igual ao grau do vértice que corres- ponde a esta coluna; • Se uma coluna possui só 0 ela é um vértice isolado. Representação de grafos por Matrizes 19 Definição 2.11. Seja G um grafo simples de n vértices v1, v2, · · · , vn e n arestas a1, a2, ... , an. A matriz de adjacência é uma matriz quadrada de ordem n × n e o valor de cada um de seus elementos ejk é dado da seguinte forma: ejk = { 1, se os vértices vj e vk são ligados por arestas 0, caso contrário Exemplo 2.6. Faça a representação, usando a matriz de adjacência, do grafo da Figura 2.9. Figura 2.9: Exemplo de Grafo. A matriz resultante será  0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0  Nas matrizes adjacências também podemos identificar algumas propriedades: • Num grafo que não possui laço a diagonal principal é composta somente pelo número 0; • O grau de um vértice é igual a quantidade de números 1 de sua fila (linha ou coluna); • A partir da matriz é possível construir seu grafo. As matrizes de incidência e adjacência são formas simples de representar grafos. Computacionalmente, os cálculos a partir destas matrizes resolvem muitas situações práticas. 3 Ciclo, Caminho e Conexidade Neste capítulo todos os resultados foram retirados de Jurkieiwicz [10] e antes de enunciarmos as definições e os resultados faremos a seguinte consideração: Se um grafo possui, por exemplo, os vértices v e w ligados por uma aresta, vamos denotá-la por (v, w) e, quando não houver confusão, simplesmente por vw. Definição 3.1. Um passeio é uma sequência de arestas do tipo v0v1, v1v2, · · · , vs−1vs e s é o comprimento do passeio. Se o passeio possui arestas distintas ele é chamado trilha porém, se v0 = vs o passeio é chamado trilha fechada. Se além das arestas, todos os vértices são distintos temos um caminho e se v0 = vs temos um ciclo ou caminho fechado. A conexidade também pode ser definida através da observação de que um grafo G é conexo se, e só se, existe um caminho entre dois vértices quaisquer. Para isto estamos considerando que entre um vértice e ele mesmo existe um caminho de comprimento zero. Além disso, o menor comprimento possível entre os vértices v e w de um grafo é chamado distância entre v e w. Definição 3.2. Dizemos que um grafo é k-conexo se ao retirarmos k − 1 vértices do grafo, ele continua conexo. Figura 3.1: Grafo 3-conexo Fonte: Jurkieiwicz [10], p. 20. 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 Demonstração: (⇒) Seja G bipartido com os conjuntos de partição V1 e V2. Quando não há ciclos em G, não há o que provar. Se há um ciclo em G este alterna vértices de V1 e V2. Partindo de V1, por exemplo, para retornar ao ponto de partida utilizaremos um número par de arestas. O ciclo é, portanto, de comprimento é par. (⇐) Seja G um grafo com no mínimo dois vértices e que não contem ciclos de com- primento ímpar. Podemos considerar, sem perda de generalidade, G um grafo conexo, pois caso contrário, consideraríamos cada componente conexa separadamente. Vamos particionar o seu conjunto de vértices em dois subconjuntos V1 e V2, independentes e disjuntos. Tomamos um vértice v qualquer, o subconjunto V1 será constituído de todos os vértices w que possuam um caminho de comprimento par entre v e w. O subconjunto V2 será constituído por todos os vértices w tais que haja um caminho de comprimento ímpar entre v e w. Os conjuntos V1 e V2 são disjuntos, pois se w perten- cesse aos dois conjuntos ao mesmo tempo, existiria um caminho de comprimento par e outro de comprimento ímpar ligando v e w. Esses dois caminhos podem se cruzar (ou não) antes de chegar em w, produzindo alguns ciclos. Como o número de arestas usando estes ciclos é ímpar (é a soma do número de arestas dos dois caminhos) isto produziria pelo menos um ciclo ímpar em G, contrariando a hipótese. � 3.1 O problema do menor caminho Nessa seção trataremos do problema do menor caminho, o qual é relativamente simples mas que nos proporciona muitas abordagens matemáticas relacionadas à Teoria dos Grafos. Por exemplo, se o João sai de sua casa para ir à escola qual é o menor caminho que ele pode fazer, considerando que existem muitas ruas que o leva ao seu destino? Veja Figura 3.2. Figura 3.2: Qual o menor caminho até a escola? Fonte: Jurkieiwicz [10], p. 32. O problema do menor caminho 22 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 Adicionando a esse percurso o caminho até a escola teremos: • 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. Pelo apresentado, notamos que o algoritmo de Dijkstra se inicia em uma estimativa para a escolha do caminho mais curto, entre um vértice dado como inicial, até um vértice dado como o final. Essa estimativa vai se ajustando no decorrer das análises e um vértice é considerado fechado quando o caminho até ele é o mais curto, se isso não ocorre ele é classificado como aberto. Assim que todos os vértices são classificados como fechados, os percursos são comparados e o menor caminho é determinado. 4 Grafos Eulerianos e Hamiltonianos O objetivo deste capítulo é conceituar e diferenciar os Grafos Eulerianos dos Grafos Hamiltonianos. Os resultados foram retirados de Jurkieiwicz [10]. 4.1 O problema das Pontes de Königsberg Voltando ao Problema das Pontes de Königsberg, a discussão entre os moradores da cidade era a seguinte: No centro da cidade de Königsberg havia vertentes do Rio Pregel, que formavam duas ilhas. Havia sete pontes, seis que ligavam estas ilhas à cidade e uma ponte que fazia a ligação entre as duas ilhas, conforme a Figura 4.1. É possível atravessar as sete pontes, passando por todas elas uma única vez e retornar ao ponto de partida? O diagrama que representa este problema é como na Figura 4.1 onde os vértices a, b, c e d são as margens e as ilhas, e as arestas correspondem às pontes. Para este problema ter solução, é preciso traçar uma trilha fechada contendo todas as arestas. A pergunta de Euler então foi saber qual grafo tinha estas propriedades. Figura 4.1: Grafo das Pontes de Königsberg. Fonte: Jurkieiwicz [10], 2009, p. 46. 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 Figura 4.2: Grafo euleriano e semieuleriano Fonte: Jurkieiwicz [10], p. 52. 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. Demonstração: Se o grafo G possui laços ou arestas múltiplas não temos o que provar, pois, G possui um ciclo. Consideremos então apenas grafos simples. Iniciemos nossa trilha em um vértice v0 qualquer. Quando chegamos em qualquer vértice ou é a primeira vez que passamos por ele, e então podemos continuar pois o grau é maior ou igual a dois, ou já passamos por ele produzindo assim um ciclo. Como o número de vértices é finito, o lema está provado. � Teorema 4.1. (Teorema de Euler (1736)) Um grafo conexo G (não necessariamente simples) é euleriano se, e somente se, todos os seus vértices tem grau par. Demonstração: (⇒) Suponha que G possua uma trilha fechada de comprimento m. Cada vez que a trilha passa por um vértice utiliza duas arestas, uma aresta para entrar e outra para sair. Logo, o grau de cada vértice é obrigatoriamente par. (⇐) Usaremos indução sobre o número de arestas m do grafo. Por vacuidade o teorema é válido quando m = 0. Suponhamos que o teorema seja válido para todos os grafos com menos de m arestas. Sendo G conexo todos os seus vértices possuem grau maior ou igual que dois, pois os graus são pares. Pelo Lema 4.1 G possui um ciclo (que é uma trilha fechada). Dentre todas as trilhas fechadas em G selecionamos uma trilha T de comprimento máximo. Se T tem comprimento igual a m, o teorema está provado. Caso contrário, consideremos o grafo H resultado da exclusão das arestas de T . Como retiramos um número par arestas de cada vértice de T e pela hipótese todos os vértices do grafo possuem grau par, ao menos uma das componentes de H tem um vértice em comum com T e tem todos os vértices com grau par. Pela hipótese de indução, H possui uma trilha fechada que passa por todos os seus vértices, e podemos formar uma trilha fechada concatenando T com a trilha em H. Porém, isso contraria a maximalidade na escolha de T . � O Problema Chinês do Carteiro 26 Corolário 4.1. Um grafo conexo G (não necessariamente simples) é semieuleriano se, e somente se, no máximo, dois vértices têm grau ímpar. 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: 4.2 O Problema Chinês do Carteiro Em Jurkieiwicz [10] o autor apresenta O Problema Chinês do Carteiro e o conceitua de forma significante como grafos eulerianos. O problema não recebe esse nome por causa da nacionalidade do carteiro e sim pela nacionalidade do pesquisador que o estudou pela primeira vez, o matemático Mei-Ku Kuan em 1962. A proposta do problema é tornar menor possível, a distância que um carteiro irá percorrer, por todas as ruas de uma cidade. Sabemos que se o grafo for euleriano não teremos problemas em minimizar esse percurso, mas se não for, teremos que torná-lo euleriano. Lembramos que, o número de vértices de grau ímpar é par (veja Corolário 2.1) logo, poderemos unir pares de vértices por novas arestas, tornando-os pares. É óbvio que não serão construídas novas ruas, mas o carteiro deverá percorrer ruas repetidas, de forma que o caminho se torne o menor possível. A situação apresentada pelo problema em questão é bastante interessante, pois sua solução traz economia de tempo e de custos. Da mesma forma que fizemos no problema do menor caminho, para resolver este problema também trabalhamos com grafos valorados. Ou seja, existe uma função f : A → R+ relacionando o conjunto de arestas A de um grafo a um conjunto de números positivos que pode indicar o comprimento, custo, tempo, ou o que a estruturação do problema exigir. Figura 4.3: Diagrama Carteiro Fonte: Jurkieiwicz [10], p. 57. 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 o menor caminho entre os vértices a e b. Nesse caso, pelo algoritmo de Dijkstra a melhor forma de tornar este grafo euleriano é construir uma “aresta virtual” entre os vértices a e b, ou seja, percorrer o caminho av2, v2v3, v3v4, v4b como se fosse uma aresta. 4.3 O Problema do Caixeiro Viajante Segundo Sampaio [18] um dos problemas gerais com grafos é conhecido como O Problema do Ciclo Hamiltoniano originado em 1859 quando o matemático Willian Rowan Hamilton (1805-1865) apresentou o jogo chamado The Icosian Game. O jogo consiste em um tabuleiro em forma de dodecaedro, veja a Figura 4.4, onde cada um dos 20 vértices são nomeados com nomes de cidades importantes do mundo. O objetivo do jogo é percorrer o dodecaedro utilizando as suas 30 arestas, passando por cada cidade uma única vez, começando e terminando na mesma cidade, isto é possível? Figura 4.4: Dodecaedro e o seu grafo associado Fonte: Costa [5], p.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. Figura 4.5: Circuito Hamiltoniano Fonte: Jurkieiwicz [10], p.59. Na Figura 4.5 temos um exemplo de circuito hamiltoniano e o grafo do dodecaedro na Figura 4.4 é um exemplo de grafo hamiltoniano. O Problema do Caixeiro Viajante 28 O problema de saber se um grafo é ou não hamiltoniano (ou seja, possui um ciclo hamiltoniano) é, segundo Jurkieiwicz [10], um dos mais estudos na Teoria dos Grafos, devido a sua aplicabilidade em comunicação e transporte, mas os teoremas encontrados estão longe de dar uma solução elegante mostrando condições necessárias e suficientes para um grafo ser hamiltoniano. O que conhecemos é o Teorema de Dirac 4.2 que dá uma condição suficiente para um grafo G ser hamiltoniano impondo condições sobre o seu grau mínimo δ(G). Para demonstrar este resultado precisamos do seguinte lema que pode ser encon- trado em Costa [5]: Lema 4.2. Seja G um grafo de ordem n. Se δ(G) ≥ n−1 2 , então G é convexo. Demonstração: Mostremos por indução. Se n = 1, δ(G) ≥ 0 = n−1 2 , e claramente G é conexo. Suponhamos que δ(G) ≥ n−1 2 implica G conexo. Se G tem ordem n+1 e δ(G) ≥ (n+1)−1 2 = n 2 > n−1 2 , fixamos um v ∈ V(G) e tomamos H sugbrafo de G com V(H) = V(G)− {v} e A(H) = A(G)− {vwi;wi ∈ N(v)}. Assim, H tem ordem n e δ(H) ≥ δ(G) > n−1 2 e, por hipótese de indução, é conexo. Como G é obtido de H adicionando o vértice v e as arestas conectando v ao H, segue que G é conexo. � Teorema 4.2. (Teorema de Dirac) Seja G um grafo simples de ordem n ≥ 3. Se δ(G) ≥ n 2 , então G é Hamiltoniano. Demonstração: Suponhamos que G não seja hamiltoniano. Seja P um caminho v1v2...vp em G com comprimento máximo, e portanto, todo vértice adjacente de v1 e de todo vértice adjacente de vp estão em P com (d(v1), d(vp) ≤ p − 1) e como δ(G) ≥ n 2 , v1 e vp tem no mínimo n/2 vizinhos em P . Afirmamos que deve existir algum j com 1 ≤ j ≤ p − 1, tal que vj ∈ N(vp) e vj+1 ∈ N(v1). Suponhamos que este não seja o caso, ou seja, se vj ∈ N(vp) então vj+1 /∈ N(v1). Assim, como d(vp) ≥ δ(G) ≥ n 2 então d(v1) ≤ p− 1− n 2 < n− n 2 = n 2 , contrariando a hipótese de δ(G) ≥ n 2 . Agora, seja o ciclo C = v1v2...vjvpvp−1...vj+1v1, com os mesmos vértices de P , porém com vjvp e vj+1v1 arestas a mais. Como G é não Hamiltoniano, existe no mínimo um vértice w de G que não está em P . Mas, como δ(G) ≥ n 2 ≥ n−1 2 , pelo Lema 4.2, G é conexo e portanto w deve ser adjacente a algum vértice vi de P . Tomando o caminho em G que começa em w, passa por vi, e continua o ciclo C obtemos um caminho mais longo que P , o que é um absurdo. Logo não podemos ter G não Hamiltoniano, ou seja, G é Hamiltoniano. � 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 menor possível? Este problema também é conhecido como problema de conexão do peso mínimo. A representação da situação se dá através de um grafo onde, as cidades são os vértices, e o caminho entre elas, as arestas. Como construir tal ciclo e ainda com o menor “peso”? Para responder precisamos das seguintes definições e resultados abaixo. 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. Figura 4.6: (a) Árvore (b) Floresta Fonte: Costa [5], p.30. 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. 2. T não contém ciclos e tem n− 1 arestas. 3. T é conexo e tem n− 1 arestas. 4. T é conexo e toda aresta é uma ponte. 5. Todo par de vértices de T é ligado por um único caminho. 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 ′ e T ′′ com n′ e n′′ vértices respectivamente, onde n = n′+n′′. Por indução em n, temos que T ′ possui n′ − 1 aresta e T ′′ possui n′′ − 1 , ao acrescentarmos a aresta que liga u a v, teremos o número de arestas de T dado por (n′ − 1) + (n′′ − 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. � Definição 4.4. Temos uma árvore geradora T de um grafo G, quando T é uma árvore de G que possui todos os vértices de G. Na Figura 4.7 temos o exemplo de um Grafo G e de uma árvore geradora T de G. Figura 4.7: Grafo e sua Árvore Geradora Fonte: Autora Agora vamos voltar ao Problema do Caixeiro Viajante considerando como exemplo o grafo completo e valorado da Figura 4.8. O Teorema 4.2 garante que este grafo é Hamiltoniano, mas não dá uma maneira de encontrarmos o ciclo hamiltoniano de menor peso. Uma maneira seria calcular o peso de todos os possíveis ciclos hamiltonianos, mas esta solução é inviável devido a grande quantidade de possibilidades que teríamos num grafo com ordem n muito grande. Assim, um procedimento para encontramos tal ciclo consiste primeiramente em encontramos a sua árvore geradora de menor valor: Exemplo 4.1. Dado o grafo G valorado representado na Figura 4.8, qual sua árvore geradora de menor valor? Para a resolução desse problema utilizaremos o algoritmo de Kruskal, que con- siste em escolher as arestas de menor valor e, se um ciclo não é formado, as acrescen- tamos à nossa árvore, do contrário são descartadas. Quando haver n− 1 arestas, nossa árvore está formada. No caso deste grafo sua ordem é n = 5 e temos como aresta de menor valor ec⇒ 6, depois a aresta ae ⇒ 40, em seguida temos um empate entre as arestas ac ⇒ 42 e O Problema do Caixeiro Viajante 31 Figura 4.8: Grafo G valorado Fonte: Jurkieiwicz [10], p.69. bd ⇒ 42, ou seja, poderíamos escolher qualquer uma, mas a aresta ac formaria um ciclo com as demais logo, é descartada. Dando prosseguimento ao algorítimo, ao escolhermos a próxima aresta de menor valor temos novamente um empate entre as arestas ed⇒ 44 e bc⇒ 44, como podemos escolher qualquer uma delas, vamos optar pela aresta bc. Como já temos 4 arestas nossa árvore está completa: ae− ec− cb− bd⇒ 132. Teorema 4.4. O algoritmo de Kruskal fornece uma solução ótima. Demonstração: Através do algoritmo chegamos a árvore geradora T . Agora supo- nhamos que T não tenha peso mínimo, ou seja, existe T ′ que possui um peso menor que T . Seja e a primeira aresta escolhida para T que não pertence a T ′. Se adicionarmos e a T ′ teremos um ciclo que contém uma aresta ek que não pertence a T . Retiramos então a aresta ek e conseguimos uma árvore T ′′ com peso menor que T . Só que neste caso, a aresta ek teria sido escolhida pelo algoritmo no lugar de e, o que nos prova que o algoritmo constrói efetivamente uma árvore de menor peso. � 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 Este capítulo tem o objetivo de apresentar alguns conceitos e resultados importantes para estudarmos o Problema das Quatro Cores, uma aplicação interessante da Teoria dos Grafos que busca encontrar o número mínimo de cores usadas para colorir um mapa, de acordo com algumas regras. Estes conceitos e resultados foram o retirados de Costa [5] e Jurkieiwicz [10]. Já abordagem histórica do Problema das Quatro Cores foi estudada a partir de Sousa [19]. Definição 5.1. Dizemos que um conjunto de vértices em um grafo G é independente se seus vértices são dois a dois não adjacentes, ou seja, não estão ligados. O número de independência, denotado por α(G), é a cardinalidade do subconjunto independente máximo de vértices do grafo. Exemplo 5.1. O grafo da Figura 5.1 representa a incompatibilidade de horários entre professores que devem aplicar um exame final. Os vértices são ligados por uma aresta se estes representarem professores que possuem um aluno em comum que farão o exame final. Qual o maior número de professores que pode dar prova ao mesmo tempo? A resposta é dada pelo subconjunto independente máximo de vértices do grafo. O sub- conjunto assinalado com quadrados na Figura 5.1 é o conjunto com estas característica, ou seja, α(G) = 4. Assim, o número máximo de professores que darão prova ao mesmo tempo será 4. Figura 5.1: Grafo para horário do exame final Fonte: Jurkieiwicz [10], p.74. Definição 5.2. Dizemos que um conjunto independente I é maximal se não existe um conjunto independente J com I ⊆ J e é máximo se |I| ≥ |J |, para todo conjunto independente J . 32 33 Todo conjunto independente máximo é um conjunto independente maximal, mas a recíproca não é verdadeira, como mostra o exemplo abaixo. 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: 1. A barraca só pode ser instalada em uma esquinas (vértices) e 2. Esquinas próximas (vértices adjacentes) só admitem uma barraca. Figura 5.2: Grafo do parque. Fonte: Jurkieiwicz [10], p.75. Para instalar o número máximo de barracas procuramos o conjunto independente máximo. Na Figura 5.3 à esquerda temos um conjunto independente maximal, ou seja, não podemos acrescentar mais barracas de sorvete. À direita também temos um conjunto independe, porém com quase o dobro de barracas. Figura 5.3: Grafo do parque. Fonte: [10], p.75. 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). Quando em uma situação problema precisamos dividir o conjunto de vértices de um grafo em um conjunto de vértices independente disjuntos, surge então a necessidade da aplicação da coloração. 34 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: Teorema 5.1. Para todo grafo G tem-se que χ(G) ≤ ∆(G) + 1 Demonstração: Colorimos cada vértice. Cada vértice pode ser adjacente a, no máximo, ∆(G) vértices logo, sempre haverá uma cor para atribuirmos ao próximo vértice. � Teorema 5.2. Um grafo G é bipartido se, e somente se, χ(G) = 2 Demonstração: Basta atribuir uma cor a cada partição independente do grafo G. � 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: • Uma barraca deve ser localizada em uma esquina (vértice); • Esquinas próximas (vértices adjacentes) só admitem barracas com serviços dife- rentes. Por motivos comerciais, o desafio é encontrar o menor número de barracas que podemos usar, evitando a diversificação excessiva de serviços. A Figura 5.4 mostra que podemos colorir os vértices com apenas três cores para a identificação de cada tipo de serviço, esse é o número mínimo. Figura 5.4: Grafo do parque. Fonte: [10], p.78. O teorema das Quatro e Cinco Cores 35 5.1 O teorema das Quatro e Cinco Cores Segundo Sousa [19] sua história iniciou-se em 1852, quando Francis Guthrie pintava em um mapa da Inglaterra com muitos distritos, de forma que distritos vizinhos não fossem coloridos da mesma cor, ele muito refletiu sobre o problema e concluiu que qualquer mapa poderia ser colorido por no mínimo quatro cores seguindo suas regras. Francis Guthrie foi advogado, botânico e matemático, e tinha um irmão mais novo chamado Frederick Guthrie, que era aluno do famoso matemático e lógico britânico Augustus De Morgan. Quando Frederick apresentou para De Morgan a conjectura de seu irmão mais velho, este ficou extremamente entusiasmado e imediatamente escreveu uma carta para Sir Willian Rowan Hamilton para informá-lo sobre o problema. Ao contrário de De Morgan, este não se empolgou tanto com o problema, mas Morgan no entanto, escreveu cartas para outros matemáticos que discutiram o problema. Essas discussões tiveram algum desenvolvimento, porém, depois de 1860, por 20 anos, o problema das quatro cores deixou de ser discutido, mas não esquecido, tanto que, em 1879, Alfred Bray Kempe publicou a demonstração completa do Teorema das Quatro Cores no American Journal of Mathematics. Tal demonstração foi estudada por vários matemáticos que até chegaram a sugerir melhorias em sua demonstração. Em 1890, Percy John Heawood encontrou um sutil erro na demonstração e lamentou- se em não poder apresentar uma demonstração alternativa para o teorema, porém provou o Teorema das Cinco Cores, aumentando de quatro para cinco a quantidade mínima de cores necessárias para a resolução do problema em questão. Somente em 1976, com a ajuda de um computador, Kenneth Appel e Wolfgang Ha- kem apresentaram enfim uma demonstração para o Teorema das Quatro Cores. Apesar da notícia ter sido recebida com grande euforia pelos matemáticos, assim que souberam que a prova ocorreu por intermédio de inúmeros cálculos feitos por um computador e que seria impossível de ser conferida à mão, essa alegria diminuiu drasticamente. A demonstração foi aceita, mas ainda é motivo de discussões e alguns matemáticos con- tinuaram a procurar uma demonstração mais simples. Em 1994, Paulo D. Seymour apresentou uma resolução simplificada deste teorema, contando com a ajuda de Neil Robertson, Daniel P. Sanders e Robin Thomas, mas essa demonstração, apesar de mais simples, não dispensou a ajuda do computador. Até hoje a demonstração que dispensa a ajuda do computador ainda não foi encontrada, ou seja é um problema aberto! Em Jurkieiwicz [10] o autor apresenta uma formulação do teorema das quatro cores em forma de coloração de vértices: Teorema 5.3. (Teorema das 4 cores) Num grafo planar G tem-se que χ(G) ≤ 4. Em Sampaio [18] encontramos o seguinte Teorema sobre as quatro cores mínimas para se colorir um grafo: Teorema 5.4. Se um grafo admite um circuito hamiltoniano, então suas faces podem ser coloridas com quatro cores. Demonstração: Tomemos um circuito hamiltoniano em um grafo plano, onde o agrupamento de suas arestas divide o plano em duas regiões, uma limitada, interior à curva, e outra constituída dos pontos exteriores à curva. Através da observação da Figura 5.5 temos no item (a) um tabuleiro "icosiano", onde nele é traçado um circuito hamiltoniano (em azul), em (b) é utilizado duas cores para preencher de forma alter- nada as faces interiores do circuito, em (c), com duas outras cores, de forma também O teorema das Quatro e Cinco Cores 36 Figura 5.5: Tabuleiro Icosiano Fonte: Sampaio [18], p. 22. 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. � Para uma melhor compreensão do teorema 5.4 utilizaremos um exercício encontrado em Sampaio [18]: Exemplo 5.4. Construa um circuito hamiltoniano no grafo representado pela Figura 5.6 e use-o para colorir as faces com 4 cores. Note que na Figura 5.7 temos no item (a) a coloração feita com o mesmo circuito hamiltoniano construído no Teorema 5.4, realizando o mesmo processo de coloração exceto a coloração da região que envolve todo o tabuleiro icosiano. No item (b) para a coloração do restante do grafo construiremos um segundo circuito hamiltoniano, colorindo alternadamente a parte interna do circuito, com duas cores já utilizadas no primeiro. No item (c) colorimos as regiões externas ao circuito com as outras duas cores restantes também de forma alternada. No item (d) chegamos na coloração final do mapa. Como comentamos na introdução desta seção, as várias tentativas de resolução do teorema das quatro cores fizeram com que em 1890 Percy John Heawood demonstrasse um resultado um pouco mais fraco, o Teorema das Cinco Cores. Para demonstrá-lo utilizamos o seguinte lema: O teorema das Quatro e Cinco Cores 37 Figura 5.6: Grafo para colorir Fonte: Sampaio [18], p. 23. Figura 5.7: Grafo colorido Fonte: Coloração feita pela autora. 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 Figura 5.8: Cinco cores Fonte: Jurkieiwicz [10], p.104. 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 Muitas vezes ao iniciarmos um conteúdo em sala de aula os alunos já se assustam só com o nome. Ou porque apresentamos o conteúdo já com definições muito teóricas e fórmulas que não fazem sentido para eles, ou porque o conteúdo não se aplica a realidade na qual ele está inserido. Acreditamos que uma forma de conquistar atenção dos alunos para determinado conteúdo é mudar a forma como o mesmo é apresentado. Se a apresentação for feita com um problema desafio e só depois de várias tentativas é que a teoria formal é exposta, teremos por parte dos alunos um maior interesse e um maior envolvimento, uma vez que ele participou ativamente do processo de ensino- aprendizagem. Ao prepararmos nossas aulas, principalmente na educação inicial, temos que nos atentar à realidade dos alunos e se o conteúdo a ser trabalhado traz uma forma que realmente os incentive a construir pontes entre a matemática da escola e a matemática de seu cotidiano. De acordo com Carraher [3] a aprendizagem de matemática na sala de aula é um momento de interação entre a matemática organizada pela comunidade científica, ou seja, a matemática formal e a matemática como atividade humana. Sendo assim, quando um aluno consegue identificar a aplicabilidade em seu cotidi- ano do que lhe é ensinado, isso o motivará a absorver de forma mais agradável o que lhe será apresentado. Reforçamos então a importância de se iniciar os conteúdos, sempre que possível, pela sua aplicabilidade, para depois passar a abstração. Segundo Cool [6] o aluno é o responsável pelo seu processo ensino-aprendizagem, onde o sucesso desse processo está ligado à importância que o mesmo dá ao conteúdo que está sendo apresentado. O autor também afirma que professor e aluno possuem papéis distintos nesse processo, mas é papel do professor escolher as melhores técnicas para o sucesso do processo de ensino-aprendizagem. Segundo os Parâmetros Curriculares Nacionais do Ensino Médio (PCNEM)[2] o conhecimento matemático está inserido em diversas situações e interligado à outras áreas do conhecimento, onde faz com que sua aplicabilidade dê sentido ao que será aprendido. Especificamente no Ensino Médio, a Matemática deve ser entendida como fundamental na formação do educando, pois ela contribuirá no desenvolvimento de capacidades que serão exigidas na sua futura vida profissional. Aprender Matemática de uma forma contextualizada, integrada e re- lacionada a outros conhecimentos traz em si o desenvolvimento de com- petências e habilidades que são essencialmente formadoras, à medida que instrumentalizam e estruturam o pensamento do aluno, capacitando-o para compreender e interpretar situações, para se apropriar de linguagens es- pecíficas, argumentar, analisar e avaliar, tirar conclusões próprias, tomar 39 40 decisões, generalizar e para muitas outras ações necessárias à sua formação. ([2], p.111). Nos Parâmetros Curriculares Nacionais do Ensino Médio (PCNEM) [2], também encontramos que a resolução de problemas é fundamental, pois faz o aluno pensar e desenvolver estratégias para solucionar o desafio proposto. Na resolução de problemas, o tratamento de situações complexas e diver- sificadas oferece ao aluno a oportunidade de pensar por si mesmo, construir estratégias de resolução e argumentação, relacionar diferentes conhecimen- tos e enfim, perseverar na busca da solução. E, para isso, os desafios devem ser reais e fazer sentido ([2], p.113). Não defendemos a ausência de exercícios abstratos onde os alunos devam calcular, resolver ou demonstrar alguma expressão ou afirmação, pois é através deles que as técnicas e propriedades são desenvolvidas. As duas formas de ensino, sempre que possível, devem caminhar juntas. Especificamente no Ensino Médio é esperado do aluno que seus conhecimentos ma- temáticos o ajudem a analisar, de forma crítica, as informações que decodifica do meio onde vive. Assim as sugestões de situações problemas propostos ao aluno deve ir além de simples descrição e representação de dados, deve proporcionar ao aluno a capacidade de investigação e tomada de decisão. Uma das grandes competências propostas pelo PCNEM diz respeito à contextualização sociocultural como forma de aproximar o aluno da reali- dade e fazê-lo vivenciar situações próximas que lhe permitam reconhecer a diversidade que o cerca e reconhecer-se como indivíduo capaz de ler e atuar nessa realidade ([2], p.126). Baseado nesses pensamentos apresentaremos a utilização da Teoria dos Grafos na resolução de problemas, tendo como público alvo os alunos do Ensino Médio. Esse conteúdo será apresentado através de uma metodologia que acreditamos ser possível de trabalhar no processo ensino-aprendizagem. A Teoria dos Grafos não faz parte do currículo de matemática do Ensino Médio, mas pode ser relacionada a outros conteúdos do currículo disciplinar regular do Ensino Médio, como por exemplo o estudo das Matrizes, análise combinatória, problemas nas áreas de informática, engenharia e química. A sequência didática que iremos seguir será dividida em dois momentos que terão por objetivo a apresentação da teoria dos grafos a partir da resolução de problemas, para assim chegar na apresentação história da Teoria dos Grafos e suas aplicações nos dias atuais, relacionando essa teoria com o conteúdo Matrizes. As atividades escolhidas são do recurso educacional multimídia "Aviões e Matrizes", disponível no Portal M3 Matemática Multimídia1. As atividades que escolhemos foram aplicadas no período diurno do segundo ano do Ensino Médio de uma escola da rede particular da cidade de São Pedro - SP. A sala é composta por 18 alunos que se mostraram dispostos a vivenciar os conteúdos matemáticos através de recursos diferenciados. No momento da aplicação das ativi- dades os alunos já possuíam os conteúdos relacionados às Matrizes, o que facilitou a apresentação, apenas alguns conceitos tiveram que ser relembrados para alguns alunos da sala. 1http://m3.ime.unicamp.br/ Atividade 1: Caminho fechado e grafos 41 6.1 Atividade 1: Caminho fechado e grafos Esse experimento possui duas partes. A primeira parte está voltada para a intro- dução do conceito de grafos, onde seu ponto de partida é o problema inspirado nas Pontes de Könisgsberg. Nesta parte os alunos explorarão diversas situações que podem ser representadas por grafos, além de trabalharem com conceito de caminho fechado sob estes grafos. Na segunda parte os alunos são motivados a criar suas próprias atividades sobre grafos. Os objetivos desta atividade são: • introduzir o conceito de grafos; • identificar caminhos fechados; • aplicar o conceito de grafos no dia a dia. 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. Figura 6.1: Atividade Pontes de Könisgsberg Fonte: Guia do professor, p.2 Passamos, em seguida, a introduzir os conceitos de arestas, vértices e caminho fechado. Após a conceitualização, os alunos receberam duas novas imagens, que são referentes às plantas de um museu (Figura 6.2 e 6.4)que foram trabalhadas a partir dos seguintes problemas: Problema para a Figura 6.2: Essa é a planta de uma exposição de um museu. Você acha possível fazer um passeio pelas salas, passando por todas elas apenas uma vez por cada porta? Se sim, encontre uma solução. 2Disponível em: http://m3.ime.unicamp.br/recursos/1258 Atividade 1: Caminho fechado e grafos 42 Figura 6.2: Planta simples de um Museu Fonte: Guia do professor,p.4 A solução foi muito simples de ser encontrada, e todos as duplas a solucionaram imediatamente. Para exemplificar, a Figura 6.3 traz a resolução feita por um dos alunos. Figura 6.3: Resolução da planta simples de um Museu 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. Figura 6.4: Planta de um museu sem um caminho fechado Fonte: Guia do Professor, p.4 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 Figura 6.5: Planta de um Museu sem o caminho fechado 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. Figura 6.6: Ruas para entrega de jornais Fonte: Guia do Professor, p.5 Durante a realização da atividade os alunos foram questionados constantemente, justificando suas estratégias de resolução. A discussão de soluções entre os integrantes das duplas também foi estimulada. Houve ainda a discussão entre as duplas. A obser- vação das resoluções de cada dupla foi muito interessante e a forma com que cada um chegou à resposta final foi muito satisfatória. Na Figura 6.7, temos a resolução de uma dupla que utilizou lápis colorido para diferenciar as arestas. No final dos desafios propostos todos os grafos, que eram soluções do exercícios e outros que utilizamos como exemplos, foram colocados na lousa. Em cada um deles foi identificado se existia caminho fechado ou não e por fim, os alunos foram desafiados a descobrir porque em alguns grafos era possível e em outros não, sair e voltar ao mesmo Atividade 1: Caminho fechado e grafos 44 Figura 6.7: Ruas para entrega de jornais 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. Figura 6.8: Grafos propostos pelos alunos Acompanhar a elaboração e a construção da atividade pelos alunos foi muito interes- sante, pois pudemos notar a utilização das conclusões da primeira parte da atividade. Frases como "esse vértice é par"ou "esse vértice é ímpar"foram ouvidas com frequência Atividade 2: Aviões e Matrizes 45 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 Atividade 2: Aviões e Matrizes Para a segunda atividade utilizaremos o software Aviões e Matrizes3 que dá a relação entre as malhas aéreas e matrizes através de grafos e sua representação por matriz adjacência. Esta atividade está dividida em três partes, onde cada uma delas foi aplicada em uma hora. Os conceitos apresentados pelo software para os problemas que compõem esta atividade são: malhas aéreas e escalas, grafos e matrizes adjacência. Assim, o objetivo da atividade é: • estudo de matrizes usando a teoria dos grafos; • definir matriz adjacência e • fazer uma aplicação da matriz em malhas aéreas. 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. Segundo Problema: Transforme o grafo da Figura 6.9 na matriz adjacência. As instruções e a solução desta atividade estão representados na Figura 6.10. 3http://m3.ime.unicamp.br/recursos/1221 Atividade 2: Aviões e Matrizes 46 Figura 6.9: Resolução e enunciado do Primeiro Problema - Parte II Figura 6.10: Resolução do Segundo Problema - Parte II 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. Terceiro Problema: Dada a matriz, desenhe o seu grafo. As instruções e soluções desta atividade estão na Figura 6.12. A terceira atividade foi a que os alunos mais encontraram dificuldades. Durante a realização das atividades a intervenção do professor ficou focada em sanar dúvidas pequenas do conteúdo e incentivar os alunos para sempre fazerem o melhor a cada questão. Atividade 2: Aviões e Matrizes 47 Figura 6.11: Matrizes Fonte: Autora 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, seM1 é a matriz adjacência de um determinado grafo, seu quadrado, a matriz M2 1 , 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 Figura 6.12: Enunciado e resolução do Terceiro Problema - Parte II Figura 6.13: Enunciado e resolução do Primeiro Problema - Parte II 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 M2 1 , ou seja, M1 ×M1. Como os alunos já dominavam o conteúdo multiplicação de matrizes, não houve muitas dúvidas para sua realização, apenas foi uma questão trabalhosa, onde quase todos os grupos chegaram na resposta. Para a sequência das atividade o software apresenta uma explicação sobre o que é uma Matriz Adjacência e a relação existente entre a multiplicação de matrizes e as malhas aéreas. Notamos que a explicação não foi de fácil compreensão para os alunos, que necessitaram de outra explicação mais detalhada e exemplificada. Na sequência, resolveram a seguinte atividade Terceiro Problema (ver Figura 6.14): Analisando a matriz, responda: de quantas maneiras é possível ir da Cidade 4 para a Cidade 1 com exatamente três voos? A Atividade 2: Aviões e Matrizes 49 Figura 6.14: Resolução do Segundo Problema - Parte II resposta é 4 voos. Quarto Problema (ver 6.15): Qual é a matriz que representa as conexões com uma escala? Para a resolução, os alunos foram estimulados a realizar a multiplicação da matriz do item anterior por ela mesma, para que chegassem ao resultado, como mostra a Figura 6.15 Figura 6.15: Resolução do Quarto Problema - Parte II 6.2.3 Parte III Nesta parte os alunos aplicaram os conceitos construídos nas atividades das partes anteriores, além da compreensão de que a expressão “menor malha” é utilizada para se Atividade 2: Aviões e Matrizes 50 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. Figura 6.16: Resolução Primeiro Problema - Parte III 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. Figura 6.17: Malha do segundo problema - Parte III 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 Figura 6.18: Solução do segundo problema - Parte III 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). A solução dessa questão é a criação de dois hubs conectados e para o cálculo de quantas soluções diferentes entre si basta fazer a combinação C8,2, onde temos oito cidades, combinadas duas a duas, resultando num total de C8,2 = 8 2!6! = 28 possibilida- des. A resolução não acaba nesse cálculo, pois é preciso definir quantos aeroportos se conectam a cada um dos hubs (mínimo um, máximo cinco) e quais são esses aeroportos. Escolha dois hubs, por exemplo A e B. Os alunos encontraram dificuldades para resolver esta atividade. Assim, foram dadas orientações para a solução conduzindo o seguinte raciocínio: Primeiramente, vamos associar uma cidade ao hub A e as restantes ao B, o cálculo será a combinação C6,1 = 6. Agora associando duas cidades ao hub A e as restantes ao B. O cálculo será a combinação C6,2 = 15. Na sequência associamos três cidades ao hub A e as restantes ao B, o cálculo será a combinação C6,3 = 20. Quando associamos quatro cidades ao hub A, o cálculo será C6,4 = 15 e quando associamos cinco cidades ao hub A, o cálculo será C6,5 = 6. Temos assim um total de 62 possibilidades para cada uma das 28 possibilidades de pares de hubs calculadas anteriormente, nos dando um total de 28 · 62 = 1736 possibilidades de configurações com dois hubs. 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 Figura 6.19: Malha para o Quarto Problema - Parte III estar conectadas ao mesmo hub e as cidades 7, 8 e 9 a outro hub. Ao chegarem a esta conclusão várias soluções foram encontradas, uma destas está representada na Figura 6.20 Figura 6.20: Solução do Quarto Problema - Parte III Durante a realização das atividades conceitos que os alunos já dominavam como multipicação de matrizes e combinação tiveram que ser relembradas para alguns deles, algumas atividades que eles demonstraram dificuldade na realização foi devido a ativi- dade ser trabahosa em relação aos cálculos ou exigirem maior atenção por parte deles. Trabalhos com alunos imediatistas, onde tudos as informação explícitas são aceitas com maior facilidade que as informações implícitas. Além da intervenção do professor o auxílio entre os componentes das duplas e as duplas ajudou que essas barreiras fossem superadas. Muitos conceitos matemáticos estavam envolvidos nas atividades trabalhadas, como por exemplo, a definição de matrizes, multiplicação de Matrizes, Combinação entre outros. Podemos dizer que as atividades ocorrem de forma satisfatória, onde o envolvimento dos alunos na realização das mesmas foi gratificante e satisfatório. 7 Considerações Finais 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 M3 - 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 ser explorados para o ensino da Matemática, já que o processo de aprendizagem deve considerar inteligências múltiplas. A ampla literatura que estuda novos recursos educacionais aponta que o uso do laboratório de informática, vídeo, áudio, jogos e outros recursos educacionais estimula os alunos que estão acostumados com salas de aula, lousa e giz. Além disso, estimula a prática do professor de Matemática na busca da constante atualização para a aplicação de novos recursos educacionais em sala. Assim, a perspectiva deste trabalho está, além da exploração das outras atividades disponíveis na coleção M3 como sólidos de revolução, inequações, programação linear, gráficos de barras e setores e histogramas, a busca de outros recursos tecnológicos na prática docente, pois a experiência mostrou que a tecnologia pode ser um aliado no processo de ensino-aprendizagem que exige uma pluralidade de práticas para ser bem sucedido. Referências [1] AMARAL, R. B. Vídeo na Sala de Aula de Matemática: Que Possibilidades? Educação Matemática em Revista, n. 40, p. 38-47, nov 2013. [2] BRASIL. Secretaria da Educação Média e Tecnológica. Parâmetros Curriculares Nacionais: ciências da natureza e suas tecnologias. Brasília: MEC, 2002. [3] CARRAHER,T.N.et al. Na vida dez na escola zero - 6a. edição - São Paulo: Cor- tez, 1991. [4] CYRUNO, M.C.C.T. (2016b). Potencialidades da exploração de um caso multimí- dia como elemento da prática na formação inicial de professores de Matemática. Educação Matemática em Revista, 39(b), 80-89. [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. [6] COOL,C.Significados e sentido na aprendizagem escolar: Reflexões em torno do conceito de aprendizagem significativa. Cadernos de Formação: Psicologia da edu- cação. São Paulo: UNESP, 2006. [7] DE FARIAS, Andréia Araújo. Atividades de modelagem envolvendo a teoria dos grafos no ensino médio. Dissertação. Universidade Estadual de Maringá, 2014. [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. [10] JURKIEIWICZ, Samuel. Grafos: Uma Introdução. OBMEP, 2009. [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: . 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. [17] SAMPAIO, João Carlos V. Passeios de Euler e as pontes de Königsberg. Belo Horizonte - MG: I Bienal de SBM, 2002 [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.