SOARES, F. V. S. Três teoremas interessantes em teoria dos grafos. 2017 57 f. Dissertação (Mestrado Profissional em Matemática em Rede Nacional) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2017. / Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-07-18T18:40:29Z No. of bitstreams: 1 2017_dis_fvssoares.pdf: 689594 bytes, checksum: c808d7f662ffa76dbeb23ee14f4bbcf1 (MD5) / Rejected by Rocilda Sales (rocilda@ufc.br), reason: Boa tarde, Revisei a Dissertação de FRANCISCO VANDIÉSIO SOUSA SOARES e encontrei alguns erros de formatação que devem ser corrigidos pelo autor. Tais erros estão listados a seguir: 1 – PALAVRAS-CHAVE ( a recomendação da ABNT é que apenas a primeira letras dos termos das palavras-chave estejam em letra maiúscula, salvo se forem nomes próprios,. Assim, o termo “Teorema das Cinco Cores”, e os subsequentes, devem apresentar a seguinte forma: “Teorema das cinco cores”) OBS.: essa regra também serve para os títulos de capítulos, seções e subseções; 2- SUMÁRIO (insira a formatação itálico nas seções terciarias “5.1.1”,”5.1.2”, “5.1.3” do sumário e no interior do trabalho) 3- REFERÊNCIAS (as referências devem seguir o padrão ABNT, o qual especifica que o último sobrenome do autor ou dos autores, caso haja mais de um, deve estar em caixa alta, iniciando a referência, há quatro referências na bibliografia do seu trabalho que que estão incorretas. Assim, referências como: Hefez, Abramo; Fernandez, Cecilia. Introdução à Álgebra Linear (COLEÇÃO PROFMAT). Rio de Janeiro: SBM, 2012 Dever ser alteradas para: HEFEZ, Abramo; FERNANDEZ, Cecilia. Introdução à Álgebra Linear (COLEÇÃO PROFMAT). Rio de Janeiro: SBM, 2012 Em caso de dúvidas, consulte as referências dos em autores em livros ou outras fontes confiáveis. Atenciosamente, on 2017-07-19T16:21:14Z (GMT) / Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-07-24T13:27:51Z No. of bitstreams: 1 2017_dis_fvssoares.pdf: 692235 bytes, checksum: 4b683f2b5e481f09fae4126e6f9b1838 (MD5) / Rejected by Rocilda Sales (rocilda@ufc.br), reason: Boa tarde, O autor esqueceu de colocar o item Referências na folha do Sumário. Rocilda on 2017-07-25T15:51:27Z (GMT) / Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-07-25T18:16:18Z No. of bitstreams: 1 2017_dis_fvssoares.pdf: 692486 bytes, checksum: e2919b69f55bc8ab3f42aaab72795274 (MD5) / Rejected by Rocilda Sales (rocilda@ufc.br), reason: Bom dia, O item Referências fica na mesma margem da Conclusão. on 2017-07-26T13:55:59Z (GMT) / Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-07-26T15:04:09Z No. of bitstreams: 1 2017_dis_fvssoares.pdf: 692491 bytes, checksum: 692aded24df0a0677bf540d9d90d0d84 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-07-28T14:58:07Z (GMT) No. of bitstreams: 1 2017_dis_fvssoares.pdf: 692491 bytes, checksum: 692aded24df0a0677bf540d9d90d0d84 (MD5) / Made available in DSpace on 2017-07-28T14:58:08Z (GMT). No. of bitstreams: 1 2017_dis_fvssoares.pdf: 692491 bytes, checksum: 692aded24df0a0677bf540d9d90d0d84 (MD5) Previous issue date: 2017-07 / The results presented in this work constitute themselves in particular topics of Graph Theory. One of the great advantages of the study of graphs lies in the fact that, besides being mathematically interesting objects, graphs appear in a multitude of practical ap- plications. Indeed, on the one hand, the statements of most of the famous problems in Graph Theory can be easily explained to an average high school student; on the other, the roots of those problems, most of the times, lie in important practical applications of the theory to such diverse areas as Physics, Chemistry, Biology, Electrical Engineering and Operations Research. In this work we restrict ourselves to the discussion of the spe- cific problems in Graph Theory: the Five Colors Theorem, which is a problem on vertex coloring of planar graphs, the Art Gallery Theorem, which is a result on Extremal Graph Theory, and the Friedship Theorm, which is an amazingly beautiful result in Algebraic Graph Theory. We present a structured and detailed discussion of such results, in the hope that their aesthetic appeal serve as an exhortation for the inclusion of the rudiments of Graph Theory in High School curriculum. / Os resultados apresentados neste trabalho são tópicos particulares de Teoria dos Grafos. Uma das grandes vantagens do estudo de grafos reside no fato de que, além de serem objetos matematicamente interessantes, grafos aparecem em uma miríade de aplicações práticas. De fato, por um lado, a maioria dos enunciados dos problemas famosos de Teoria dos Grafos pode ser facilmente explicada a um estudante da escola básica; por outro, as raízes de tais problemas, o mais das vezes, repousam em importantes aplicações práticas da teoria a áreas tão diversas quanto Física, Química, Biologia, Engenharia Elétrica e Pesquisa Operacional. Neste trabalho, vamos nos restringir à discussão de três problemas específicos de Teoria dos Grafos: o Teorema das Cinco Cores, que é um problema de coloração de vértices de um grafo planar, o Teorema da Galeria de Arte, que é um resultado de Teoria Extremal de Grafos e o Teorema da Amizade, que é um belíssimo resultado da Teoria Algébrica dos Grafos. Apresentamos tais resultados em detalhe e estruturadamente, na expectativa de que seus apelos estéticos sirvam de exortação à inclusão dos rudimentos de Teoria dos Grafos nos currículos do Ensino Médio.

Neste trabalho estudamos um pouco de Teoria dos Grafos, abordando diversas definições e teoremas interessantes. Apresentamos o Teorema das Quatro Cores, desde o surgimento do problema com Francis Guthrie. Analisamos a demonstração do teorema realizada por Alfred Bray Kempe e sua refutação através do contraexemplo de Percy John Heawood. Analisamos também a demonstração do Teorema das Cinco Cores de Percy John Heawood. Porém, apresentamos a primeira demonstração válida do Teorema das Quatro Cores, como sua particularidade de ter sido feita com o auxílio de um computador. O trabalho é concluído com uma análise sobre os benefícios que o conhecimento de Teoria dos Grafos pode render aos alunos do Ensino Básico, e como professor o pode trabalhar este assunto em sala de aula, inclusive abordando o problema de coloração de mapas. / In this paper we study Graph Theory, addressing various definitions and interesting theorems. We present the Four Color Theorem, since the origin of the problem with Francis Guthrie. We analyze the proof of the theorem presented by Alfred Bray Kempe, and its refutation by Percy John Heawood counter-example. We also analyze the Percy John Heawood demonstration of the Five Color Theorem. Finally, we present the first valid proof of the Four Colors Theorem, with its peculiarity of having been done with the aid of a computer. We conclude with an analysis of the beneficial that the knowledge of Graph Theory can render students of Basic Education, and how a teacher can work this topic in the classroom, including addressing the problem of map coloring.

Neste trabalho estudamos um pouco de Teoria dos Grafos, abordando diversas definições e teoremas interessantes. Apresentamos o Teorema das Quatro Cores, desde o surgimento do problema com Francis Guthrie. Analisamos a demonstração do teorema realizada por Alfred Bray Kempe e sua refutação através do contraexemplo de Percy John Heawood. Analisamos também a demonstração do Teorema das Cinco Cores de Percy John Heawood. Porém, apresentamos a primeira demonstração válida do Teorema das Quatro Cores, como sua particularidade de ter sido feita com o auxílio de um computador. O trabalho é concluído com uma análise sobre os benefícios que o conhecimento de Teoria dos Grafos pode render aos alunos do Ensino Básico, e como professor o pode trabalhar este assunto em sala de aula, inclusive abordando o problema de coloração de mapas. / In this paper we study Graph Theory, addressing various definitions and interesting theorems. We present the Four Color Theorem, since the origin of the problem with Francis Guthrie. We analyze the proof of the theorem presented by Alfred Bray Kempe, and its refutation by Percy John Heawood counter-example. We also analyze the Percy John Heawood demonstration of the Five Color Theorem. Finally, we present the first valid proof of the Four Colors Theorem, with its peculiarity of having been done with the aid of a computer. We conclude with an analysis of the beneficial that the knowledge of Graph Theory can render students of Basic Education, and how a teacher can work this topic in the classroom, including addressing the problem of map coloring.