Teorema das quatro cores -Four color theorem

Exemplo de um mapa de quatro cores
Um mapa de quatro cores dos estados dos Estados Unidos (ignorando lagos e oceanos)

Em matemática , o teorema das quatro cores , ou o teorema do mapa de quatro cores , afirma que não são necessárias mais de quatro cores para colorir as regiões de qualquer mapa, de modo que não haja duas regiões adjacentes com a mesma cor. Adjacente significa que duas regiões compartilham um segmento de curva limite comum, não apenas um canto onde três ou mais regiões se encontram. Foi o primeiro grande teorema a ser provado usando um computador . Inicialmente, esta prova não foi aceita por todos os matemáticos porque a prova assistida por computador era inviável para um ser humano verificar manualmente . A prova ganhou ampla aceitação desde então, embora algumas dúvidas permaneçam.

O teorema das quatro cores foi provado em 1976 por Kenneth Appel e Wolfgang Haken após muitas provas falsas e contra-exemplos (ao contrário do teorema das cinco cores , provado em 1800, que afirma que cinco cores são suficientes para colorir um mapa). Para dissipar quaisquer dúvidas remanescentes sobre a prova de Appel-Haken, uma prova mais simples usando as mesmas ideias e ainda contando com computadores foi publicada em 1997 por Robertson, Sanders, Seymour e Thomas. Em 2005, o teorema também foi provado por Georges Gonthier com um software de prova de teoremas de uso geral .

Formulação precisa do teorema

Em termos teóricos de grafos, o teorema afirma que para grafo planar loopless , seu número cromático é .

A afirmação intuitiva do teorema das quatro cores - "dada qualquer separação de um plano em regiões contíguas, as regiões podem ser coloridas usando no máximo quatro cores, de modo que não haja duas regiões adjacentes com a mesma cor" - precisa ser interpretada apropriadamente para estar correta .

Primeiro, as regiões são adjacentes se compartilham um segmento de fronteira; duas regiões que compartilham apenas pontos de fronteira isolados não são consideradas adjacentes. (Caso contrário, um mapa em forma de gráfico de pizza criaria um número arbitrariamente grande de regiões 'adjacentes' umas às outras em um canto comum e, como resultado, exigiria um número arbitrariamente grande de cores.) Em segundo lugar, regiões bizarras, como aqueles com área finita, mas perímetro infinitamente longo, não são permitidos; mapas com essas regiões podem exigir mais de quatro cores. (Para garantir, podemos restringir a regiões cujos limites consistem em um número finito de segmentos de linha reta. É permitido que uma região tenha enclaves , ou seja, ela envolve inteiramente uma ou mais outras regiões.) Observe que a noção de "região contígua" (tecnicamente: subconjunto aberto conectado do plano) não é o mesmo que um "país" em mapas regulares, uma vez que os países não precisam ser contíguos (eles podem ter exclaves , por exemplo, a Província de Cabinda como parte de Angola , Nakhchivan como parte do Azerbaijão , Kaliningrado como parte da Rússia, França com seus territórios ultramarinos e Alasca como parte dos Estados Unidos não são contíguos). Se exigimos que todo o território de um país receba a mesma cor, então quatro cores nem sempre são suficientes. Por exemplo, considere um mapa simplificado:

4CT Inadequacy Example.svg

Neste mapa, as duas regiões identificadas como A pertencem ao mesmo país. Se quiséssemos que essas regiões recebessem a mesma cor, seriam necessárias cinco cores, pois as duas regiões A juntas são adjacentes a outras quatro regiões, cada uma adjacente a todas as outras. Forçar duas regiões separadas a terem a mesma cor pode ser modelado adicionando uma 'alça' unindo-as fora do plano.

4CT Inadequacy Explication.svg

Tal construção torna o problema equivalente a colorir um mapa em um toro (superfície do gênero 1), que requer até 7 cores para um mapa arbitrário. Uma construção semelhante também se aplica se uma única cor for usada para várias áreas disjuntas, como para corpos d'água em mapas reais, ou se houver mais países com territórios disjuntos. Em tais casos, mais cores podem ser necessárias com um gênero crescente de uma superfície resultante. (Consulte a seção Generalizações abaixo.)

Um mapa com quatro regiões e o grafo planar correspondente com quatro vértices.

Uma declaração mais simples do teorema usa a teoria dos grafos . O conjunto de regiões de um mapa pode ser representado de forma mais abstrata como um grafo não direcionado que possui um vértice para cada região e uma aresta para cada par de regiões que compartilham um segmento de fronteira. Este grafo é planar : pode ser desenhado no plano sem cruzamentos, colocando cada vértice em um local escolhido arbitrariamente dentro da região a que corresponde, e desenhando as arestas como curvas sem cruzamentos que partem do vértice de uma região, através de uma área compartilhada. segmento de fronteira, para o vértice de uma região adjacente. Por outro lado, qualquer gráfico planar pode ser formado a partir de um mapa dessa maneira. Na terminologia da teoria dos grafos, o teorema das quatro cores afirma que os vértices de cada grafo planar podem ser coloridos com no máximo quatro cores, de modo que dois vértices adjacentes não recebam a mesma cor, ou para abreviar:

Todo grafo planar é quadricolorável .

História

Tentativas iniciais de prova

Carta de De Morgan para Hamilton , 23 de outubro de 1852

Pelo que se sabe, a conjectura foi proposta pela primeira vez em 23 de outubro de 1852, quando Francis Guthrie , ao tentar colorir o mapa dos condados da Inglaterra, notou que eram necessárias apenas quatro cores diferentes. Na época, o irmão de Guthrie, Frederick , era aluno de Augustus De Morgan (ex-conselheiro de Francis) na University College London . Francis perguntou a Frederick sobre isso, que então o levou para De Morgan (Francis Guthrie se formou mais tarde em 1852 e mais tarde tornou-se professor de matemática na África do Sul). Segundo De Morgan:

"Um aluno meu [Guthrie] pediu-me hoje para lhe dar uma razão para um fato que eu não sabia que era um fato - e ainda não sei. Ele diz que se uma figura for qualquer, quão dividida e os compartimentos coloridos de maneira que figuras com qualquer porção de linha de limite comum são coloridas de forma diferente - quatro cores podem ser desejadas, mas não mais - o seguinte é o caso dele em que quatro cores são desejadas. A consulta não pode ser inventada como uma necessidade de cinco ou mais..." ( Wilson 2014 , pág. 18)

"FG", talvez um dos dois Guthries, publicou a questão no The Athenaeum em 1854, e De Morgan colocou a questão novamente na mesma revista em 1860. Outra referência publicada anteriormente por Arthur Cayley  ( 1879 ), por sua vez, credita a conjectura a De Morgan.

Houve várias tentativas iniciais fracassadas de provar o teorema. De Morgan acreditava que isso decorria de um simples fato sobre quatro regiões, embora não acreditasse que esse fato pudesse ser derivado de fatos mais elementares.

Isso ocorre da seguinte maneira. Nunca precisamos de quatro cores em um bairro, a menos que haja quatro condados, cada um dos quais com linhas de fronteira em comum com cada um dos outros três. Tal coisa não pode acontecer com quatro áreas, a menos que uma ou mais delas esteja incluída nas demais; e a cor usada para o condado fechado é assim liberada para continuar. Agora, este princípio, de que quatro áreas não podem ter limites comuns com todas as outras três sem inclusão, não é, acreditamos plenamente, capaz de demonstração em algo mais evidente e mais elementar; deve permanecer como um postulado.

Uma prova proposta foi dada por Alfred Kempe em 1879, que foi amplamente aclamada; outro foi dado por Peter Guthrie Tait em 1880. Não foi até 1890 que a prova de Kempe foi mostrada incorreta por Percy Heawood , e em 1891, a prova de Tait foi mostrada incorreta por Julius Petersen - cada prova falsa permaneceu incontestada por 11 anos.

Em 1890, além de expor a falha na prova de Kempe, Heawood provou o teorema das cinco cores e generalizou a conjectura das quatro cores para superfícies de gênero arbitrário.

Tait, em 1880, mostrou que o teorema das quatro cores é equivalente à afirmação de que um certo tipo de grafo (chamado de snark na terminologia moderna) deve ser não planar .

Em 1943, Hugo Hadwiger formulou a conjectura de Hadwiger , uma generalização abrangente do problema das quatro cores que ainda permanece sem solução.

Prova por computador

Durante as décadas de 1960 e 1970, o matemático alemão Heinrich Heesch desenvolveu métodos de usar computadores para procurar uma prova. Notavelmente, ele foi o primeiro a usar a descarga para provar o teorema, o que acabou sendo importante na parte de inevitabilidade da subsequente prova de Appel-Haken. Ele também expandiu o conceito de redutibilidade e, junto com Ken Durre, desenvolveu um teste de computador para isso. Infelizmente, nessa conjuntura crítica, ele não conseguiu obter o tempo necessário do supercomputador para continuar seu trabalho.

Outros adotaram seus métodos, incluindo sua abordagem assistida por computador. Enquanto outras equipes de matemáticos corriam para completar as provas, Kenneth Appel e Wolfgang Haken, da Universidade de Illinois, anunciaram, em 21 de junho de 1976, que haviam provado o teorema. Eles foram auxiliados em algum trabalho algorítmico por John A. Koch .

Se a conjectura das quatro cores fosse falsa, haveria pelo menos um mapa com o menor número possível de regiões que requer cinco cores. A prova mostrou que tal contra-exemplo mínimo não pode existir, através do uso de dois conceitos técnicos:

  1. Um conjunto inevitável é um conjunto de configurações tal que todo mapa que satisfaça algumas condições necessárias para ser uma triangulação mínima não 4-colorível (como ter grau mínimo 5) deve ter pelo menos uma configuração desse conjunto.
  2. Uma configuração redutível é um arranjo de países que não pode ocorrer em um contra-exemplo mínimo. Se um mapa contém uma configuração redutível, o mapa pode ser reduzido a um mapa menor. Este mapa menor tem a condição de que se puder ser colorido com quatro cores, isso também vale para o mapa original. Isso implica que, se o mapa original não pode ser colorido com quatro cores, o mapa menor também não pode e, portanto, o mapa original não é mínimo.

Usando regras e procedimentos matemáticos baseados em propriedades de configurações redutíveis, Appel e Haken encontraram um conjunto inevitável de configurações redutíveis, provando assim que um contra-exemplo mínimo para a conjectura de quatro cores não poderia existir. A prova deles reduzia a infinidade de mapas possíveis a 1.834 configurações redutíveis (posteriormente reduzidas a 1.482) que precisavam ser verificadas uma a uma por computador e levavam mais de mil horas. Esta parte da redutibilidade do trabalho foi verificada de forma independente com diferentes programas e computadores. No entanto, a parte inevitável da prova foi verificada em mais de 400 páginas de microfichas , que tiveram de ser verificadas manualmente com a ajuda da filha de Haken, Dorothea Blostein ( Appel & Haken 1989 ).

O anúncio de Appel e Haken foi amplamente divulgado pela mídia de notícias em todo o mundo, e o departamento de matemática da Universidade de Illinois usou um carimbo dizendo "Quatro cores são suficientes". Ao mesmo tempo, a natureza incomum da prova - foi o primeiro grande teorema a ser provado com ampla assistência de computador - e a complexidade da parte verificável por humanos gerou considerável controvérsia ( Wilson 2014 ).

No início dos anos 1980, espalharam-se rumores de uma falha na prova de Appel-Haken. Ulrich Schmidt, da RWTH Aachen, examinou a prova de Appel e Haken para sua tese de mestrado publicada em 1981 ( Wilson 2014 , 225). Ele havia verificado cerca de 40% da parcela de inevitabilidade e encontrado um erro significativo no procedimento de descarga ( Appel & Haken 1989 ). Em 1986, Appel e Haken foram solicitados pelo editor do Mathematical Intelligencer a escrever um artigo abordando os rumores de falhas em sua prova. Eles responderam que os rumores se deviam a uma "má interpretação dos resultados [de Schmidt]" e agradeceram com um artigo detalhado ( Wilson 2014 , 225–226). Sua magnum opus , Every Planar Map is Four-Colorable , um livro que reivindica uma prova completa e detalhada (com um suplemento de microficha de mais de 400 páginas), apareceu em 1989; explicou e corrigiu o erro descoberto por Schmidt, bem como vários outros erros encontrados por outros ( Appel & Haken 1989 ).

Simplificação e verificação

Desde a prova do teorema, uma nova abordagem levou a uma prova mais curta e a um algoritmo mais eficiente para mapas de 4 cores. Em 1996, Neil Robertson , Daniel P. Sanders , Paul Seymour e Robin Thomas criaram um algoritmo de tempo quadrático (exigindo apenas tempo O ( n 2 ), onde n é o número de vértices), aprimorando um algoritmo de tempo quártico baseado na prova de Appel e Haken. A nova prova, baseada nas mesmas ideias, é semelhante à de Appel e Haken, mas mais eficiente porque reduz a complexidade do problema e requer a verificação de apenas 633 configurações redutíveis. As partes de inevitabilidade e redutibilidade desta nova prova devem ser executadas por um computador e são impraticáveis ​​para verificação manual. Em 2001, os mesmos autores anunciaram uma prova alternativa, provando a conjectura de snark . Esta prova permanece inédita, no entanto.

Em 2005, Benjamin Werner e Georges Gonthier formalizaram uma prova do teorema dentro do assistente de prova Coq . Isso eliminou a necessidade de confiar nos vários programas de computador usados ​​para verificar casos específicos; é necessário apenas confiar no kernel Coq.

Resumo das ideias de prova

A discussão a seguir é um resumo baseado na introdução de Every Planar Map is Four Colorable ( Appel & Haken 1989 ). Embora falho, a suposta prova original de Kempe do teorema das quatro cores forneceu algumas das ferramentas básicas usadas posteriormente para prová-lo. A explicação aqui é reformulada em termos da formulação da teoria dos grafos moderna acima.

O argumento de Kempe é o seguinte. Primeiro, se as regiões planares separadas pelo grafo não forem trianguladas , ou seja, não tiverem exatamente três arestas em seus limites, podemos adicionar arestas sem introduzir novos vértices para tornar cada região triangular, incluindo a região externa ilimitada. Se esse grafo triangulado for colorível usando quatro cores ou menos, o grafo original também será, pois a mesma coloração é válida se as arestas forem removidas. Portanto, basta provar o teorema das quatro cores para grafos triangulados para prová-lo para todos os grafos planares e, sem perda de generalidade, assumimos que o grafo é triangulado.

Suponha que v , e , e f sejam o número de vértices, arestas e regiões (faces). Como cada região é triangular e cada aresta é compartilhada por duas regiões, temos que 2 e = 3 f . Isso junto com a fórmula de Euler , ve + f = 2, pode ser usado para mostrar que 6 v − 2 e = 12. Agora, o grau de um vértice é o número de arestas adjacentes a ele. Se v n é o número de vértices de grau n e D é o grau máximo de qualquer vértice,

Mas como 12 > 0 e 6 − i ≤ 0 para todo i ≥ 6, isso demonstra que existe pelo menos um vértice de grau 5 ou menos.

Se houver um grafo que exija 5 cores, haverá um grafo mínimo , em que a remoção de qualquer vértice o torna quatro cores. Chame esse gráfico de G. Então G não pode ter um vértice de grau 3 ou menor, porque se d ( v ) ≤ 3, podemos remover v de G , quatro cores no grafo menor, depois adicionar de volta v e estender a quatro cores para ele escolhendo um cor diferente de seus vizinhos.

Um grafo contendo uma cadeia de Kempe consistindo em vértices azuis e vermelhos alternados

Kempe também mostrou corretamente que G não pode ter nenhum vértice de grau 4. Como antes, removemos o vértice v e colorimos em quatro cores os vértices restantes. Se todos os quatro vizinhos de v são de cores diferentes, digamos vermelho, verde, azul e amarelo no sentido horário, procuramos um caminho alternado de vértices coloridos de vermelho e azul unindo os vizinhos vermelho e azul. Esse caminho é chamado de cadeia de Kempe . Pode haver uma cadeia Kempe unindo os vizinhos vermelho e azul, e pode haver uma cadeia Kempe unindo os vizinhos verde e amarelo, mas não ambos, pois esses dois caminhos necessariamente se cruzariam, e o vértice onde eles se cruzam não pode ser colorido. Suponha que sejam os vizinhos vermelho e azul que não estão encadeados. Explore todos os vértices ligados ao vizinho vermelho por caminhos alternados vermelho-azul e, em seguida, inverta as cores vermelho e azul em todos esses vértices. O resultado ainda é uma quatro cores válida, e v agora pode ser adicionado de volta e colorido de vermelho.

Isso deixa apenas o caso onde G tem um vértice de grau 5; mas o argumento de Kempe foi falho para este caso. Heawood percebeu o erro de Kempe e também observou que, se alguém estivesse satisfeito em provar que apenas cinco cores são necessárias, poderia executar o argumento acima (mudando apenas que o contra-exemplo mínimo requer 6 cores) e usar cadeias de Kempe na situação de grau 5 para provar o teorema das cinco cores .

De qualquer forma, lidar com esse caso de vértice de grau 5 requer uma noção mais complicada do que remover um vértice. Em vez disso, a forma do argumento é generalizada para considerar configurações , que são subgrafos conectados de G com o grau de cada vértice (em G) especificado. Por exemplo, o caso descrito na situação de vértice de grau 4 é a configuração que consiste em um único vértice rotulado como tendo grau 4 em G . Como acima, basta demonstrar que, se a configuração for removida e o gráfico restante for quadricolor, a coloração pode ser modificada de forma que, quando a configuração for adicionada novamente, a quadricoloração possa ser estendida a ela como bem. Uma configuração para a qual isso é possível é chamada de configuração redutível . Se pelo menos uma de um conjunto de configurações deve ocorrer em algum lugar em G, esse conjunto é chamado de inevitável . O argumento acima começou dando um conjunto inevitável de cinco configurações (um único vértice com grau 1, um único vértice com grau 2, ..., um único vértice com grau 5) e então passou a mostrar que os primeiros 4 são redutíveis; exibir um conjunto inevitável de configurações onde cada configuração no conjunto é redutível provaria o teorema.

Como G é triangular, o grau de cada vértice em uma configuração é conhecido e todas as arestas internas à configuração são conhecidas, o número de vértices em G adjacentes a uma determinada configuração é fixo e eles são unidos em um ciclo. Esses vértices formam o anel da configuração; uma configuração com k vértices em seu anel é uma configuração de k -anel, e a configuração junto com seu anel é chamada de configuração em anel . Como nos casos simples acima, pode-se enumerar todas as quatro cores distintas do anel; qualquer coloração que pode ser estendida sem modificação para uma coloração da configuração é chamada inicialmente boa . Por exemplo, a configuração de vértice único acima com 3 ou menos vizinhos foi inicialmente boa. Em geral, o grafo circundante deve ser recolorido sistematicamente para tornar a coloração do anel boa, como foi feito no caso acima onde havia 4 vizinhos; para uma configuração geral com um anel maior, isso requer técnicas mais complexas. Devido ao grande número de quatro cores distintas do anel, esta é a etapa principal que requer assistência do computador.

Por fim, resta identificar um conjunto inevitável de configurações passíveis de redução por esse procedimento. O método primário usado para descobrir tal conjunto é o método de descarga . A ideia intuitiva subjacente à descarga é considerar o grafo planar como uma rede elétrica. Inicialmente, a "carga elétrica" ​​positiva e negativa é distribuída entre os vértices de modo que o total seja positivo.

Lembre-se da fórmula acima:

A cada vértice é atribuída uma carga inicial de 6 graus( v ). Em seguida, "flui" a carga redistribuindo sistematicamente a carga de um vértice para seus vértices vizinhos de acordo com um conjunto de regras, o procedimento de descarga . Como a carga é preservada, alguns vértices ainda têm carga positiva. As regras restringem as possibilidades de configurações de vértices carregados positivamente, portanto, enumerar todas essas configurações possíveis fornece um conjunto inevitável.

Enquanto algum membro do conjunto inevitável não for redutível, o procedimento de descarga é modificado para eliminá-lo (enquanto introduz outras configurações). O procedimento de descarga final de Appel e Haken era extremamente complexo e, juntamente com uma descrição do conjunto de configurações inevitável resultante, preenchia um volume de 400 páginas, mas as configurações geradas podiam ser verificadas mecanicamente para serem redutíveis. A verificação do volume que descreve o conjunto de configurações inevitável em si foi feita por revisão por pares durante um período de vários anos.

Um detalhe técnico não discutido aqui, mas necessário para concluir a prova, é a redutibilidade por imersão .

Falsas refutações

O teorema das quatro cores tem sido notório por atrair um grande número de falsas provas e refutações em sua longa história. A princípio, o The New York Times se recusou, por uma questão de política, a relatar a prova de Appel-Haken, temendo que a prova se mostrasse falsa como as anteriores ( Wilson 2014 ). Algumas supostas provas, como as de Kempe e Tait mencionadas acima, ficaram sob escrutínio público por mais de uma década antes de serem refutadas. Mas muitos outros, de autoria de amadores, nunca foram publicados.

No primeiro mapa, que excede quatro cores, substituir as regiões vermelhas por qualquer uma das outras quatro cores não funcionaria, e o exemplo pode inicialmente parecer violar o teorema. No entanto, as cores podem ser reorganizadas, como visto no segundo mapa.

Geralmente, os contra-exemplos mais simples, embora inválidos, tentam criar uma região que toca todas as outras regiões. Isso força as regiões restantes a serem coloridas com apenas três cores. Como o teorema das quatro cores é verdadeiro, isso sempre é possível; no entanto, como a pessoa que desenha o mapa está focada em uma grande região, ela não consegue perceber que as regiões restantes podem, de fato, ser coloridas com três cores.

Esse truque pode ser generalizado: existem muitos mapas onde se as cores de algumas regiões forem selecionadas de antemão, torna-se impossível colorir as regiões restantes sem ultrapassar quatro cores. Um verificador casual do contra-exemplo pode não pensar em mudar as cores dessas regiões, de modo que o contra-exemplo pareça válido.

Talvez um efeito subjacente a esse equívoco comum seja o fato de que a restrição de cores não é transitiva : uma região só precisa ser colorida de maneira diferente das regiões que ela toca diretamente, não das regiões que tocam as regiões que ela toca. Se essa fosse a restrição, os grafos planares exigiriam um número arbitrariamente grande de cores.

Outras falsas refutações violam as suposições do teorema, como usar uma região que consiste em várias partes desconectadas ou impedir que regiões da mesma cor se toquem em um ponto.

tricolor

Prova sem palavras que um mapa dos estados dos EUA precisa de pelo menos quatro cores, mesmo ignorando o quadriponto

Embora todo mapa planar possa ser colorido com quatro cores, é NP-completo em complexidade decidir se um mapa planar arbitrário pode ser colorido com apenas três cores.

Um mapa cúbico pode ser colorido com apenas três cores se e somente se cada região interior tiver um número par de regiões vizinhas. No exemplo do mapa dos estados dos EUA, o Missouri ( MO ) sem litoral tem oito vizinhos (um número par): deve ter cores diferentes de todos eles, mas os vizinhos podem alternar as cores, portanto, essa parte do mapa precisa de apenas três cores. No entanto, Nevada ( NV ) sem litoral tem cinco vizinhos (um número ímpar): um dos vizinhos deve ter uma cor diferente dele e de todos os outros, portanto, quatro cores são necessárias aqui.

Generalizações

Gráficos infinitos

Unindo as setas simples e as duplas, obtém-se um toro com sete regiões que se tocam mutuamente; portanto, sete cores são necessárias.
Esta construção mostra o toro dividido em no máximo sete regiões, cada uma das quais se tocando.

O teorema das quatro cores se aplica não apenas a grafos planares finitos, mas também a grafos infinitos que podem ser desenhados sem cruzamentos no plano, e ainda mais geralmente a grafos infinitos (possivelmente com um número incontável de vértices) para os quais todo subgrafo finito é planar . Para provar isso, pode-se combinar uma prova do teorema para grafos planares finitos com o teorema de De Bruijn–Erdős afirmando que, se todo subgrafo finito de um grafo infinito é k -colorível, então todo o grafo também é k -colorável Nash- Williams (1967) . Isso também pode ser visto como uma consequência imediata do teorema de compacidade de Kurt Gödel para a lógica de primeira ordem , simplesmente expressando a colorabilidade de um grafo infinito com um conjunto de fórmulas lógicas.

Superfícies mais altas

Pode-se também considerar o problema de coloração em superfícies diferentes do plano. O problema na esfera ou no cilindro é equivalente ao do plano. Para superfícies fechadas (orientáveis ​​ou não orientáveis) com gênero positivo , o número máximo p de cores necessárias depende da característica de Euler da superfície χ de acordo com a fórmula

onde os colchetes mais externos denotam a função do piso .

Alternativamente, para uma superfície orientável , a fórmula pode ser dada em termos do gênero da superfície, g :

Esta fórmula, a conjectura de Heawood , foi proposta por PJ Heawood em 1890 e, após contribuições de várias pessoas, provada por Gerhard Ringel e JWT Youngs em 1968. A única exceção à fórmula é a garrafa de Klein , que tem característica de Euler 0 (daí a fórmula dá p = 7), mas requer apenas 6 cores, conforme demonstrado por Philip Franklin em 1934.

Por exemplo, o toro tem característica de Euler χ = 0 (e gênero g = 1) e, portanto, p = 7, portanto, não são necessárias mais de 7 cores para colorir qualquer mapa em um toro. Este limite superior de 7 é nítido: certos poliedros toroidais , como o poliedro Szilassi, requerem sete cores.

Uma faixa de Möbius requer seis cores ( Tietze 1910 ) assim como grafos 1-planares (grafos desenhados com no máximo um cruzamento simples por aresta) ( Borodin 1984 ). Se ambos os vértices e as faces de um grafo planar são coloridos, de tal forma que não há dois vértices adjacentes, faces ou par vértice-face com a mesma cor, então novamente no máximo seis cores são necessárias ( Borodin 1984 ) .

Para grafos cujos vértices são representados como pares de pontos em duas superfícies distintas, com arestas desenhadas como curvas não cruzadas em uma das duas superfícies, o número cromático pode ser no mínimo 9 e no máximo 12, mas limites mais precisos não são conhecido; este é o problema Terra-Lua de Gerhard Ringel .

regiões sólidas

Não há extensão óbvia do resultado da coloração para regiões sólidas tridimensionais. Usando um conjunto de n hastes flexíveis, pode-se fazer com que cada haste toque uma na outra. O conjunto exigiria então n cores, ou n +1 incluindo o espaço vazio que também toca cada haste. O número n pode ser considerado qualquer número inteiro, tão grande quanto desejado. Tais exemplos eram conhecidos por Fredrick Guthrie em 1880 ( Wilson 2014 ). Mesmo para cubóides paralelos ao eixo (considerados adjacentes quando dois cubóides compartilham uma área de fronteira bidimensional), um número ilimitado de cores pode ser necessário ( Reed & Allwright 2008 ; Magnant & Martin (2011) ).

Relação com outras áreas da matemática

Dror Bar-Natan deu uma declaração sobre álgebras de Lie e invariantes de Vassiliev que é equivalente ao teorema das quatro cores.

Use fora da matemática

Apesar da motivação de colorir mapas políticos de países , o teorema não é de particular interesse para os cartógrafos . De acordo com um artigo do historiador da matemática Kenneth May , "Mapas que utilizam apenas quatro cores são raros e aqueles que geralmente requerem apenas três. Livros sobre cartografia e história da cartografia não mencionam a propriedade de quatro cores" (Wilson 2014 , 2). Deve-se notar, porém, que a maioria dos mapas requer quatro cores, pois sempre que uma região é cercada por um número ímpar de regiões, são necessárias quatro cores. O teorema também não garante a exigência cartográfica usual de que regiões não contíguas de um mesmo país (como o enclave do Alasca e o resto dos Estados Unidos ) sejam coloridas de forma idêntica.

Veja também

Notas

  1. ^ De Gonthier (2008) : "Definições: Um mapa planar é um conjunto de subconjuntos disjuntos emparelhados do plano, chamados regiões. Um mapa simples é aquele cujas regiões estão conectadas em conjuntos abertos. Duas regiões de um mapa são adjacentes se seus respectivos fechamentos têm um ponto comum que não é um canto do mapa. Um ponto é um canto de um mapa se e somente se ele pertencer aos fechamentos de pelo menos três regiões. Teorema: As regiões de qualquer mapa planar simples podem ser coloridas apenas com quatro cores, de modo que quaisquer duas regiões adjacentes tenham cores diferentes”.
  2. ^ Swart (1980) .
  3. ^ Wilson (2014) , 216–222.
  4. ^ Hudson (2003) .
  5. ^ Thomas (1998 , p. 849); Wilson (2014) ).
  6. Há algum folclore matemático de que Möbius originou a conjectura das quatro cores, mas esta noção parece ser errônea. Ver Biggs, Norman ; Lloyd, E. Keith; Wilson, Robin J. (1986), Graph Theory, 1736–1936 , Oxford University Press, p. 116 , ISBN 0-19-853916-9& Maddison, Isabel (1897), "Nota sobre a história do problema de coloração de mapas", Bull. Amer. Matemática. Sociedade , 3 (7): 257, doi : 10.1090/S0002-9904-1897-00421-9
  7. ^ Donald MacKenzie, Mechanizing Proof: Computing, Risk, and Trust (MIT Press, 2004) p103
  8. ^ FG (1854) ; Mc Kay (2012)
  9. ^ a b De Morgan (anônimo), Augustus (14 de abril de 1860), "The Philosophy of Discovery, Chapters Historical and Critical. By W. Whewell.", The Athenaeum : 501–503
  10. ^ WW Rouse Ball (1960) O Teorema das Quatro Cores , em Mathematical Recreations and Essays, Macmillan, Nova York, pp 222–232.
  11. ^ Thomas (1998) , p. 848.
  12. ^ Heawood (1890) .
  13. ^ Tait (1880) .
  14. ^ Hadwiger (1943) .
  15. ^ a b Wilson (2014) .
  16. ^ Gary Chartrand e Linda Lesniak, Graphs & Digraphs (CRC Press, 2005) p.221
  17. ^ Wilson (2014) ; Appel & Haken (1989) ; Thomas (1998 , pp. 852–853)
  18. ^ Thomas (1995) ; Robertson e outros. (1996) ).
  19. ^ Thomas (1998) , pp. 852–853.
  20. ^ Thomas (1999) ; Pegg et ai. (2002) ).
  21. ^ Gontier (2008) .
  22. Dailey, DP (1980), "Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete", Discrete Mathematics , 30 (3): 289–293, doi : 10.1016/0012-365X(80)90236- 8
  23. Steinberg, Richard (1993), "O estado do problema das três cores", em Gimbel, John; Kennedy, John W.; Quintas, Louis V. (eds.), Quo Vadis, Graph Theory? , Annals of Discrete Mathematics, vol. 55, Amsterdam: North-Holland, pp. 211–248, doi : 10.1016/S0167-5060(08)70391-1 , MR  1217995
  24. ^ Ringel (1974) .
  25. ^ Gethner, Ellen (2018), "Para a lua e além", em Gera, Ralucca ; Haynes, Teresa W .; Hedetniemi, Stephen T. (eds.), Graph Theory: Favorite Conjectures and Open Problems, II , Problem Books in Mathematics, Springer International Publishing, pp. 115–133, doi : 10.1007/978-3-319-97686-0_11 , MR  3930641
  26. ^ Bar-Natan (1997) .

Referências

links externos