Master's Dissertation
DOI
https://doi.org/10.11606/D.55.2016.tde-26112016-112047
Document
Author
Full name
Carlos Laercio Gomes de Lima
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2016
Supervisor
Committee
Andretta, Marina (President)
Cobre, Juliana
Silva, Sônia Cristina Poltroniere
Simal, Janete Crema
Title in Portuguese
Um estudo sobre teoria dos grafos e o teorema das quatro cores
Keywords in Portuguese
Teorema das cinco cores
Teorema das quatro cores
Teoria dos grafos.
Abstract in Portuguese
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.
Title in English
A study on graph theory and the four color theorem
Keywords in English
Five colors theorem
Four colors theorem
Graph theory.
Abstract in English
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.
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2016-11-28