Aplicações da teoria dos grafos
Gráficos planares
Diz-se que um gráfico G é plano se puder ser representado em um plano de tal maneira que os vértices sejam todos pontos distintos, as arestas sejam curvas simples e nenhuma duas arestas se encontrem, exceto em seus terminais. Por exemplo, K 4, o gráfico completo em quatro vértices, é plana, como mostra a Figura 4A.
Diz-se que dois gráficos são homeomórficos se ambos puderem ser obtidos do mesmo gráfico por subdivisões de arestas. Por exemplo, os gráficos na Figura 4A e na Figura 4B são homeomórficos.
O gráfico K m, n é um gráfico para o qual o conjunto de vértices pode ser dividido em dois subconjuntos, um com m vértices e o outro com n vértices. Quaisquer dois vértices do mesmo subconjunto não são adjacentes, enquanto quaisquer dois vértices de subconjuntos diferentes são adjacentes. O matemático polonês Kazimierz Kuratowski em 1930 provou o seguinte famoso teorema:
Uma condição necessária e suficiente para um gráfico G para ser plana é que ele não contenha um homeomorfos subgráfico, quer K 5 ou K 3,3 mostrado na Figura 5.
Uma contração elementar de um gráfico G é uma transformação de G em um novo gráfico G 1, de modo que dois vértices adjacentes u e u de G são substituídos por um novo vértice w em G 1 ew é adjacente em G 1 a todos os vértices a qual u ou u é adjacente em G. Diz-se que um gráfico G * é uma contração de G se G * pode ser obtido de G por uma sequência de contrações elementares. A seguir, é apresentada outra caracterização de um gráfico planar devido ao matemático alemão K. Wagner em 1937.
Um gráfico é plano se, e somente se, não for contratável para K 5 ou K 3,3.
O problema do mapa de quatro cores
Por mais de um século, a solução do problema do mapa de quatro cores iludiu todos os analistas que o tentaram. O problema pode ter atraído a atenção de Möbius, mas a primeira referência escrita a ele parece ser uma carta de um Francis Guthrie a seu irmão, um estudante de Augustus De Morgan, em 1852.
O problema diz respeito a mapas planares - isto é, subdivisões do plano em regiões não sobrepostas limitadas por curvas fechadas simples. Em mapas geográficos, foi observado empiricamente, em tantos casos especiais quanto tentados, que, no máximo, são necessárias quatro cores para colorir as regiões, de modo que duas regiões que compartilham um limite comum sejam sempre coloridas de maneira diferente e certos casos em que são necessárias pelo menos quatro cores. (As regiões que se reúnem apenas em um ponto, como os estados do Colorado e Arizona nos Estados Unidos, não são consideradas como tendo um limite comum). A formalização dessa observação empírica constitui o chamado "teorema das quatro cores". O problema é provar ou refutar a afirmação de que esse é o caso de todo mapa planar. Que três cores não serão suficientes é facilmente demonstrado, enquanto a suficiência de cinco cores foi comprovada em 1890 pelo matemático britânico PJ Heawood.
Em 1879, AB Kempe, um inglês, propôs uma solução para o problema das quatro cores. Embora Heawood tenha mostrado que o argumento de Kempe era defeituoso, dois de seus conceitos se mostraram proveitosos em investigações posteriores. Uma delas, chamada inevitabilidade, afirma corretamente a impossibilidade de construir um mapa no qual cada uma das quatro configurações está ausente (essas configurações consistem em uma região com dois vizinhos, uma com três, uma com quatro e uma com cinco). O segundo conceito, o de redutibilidade, leva o nome da prova válida de Kempe de que, se houver um mapa que exija pelo menos cinco cores e que contenha uma região com quatro (ou três ou dois) vizinhos, deverá haver um mapa que exija cinco cores para um número menor de regiões. A tentativa de Kempe de provar a redutibilidade de um mapa contendo uma região com cinco vizinhos foi errônea, mas foi retificada em uma prova publicada em 1976 por Kenneth Appel e Wolfgang Haken, dos Estados Unidos. A prova deles atraiu críticas porque exigiu a avaliação de 1.936 casos distintos, cada um envolvendo até 500.000 operações lógicas. Appel, Haken e seus colaboradores criaram programas que permitiam a um grande computador digital lidar com esses detalhes. O computador precisou de mais de 1.000 horas para executar a tarefa, e a prova formal resultante tem várias centenas de páginas.
Ciclos eulerianos e o problema da ponte de Königsberg
Um multigrafo G consiste em um conjunto não vazio V (G) de vértices e um subconjunto E (G) do conjunto de pares não ordenados de elementos distintos de V (G) com uma frequência f ≥ 1 anexada a cada par. Se o par (x 1, x 2) com a frequência f pertence a E (G), os vértices x 1 e x 2 são unidos pelas arestas f.
Um ciclo euleriano de um multigráfico G é uma cadeia fechada na qual cada aresta aparece exatamente uma vez. Euler mostrou que um multigráfico possui um ciclo euleriano se, e somente se, estiver conectado (além de pontos isolados) e o número de vértices de grau ímpar é zero ou dois.
Esse problema surgiu primeiro da seguinte maneira. O rio Pregel, formado pela confluência de seus dois galhos, atravessa a cidade de Königsberg e deságua em ambos os lados da ilha de Kneiphof. Havia sete pontes, como mostrado na Figura 6A. Os habitantes da cidade se perguntavam se era possível dar um passeio e atravessar cada ponte uma vez e só uma vez. Isso é equivalente a encontrar um ciclo euleriano para o multigráfico na Figura 6B. Euler mostrou que isso é impossível porque existem quatro vértices de ordem ímpar.
