[pt] O advento do uso maciço de computadores em provas matemáticas, ocorrido ao final da década de setenta com a solução de um famoso problema matemático – a prova do Teorema das Quatro Cores – ocasionou disputas filosóficas que ainda hoje demandam esclarecimentos. O objetivo principal da tese consiste em elaborar alguns dos referidos esclarecimentos desde uma perspectiva motivada pela filosofia da matemática de Ludwig Wittgenstein, especialmente no que diz respeito à distinção continuamente manuseada e depurada pelo filósofo ao longo do desenvolvimento de seu pensamento entre provas e experimentos. Após apresentar as principais ideias da prova do Teorema das Quatro Cores em termos históricos, algumas distinções conceituais metodologicamente significativas são elaboradas. A seguir o trabalho analisa, a partir da concepção funcional de a priori de Arthur Pap, o argumento da introdução da experimentação nas matemáticas de Thomas Tymoczko. A leitura das controvérias filosóficas que se seguiram ao argumento de Tymoczko é então apresentada, aplicando-se as distinções conceituais anteriormente elaboradas. Por fim algumas ideias wittgensteinianas sobre da disitinção entre provas e experimentos são exploradas em conexão com a noção de sinopticidade de provas, considerando menos os papéis específicos de tais noções na filosofia da matemática de Wittgenstein, do que investigando as vantagens de suas possíveis aplicações no esclarecimento de tópicos críticos das referidas disputas. / [en] The massive use of computers in mathematical proofs, which started in the end of the seventies trough the solution of one famous mathematical problem – the Four-Color Theorem – entailed philosophical disputes still in need of elucidation. The central aim of this thesis consists in elaborating some of these elucidations from a point of view motivated by Ludwig Wittgenstein’s philosophy of mathematics, mainly in what concerns the distinction between proofs and experiments, which was continuously used and elaborated by the philosopher in the course of the development of his thought. After the presentation of the main ideas involved in the proof of the Four-Color Theorem from a historical perspective, some methodological conceptual distinctions are elaborated. The thesis then shifts to an analysis of the introduction of experiment in mathematics argument, by Thomas Tymoczko, from the point of view of Arthur Pap’s conception of functional a priori. An interpretation of the controversies that followed that argument is developed trough the application of the conceptual distinctions previously elaborated. At last, some wittgensteinian ideas about the distinction between proofs and experiments are explored in connection with the notion of surveyability of proofs, concerned less with its specific roles in Wittgenstein’s philosophy of mathematics than with investigating the advantages of its possible applications in the elucidation of some critical points in the referred controversies.

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.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work brings an approach to the basic notions of Graph Theory, presenting historical context, concepts, de nitions and examples in order to provide the reader with previous knowledge of the theory. The main objective is to perform a study of the graphs applied to the staining using the dual graph and the method of the greedy algorithm. To do so, we will present the demonstration attempt of the 4-Color Theorem that had been developed by Kempe and the proof of the 5-Color Theorem, made 11 years later by Heawood. Finally, we will seek the resolution of some situations problems that will be modeled through the coloring of vertices. / Este trabalho traz uma abordagem às noções da Teoria dos Grafos, apresentando contexto histórico, conceitos, definições e exemplos com o intuito de proporcionar ao leitor conhecimentos prévios da teoria. O principal objetivo é efetuar um estudo dos grafos aplicados à coloração mediante o uso do grafo dual e o métdo do algoritmo guloso. Para tanto, executaremos um esboço acerca da tentativa de demonstração do Teorema das 4 Cores que fora desenvolvida por Kempe e da prova do Teorema das 5 Cores, feita 11 anos mais tarde por Heawood. Por fim, buscaremos a resolução de algumas situações problemas que serão modeladas através da coloração de vértices. / São Cristóvão, SE

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.

Orientador: Christiane Neme Campos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:02:03Z (GMT). No. of bitstreams: 1 Galvao_KaioKaram_M.pdf: 1971760 bytes, checksum: e2f60ab09595b03fa6da5051cd78e3f3 (MD5) Previous issue date: 2013 / Resumo: Em 1971, Fulkerson propôs a seguinte conjetura: todo grafo cúbico sem arestas de corte admite seis emparelhamentos perfeitos tais que cada aresta do grafo pertence a exatamente dois destes emparelhamentos. A Conjetura de Fulkerson tem desafiado pesquisadores desde sua publicação. Esta conjetura é facilmente verificada para grafos cúbicos 3-aresta-coloráveis. Portanto, a dificuldade do problema reside em estabelecer a conjetura para grafos cúbicos sem arestas de corte que não possuem 3-coloração de arestas. Estes grafos são chamados snarks. Nesta dissertação, a Conjetura de Fulkerson e os snarks são introduzidos com ¿ênfase em sua história e resultados mais relevantes. Alguns resultados relacionados à Conjetura de Fulkerson são apresentados, enfatizando suas conexões com outras conjeturas. Um breve histórico do Problema das Quatro Cores e suas relações com snarks também são apresentados. Na segunda parte deste trabalho, a Conjetura de Fulkerson é verificada para algumas famílias infinitas de snarks construídas com o método de Loupekine, utilizando subgrafos do Grafo de Petersen. Primeiramente, mostramos que a família dos LP0-snarks satisfaz a Conjetura de Fulkerson. Em seguida, generalizamos este resultado para a família mais abrangente dos LP1-snarks. Além disto, estendemos estes resultados para Snarks de Loupekine construídos com subgrafos de snarks diferentes do Grafo de Petersen / Abstract: In 1971, Fulkerson proposed a conjecture that states that every bridgeless cubic graph has six perfect matchings such that each edge of the graph belongs to precisely two of these matchings. Fulkerson's Conjecture has been challenging researchers since its publication. It is easily verified for 3-edge-colourable cubic graphs. Therefore, the difficult task is to settle the conjecture for non-3-edge-colourable bridgeless cubic graphs, called snarks. In this dissertation, Fulkerson's Conjecture and snarks are presented with emphasis in their history and remarkable results. We selected some results related to Fulkerson's Conjecture, emphasizing their reach and connections with other conjectures. It is also presented a brief history of the Four-Colour Problem and its connections with snarks. In the second part of this work, we verify Fulkerson's Conjecture for some infinite families of snarks constructed with Loupekine's method using subgraphs of the Petersen Graph. More specifically, we first show that the family of LP0-snarks satisfies Fulkerson's Conjecture. Then, we generalise this result by proving that Fulkerson's Conjecture holds for the broader family of LP1-snarks. We also extend these results to even more general Loupekine Snarks constructed with subgraphs of snarks other than the Petersen Graph / Mestrado / Ciência da Computação / Mestre em Ciência da Computação