Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/469
Tipo: Dissertação
Título: O Problema das Quatro Cores
Autor(es): Duenha, Liana Dessandre
Abstract: É 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.
Palavras-chave: Teoria dos Grafos
Matemática da Computação
Ciência da Computação
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/469
Data do documento: 2002
Aparece nas coleções:Programa de Pós-graduação em Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Liana Dessandre Duenha.pdf824,8 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.