O teorema de quatro cores
História
O teorema de quatro cores
Geometria e Topologia
E.T.In.Ciência
A conjectura de cor quatro, em primeiro lugar, parece ter sido feita por Francis Guthrie. Ele era um estudante na University College London, onde estudou sob De Morgan. Após se graduar em Londres, estudou direito, mas por este tempo seu irmão Frederick Guthrie tornou-se um estudante de Morgan. Francis Guthrie mostrou seu irmão alguns resultados que ele tinha tentado provar sobre a coloração de mapas e Frederico pediu para perguntar De Morgan sobre eles.
De Morgan foi incapaz de dar uma resposta, mas, em 23 de outubro de 1852, no mesmo dia que ele foi perguntado, ele escreveu para Hamilton em Dublin. De Morgan escreveu:
O aluno meu me perguntou hoje dar-lhe uma razão para um fato que eu não sabia que era um fato - e não ainda. Ele diz que, se uma figura de qualquer modo ser dividido e os compartimentos de cor diferente para que figuras com qualquer parte da linha de fronteira comum são coloridas diferentemente - quatro cores podem ser queridas, mas não mais - este é o caso em que quatro cores são procuradas. Consulta não uma necessidade por cinco ou mais ser inventado. ...... Se você retrucar com algum caso muito simples que faz de mim um animal estúpido, eu acho que devo fazer como fez o Sphynx...
Hamilton respondeu em 26 de outubro de 1852 (mostrando a eficiência de si mesmo e os correios):
Eu não vou tentar seu Quatérnion de cor muito em breve.
Antes de continuar com a história da conjectura quatro cores para concluir detalhes de Francis Guthrie. Depois de praticar como um advogado, ele foi para África do Sul em 1861 como um Professor de matemática. Ele publicou alguns trabalhos matemáticos e interessou-se em botânica. Uma heather (Erica Guthriei) é nomeada após ele.
De Morgan ficava perguntando se alguém poderia encontrar uma solução para o problema de Guthrie e vários matemáticos trabalhados nela. Charles Sanders Peirce nos EUA tentou provar a conjectura na década de 1860 e era manter interessou o problema. Cayley também aprendeu do problema de Morgan e em 13 de junho de 1878, ele colocou uma questão para a London Mathematical Society perguntando se a conjectura de cor quatro tinha sido resolvida. Pouco tempo depois, Cayley enviou um documento sobre a coloração de mapas à Royal Geographical Society e foi publicado em 1879. O jornal explica onde as dificuldades residem na tentativa de provar a conjectura.
Em 17 de julho de 1879 Alfred Bray Kempe anunciou na natureza que ele tinha uma prova da conjectura quatro cores. Kempe , era um advogado de Londres, que estudou matemática sob Cayley em Cambridge e algum do seu tempo dedicado à matemática durante toda sua vida. Sugestão de Cayley Kempe apresentou o teorema para o American Journal of Mathematics , onde foi publicado em 1879. História Leia o livro antes da publicação e fez algumas simplificações. História relatada a prova para o científico associação da Universidade Johns Hopkins em novembro de 1879 e Charles Peirce, quem estava na reunião de novembro, falou da reunião de dezembro da associação do seu próprio trabalho a conjectura de cor quatro.
Kempe usou um argumento, conhecido como o método de cadeias de Kempe. Se tivermos um mapa em que cada região é de cor vermelha, verde, azul ou amarelo, exceto um, digamos X. Esta região final X não está rodeada por regiões de todas as quatro cores se a cor deixada para X. Portanto, suponho que regiões de todas as quatro cores cercam X. Se X está rodeado por regiões A, B, C, D em ordem, de cor vermelho, amarelo, verde e azul, em seguida, há dois casos a considerar.
não há nenhuma cadeia de regiões adjacentes de A para C alternadamente cor vermelha e verde.
é uma cadeia de regiões adjacentes de A para C alternadamente cor vermelha e verde.
Se detém, não há nenhum problema. Alterar A de verde e então troca a cor das regiões na cadeia de juntar-se Avermelho/verde. Desde que C não é na cadeia, permanece verde e não há agora nenhuma vermelha região adjacente a X. Cor X vermelho.
Se detém Então não pode haver nenhuma cadeia de regiões adjacentes amarelo/azul de B para D. [Ele não poderia cruzar a cadeia das regiões de vermelho/verde.] Portanto, Propriedade detém para B e D e nós mudar cores, como acima.
Kempe recebeu grande aclamação por sua prova. Ele foi eleito Fellow da Royal Society e serviu como seu tesoureiro por muitos anos. Ele foi nomeado cavaleiro em 1912. Ele publicou duas versões melhoradas de sua prova, o segundo em 1880 despertou o interesse de P G Teixeira, o Professor de Filosofia Natural em Edimburgo. Tait dirigida a Sociedade real de Edimburgo sobre o assunto e publicou dois artigos sobre a (o que agora chamamos) teorema de quatro cores. Eles contêm algumas ideias inteligentes e uma série de erros básicos.
O teorema de cor quatro voltou a ser a conjectura de cor quatro em 1890. Percy John Heawood, palestrante em Durham, Inglaterra, publicou um livro chamado teorema de coloração mapa. Nela, ele afirma que seu objetivo é bastante destrutivo do que construtivo, pois será mostrado que há um defeito na prova agora aparentemente reconhecido.
Apesar de Heawood mostrou que prova do Kempefoi errada ele provar que cada mapa pode ser cor-de-5 neste artigo. Kempe relatou o erro para a London Mathematical Society , ele mesmo e disse que ele não poderia corrigir o erro em sua prova. Em 1896 de la Vallée Poussin também apontou o erro no papel do Kempe, aparentemente inconscientes de Heawooddo trabalho.
Heawood era trabalhar durante toda sua vida no mapa de coloração, trabalho que se estendeu por quase 60 anos. Com êxito, ele investigou o número de cores necessárias para mapas em outras superfícies e deu o que é conhecido como o Heawood estimar o número necessário em termos da característica de Euler da superfície.
De Heawoodoutra reivindicação à fama é arrecadando dinheiro para restaurar o Durham Castle como secretário do fundo de restauração do Castelo de Durham. Por sua perseverança em levantar o dinheiro para salvar o Castelo de deslizar para baixo da colina sobre a qual fica Heawood recebeu a O.B.E
Heawood foi tornar mais contribuições para a conjectura de cor quatro. Em 1898, ele provou que se o número de arestas em torno de cada região é divisível por 3 Então as regiões são 4-colorável. Aí ele escreveu muitos artigos generalizar este resultado.
Para entender a obra posterior, que precisamos definir alguns conceitos.
Claramente um gráfico pode ser construído a partir de qualquer mapa regiões sendo representadas por dois vértices, juntou-se uma vantagem se as regiões correspondentes para os vértices são adjacentes e os vértices. O gráfico resultante é planar, ou seja pode ser desenhado no plano sem bordas cruzando. A conjectura de cor quatro agora pergunta se os vértices do grafo podem ser coloridos com 4 cores, para que nenhum dois vértices adjacentes são da mesma cor.
Do gráfico de uma triangulação pode ser obtida adicionando bordas para dividir qualquer rosto não triangular em triângulos. Uma configuração é parte de uma triangulação contida dentro de um circuito. Um conjunto de inevitável é um conjunto de configurações com a propriedade que qualquer triangulação deve conter uma das configurações no conjunto. Uma configuração é redutível se não pode ser contida em uma triangulação do gráfico menor que não pode ser cor-de-4.
A busca por evitáveis de moda começou em 1904 com o trabalho de Weinicke. Interesse renovado nos EUA deveu Veblen quem publicou um artigo em 1912 sobre a conjectura de cor quatro generalização Heawooddo trabalho. Mais trabalho por G D Birkhoff introduziu o conceito de redutibilidade (definido acima) em que trabalho posterior mais descansado.
Franklin em 1922 publicou ainda mais exemplos de conjuntos inevitáveis e usou Birkhoffideia de redutibilidade para provar, entre outros resultados, que qualquer mapa com 25 regiões ≤ pode ser cor-de-4. O número de regiões que resultou em um mapa 4-colorável lentamente foi aumentado. Reynolds é aumentado para 27 em 1926, Winn para 35 em 1940, minério e Stemple 39 em 1970 e Mayer para 95 em 1976.
No entanto as ideias finais necessárias para a solução da conjectura cor quatro tinham sido introduzidas antes destes dois últimos resultados. Heesch em 1969 introduziu o método de descarga. Isto consiste em atribuir a um vértice de grau a carga de 6 - eu. Agora da fórmula de Eulerpodemos deduzir que o montante dos encargos sobre todos os vértices deve ser 12. Um determinado conjunto de S de configurações pode ser provado inevitável se para uma triangulação T que não contém uma configuração em S Podemos redistribuir as acusações (sem alterar a carga total) para que nenhum vértice termina com um carga positiva.
Heesch pensei que a conjectura de cor quatro poderiam ser resolvida por considerar um conjunto de cerca de 8900 configurações. Houve dificuldades com sua abordagem, uma vez que algumas das suas configurações tinham um limite de até 18 arestas e não podem ser testadas para redutibilidade. Os testes para redutibilidade usado argumentos de cadeia de Kempe , mas algumas configurações tinham obstáculos para evitar redução.
No ano de 1976 viu uma solução completa para a conjectura de cor quatro quando era tornar-se o teorema de cor quatro para a segunda e última, vez. A prova foi alcançada por Appel e Haken, baseando seus métodos redutibilidade usando cadeias de Kempe . Eles carregavam através de ideias de Heesch e eventualmente construíram um conjunto inevitável com cerca de 1500 configurações. Eles conseguiram manter o tamanho do anel de contorno até ≤ 14 fazendo cálculos mais fácil que para o caso de Heesch. Houve um longo período onde eles essencialmente usados tentativa e erro, juntamente com a intuição inacreditável para modificar seu conjunto inevitável e seu procedimento de descarregamento. Appel e Haken usado 1200 horas de tempo de computador para resolver os detalhes da prova final. Koch assistida Appel e Haken com os cálculos do computador.
O teorema de cor quatro foi o primeiro teorema principal que devem ser provados usando um computador, tendo uma prova de que não pôde ser verificada diretamente por outros matemáticos. Apesar de algumas preocupações sobre isso inicialmente, verificação independente logo convenceu toda a gente que o teorema de cor quatro finalmente tinha provado. Detalhes da prova aparecem em dois artigos, em 1977. Trabalho recente conduziu a melhorias no algoritmo.
O aluno meu me perguntou hoje dar-lhe uma razão para um fato que eu não sabia que era um fato - e não ainda. Ele diz que, se uma figura de qualquer modo ser dividido e os compartimentos de cor diferente para que figuras com qualquer parte da linha de fronteira comum são coloridas diferentemente - quatro cores podem ser queridas, mas não mais - este é o caso em que quatro cores são procuradas. Consulta não uma necessidade por cinco ou mais ser inventado. ...... Se você retrucar com algum caso muito simples que faz de mim um animal estúpido, eu acho que devo fazer como fez o Sphynx...
Hamilton respondeu em 26 de outubro de 1852 (mostrando a eficiência de si mesmo e os correios):
Eu não vou tentar seu Quatérnion de cor muito em breve.
Antes de continuar com a história da conjectura quatro cores para concluir detalhes de Francis Guthrie. Depois de praticar como um advogado, ele foi para África do Sul em 1861 como um Professor de matemática. Ele publicou alguns trabalhos matemáticos e interessou-se em botânica. Uma heather (Erica Guthriei) é nomeada após ele.
De Morgan ficava perguntando se alguém poderia encontrar uma solução para o problema de Guthrie e vários matemáticos trabalhados nela. Charles Sanders Peirce nos EUA tentou provar a conjectura na década de 1860 e era manter interessou o problema. Cayley também aprendeu do problema de Morgan e em 13 de junho de 1878, ele colocou uma questão para a London Mathematical Society perguntando se a conjectura de cor quatro tinha sido resolvida. Pouco tempo depois, Cayley enviou um documento sobre a coloração de mapas à Royal Geographical Society e foi publicado em 1879. O jornal explica onde as dificuldades residem na tentativa de provar a conjectura.
Em 17 de julho de 1879 Alfred Bray Kempe anunciou na natureza que ele tinha uma prova da conjectura quatro cores. Kempe , era um advogado de Londres, que estudou matemática sob Cayley em Cambridge e algum do seu tempo dedicado à matemática durante toda sua vida. Sugestão de Cayley Kempe apresentou o teorema para o American Journal of Mathematics , onde foi publicado em 1879. História Leia o livro antes da publicação e fez algumas simplificações. História relatada a prova para o científico associação da Universidade Johns Hopkins em novembro de 1879 e Charles Peirce, quem estava na reunião de novembro, falou da reunião de dezembro da associação do seu próprio trabalho a conjectura de cor quatro.
Kempe usou um argumento, conhecido como o método de cadeias de Kempe. Se tivermos um mapa em que cada região é de cor vermelha, verde, azul ou amarelo, exceto um, digamos X. Esta região final X não está rodeada por regiões de todas as quatro cores se a cor deixada para X. Portanto, suponho que regiões de todas as quatro cores cercam X. Se X está rodeado por regiões A, B, C, D em ordem, de cor vermelho, amarelo, verde e azul, em seguida, há dois casos a considerar.
não há nenhuma cadeia de regiões adjacentes de A para C alternadamente cor vermelha e verde.
é uma cadeia de regiões adjacentes de A para C alternadamente cor vermelha e verde.
Se detém, não há nenhum problema. Alterar A de verde e então troca a cor das regiões na cadeia de juntar-se Avermelho/verde. Desde que C não é na cadeia, permanece verde e não há agora nenhuma vermelha região adjacente a X. Cor X vermelho.
Se detém Então não pode haver nenhuma cadeia de regiões adjacentes amarelo/azul de B para D. [Ele não poderia cruzar a cadeia das regiões de vermelho/verde.] Portanto, Propriedade detém para B e D e nós mudar cores, como acima.
Kempe recebeu grande aclamação por sua prova. Ele foi eleito Fellow da Royal Society e serviu como seu tesoureiro por muitos anos. Ele foi nomeado cavaleiro em 1912. Ele publicou duas versões melhoradas de sua prova, o segundo em 1880 despertou o interesse de P G Teixeira, o Professor de Filosofia Natural em Edimburgo. Tait dirigida a Sociedade real de Edimburgo sobre o assunto e publicou dois artigos sobre a (o que agora chamamos) teorema de quatro cores. Eles contêm algumas ideias inteligentes e uma série de erros básicos.
O teorema de cor quatro voltou a ser a conjectura de cor quatro em 1890. Percy John Heawood, palestrante em Durham, Inglaterra, publicou um livro chamado teorema de coloração mapa. Nela, ele afirma que seu objetivo é bastante destrutivo do que construtivo, pois será mostrado que há um defeito na prova agora aparentemente reconhecido.
Apesar de Heawood mostrou que prova do Kempefoi errada ele provar que cada mapa pode ser cor-de-5 neste artigo. Kempe relatou o erro para a London Mathematical Society , ele mesmo e disse que ele não poderia corrigir o erro em sua prova. Em 1896 de la Vallée Poussin também apontou o erro no papel do Kempe, aparentemente inconscientes de Heawooddo trabalho.
Heawood era trabalhar durante toda sua vida no mapa de coloração, trabalho que se estendeu por quase 60 anos. Com êxito, ele investigou o número de cores necessárias para mapas em outras superfícies e deu o que é conhecido como o Heawood estimar o número necessário em termos da característica de Euler da superfície.
De Heawoodoutra reivindicação à fama é arrecadando dinheiro para restaurar o Durham Castle como secretário do fundo de restauração do Castelo de Durham. Por sua perseverança em levantar o dinheiro para salvar o Castelo de deslizar para baixo da colina sobre a qual fica Heawood recebeu a O.B.E
Heawood foi tornar mais contribuições para a conjectura de cor quatro. Em 1898, ele provou que se o número de arestas em torno de cada região é divisível por 3 Então as regiões são 4-colorável. Aí ele escreveu muitos artigos generalizar este resultado.
Para entender a obra posterior, que precisamos definir alguns conceitos.
Claramente um gráfico pode ser construído a partir de qualquer mapa regiões sendo representadas por dois vértices, juntou-se uma vantagem se as regiões correspondentes para os vértices são adjacentes e os vértices. O gráfico resultante é planar, ou seja pode ser desenhado no plano sem bordas cruzando. A conjectura de cor quatro agora pergunta se os vértices do grafo podem ser coloridos com 4 cores, para que nenhum dois vértices adjacentes são da mesma cor.
Do gráfico de uma triangulação pode ser obtida adicionando bordas para dividir qualquer rosto não triangular em triângulos. Uma configuração é parte de uma triangulação contida dentro de um circuito. Um conjunto de inevitável é um conjunto de configurações com a propriedade que qualquer triangulação deve conter uma das configurações no conjunto. Uma configuração é redutível se não pode ser contida em uma triangulação do gráfico menor que não pode ser cor-de-4.
A busca por evitáveis de moda começou em 1904 com o trabalho de Weinicke. Interesse renovado nos EUA deveu Veblen quem publicou um artigo em 1912 sobre a conjectura de cor quatro generalização Heawooddo trabalho. Mais trabalho por G D Birkhoff introduziu o conceito de redutibilidade (definido acima) em que trabalho posterior mais descansado.
Franklin em 1922 publicou ainda mais exemplos de conjuntos inevitáveis e usou Birkhoffideia de redutibilidade para provar, entre outros resultados, que qualquer mapa com 25 regiões ≤ pode ser cor-de-4. O número de regiões que resultou em um mapa 4-colorável lentamente foi aumentado. Reynolds é aumentado para 27 em 1926, Winn para 35 em 1940, minério e Stemple 39 em 1970 e Mayer para 95 em 1976.
No entanto as ideias finais necessárias para a solução da conjectura cor quatro tinham sido introduzidas antes destes dois últimos resultados. Heesch em 1969 introduziu o método de descarga. Isto consiste em atribuir a um vértice de grau a carga de 6 - eu. Agora da fórmula de Eulerpodemos deduzir que o montante dos encargos sobre todos os vértices deve ser 12. Um determinado conjunto de S de configurações pode ser provado inevitável se para uma triangulação T que não contém uma configuração em S Podemos redistribuir as acusações (sem alterar a carga total) para que nenhum vértice termina com um carga positiva.
Heesch pensei que a conjectura de cor quatro poderiam ser resolvida por considerar um conjunto de cerca de 8900 configurações. Houve dificuldades com sua abordagem, uma vez que algumas das suas configurações tinham um limite de até 18 arestas e não podem ser testadas para redutibilidade. Os testes para redutibilidade usado argumentos de cadeia de Kempe , mas algumas configurações tinham obstáculos para evitar redução.
No ano de 1976 viu uma solução completa para a conjectura de cor quatro quando era tornar-se o teorema de cor quatro para a segunda e última, vez. A prova foi alcançada por Appel e Haken, baseando seus métodos redutibilidade usando cadeias de Kempe . Eles carregavam através de ideias de Heesch e eventualmente construíram um conjunto inevitável com cerca de 1500 configurações. Eles conseguiram manter o tamanho do anel de contorno até ≤ 14 fazendo cálculos mais fácil que para o caso de Heesch. Houve um longo período onde eles essencialmente usados tentativa e erro, juntamente com a intuição inacreditável para modificar seu conjunto inevitável e seu procedimento de descarregamento. Appel e Haken usado 1200 horas de tempo de computador para resolver os detalhes da prova final. Koch assistida Appel e Haken com os cálculos do computador.
O teorema de cor quatro foi o primeiro teorema principal que devem ser provados usando um computador, tendo uma prova de que não pôde ser verificada diretamente por outros matemáticos. Apesar de algumas preocupações sobre isso inicialmente, verificação independente logo convenceu toda a gente que o teorema de cor quatro finalmente tinha provado. Detalhes da prova aparecem em dois artigos, em 1977. Trabalho recente conduziu a melhorias no algoritmo.
O ensino da matemática na Roma antiga
CMisteriosBlog
CMisteriosBlog
