O Problema das Quatro Cores

• Ano de defesa: 2002
• Autor(a) principal: Duenha, Liana Dessandre
• Orientador(a): Carvalho, Marcelo Henriques de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Teoria dos Grafos; Matemática da Computação; Ciência da Computação
• Link de acesso: https://repositorio.ufms.br/handle/123456789/469

É possível colorir qualquer mapa com não mais do que 4 cores, de forma que regiões vizinhas recebam cores diferentes?". Essa pergunta foi feita pela primeira vez em 1852 por Francis Guthrie, enquanto coloria um mapa da Inglaterra. Esse problema é conhecido como Problema das 4 Cores. Em 1878, foi publicada a primeira referência impressa da conjetura, no periódico Proceedings of the London Mathematical Society. Essa publicação disparou a febre do problema, com um grande núumero de variações equivalentes, conjeturas e falsas demonstrações. O Problema das 4 Cores é responsável por muito do que se conhece hoje em teoria dos grafos. A tentativa de resolvê-lo possibilitou o desenvolvimento de vários ramos da teoria dos grafos, através da sua equivalencia com outros problemas. Portanto, existem outros enfoques que podem ser dados em um estudo deste problema. No estudo que desenvolvemos, nosso principal objetivo foi estudar a última demonstração do Teorema das 4 Cores publicada em 1997. O teorema afirma que os vértices de um grafo planar sem laços podem ser coloridos com 4 cores distintas. Este teorema é equivalente ao problema das 4 cores. A demonstração do teorema é feita por contradição. Supõe-se a existência de um contra-exemplo para o teorema e estudando as propriedades deste contra-exemplo chega-se a uma contradição. Em várias partes da demonstração faz-se necessário o uso de programas de computador. O nosso trabalho resume-se no detalhamento da demonstração deste teorema. Para isto foi necessário o estudo detalhado de vários outros livros e artigos, alguns destes publicados no início do século passado e outros publicados depois de 1997 pelos mesmos autores, com o objetivo de esclarecer dúvidas e explicar com maior clareza os programas de computador indispensáveis para esta demonstração.