Euler's Eyes
2026-10-19
Grafos e mapas: o desenho em que só importa quem liga a quem
A cidade de Königsberg, na Prússia, era cortada pelo rio Pregel, que formava duas ilhas, e sete pontes ligavam as quatro partes da cidade. Os moradores se perguntavam se era possível dar um passeio atravessando cada ponte uma única vez. Em 1736, Euler provou que não. O livro de História conta a prova no capítulo sobre as pontes de Königsberg. Aqui interessa o que Euler fez com o desenho.
Jogar fora o mapa
Um mapa da cidade mostra ruas, casas, distâncias, a largura do rio, o formato das ilhas. Euler percebeu que nada disso importava para a pergunta. Importava só quais partes da cidade estão ligadas por quais pontes. Cada parte vira um ponto; cada ponte, um traço entre dois pontos. O resultado é o que hoje se chama grafo: quatro pontos e sete traços.
Nesse desenho, o tamanho, a distância e a forma deixam de significar alguma coisa. Pode-se esticar um traço, mudar um ponto de lugar, entortar tudo: o grafo continua o mesmo, desde que as ligações não mudem. Na linguagem de Peirce, o grafo é um ícone de um tipo muito especial: se parece com a cidade apenas nas ligações. É um ícone que escolheu, com rigor, o que copiar.
E foi esse desenho empobrecido que tornou a resposta visível. Num passeio, toda vez que se entra num ponto por uma ponte, sai-se por outra; por isso cada ponto do meio do caminho precisa ter um número par de traços. Em Königsberg, os quatro pontos tinham $5$, $3$, $3$ e $3$ traços: todos ímpares. O passeio era impossível.
O mapa que deixou de ser mapa
Em 1931, um desenhista técnico do metrô de Londres, Harry Beck, propôs um mapa novo. Os mapas antigos seguiam a geografia: as linhas se embolavam no centro e se espalhavam nos subúrbios, e ninguém conseguia ler. Beck percebeu que o passageiro não precisa saber onde fica a estação, mas em que ordem as estações vêm e onde se faz baldeação. Desenhou só linhas retas, horizontais, verticais e a $45°$, com as estações a distâncias iguais.
O mapa de Beck, publicado em 1933, é um grafo, e não um mapa. Distorce completamente a geografia, e por isso mesmo funciona. Quase todos os metrôs do mundo, incluindo os de São Paulo, Tóquio e Xangai, adotaram o mesmo princípio. O preço é que os turistas às vezes tomam o metrô para ir a uma estação que fica a cinco minutos a pé, porque no desenho ela parecia longe.
O mesmo grafo, desenhos diferentes
Como só as ligações importam, o mesmo grafo pode ter desenhos muito diferentes. Um quadrado com as duas diagonais e uma pirâmide de base triangular vista de cima são o mesmo grafo: quatro pontos, todos ligados entre si. Saber se dois desenhos representam o mesmo grafo é um problema surpreendentemente difícil para desenhos grandes, e tem nome: o problema do isomorfismo de grafos.
Às vezes o desenho importa. Um grafo é planar quando pode ser desenhado sem que nenhum traço cruze outro. Isso decide, por exemplo, se um circuito impresso pode ser feito numa única camada.
Exercício: uma oitava ponte
Se os moradores construíssem uma oitava ponte ligando as duas margens do rio, o passeio passaria a ser possível?
As margens tinham $3$ traços cada; com a nova ponte, passam a $4$. Os graus ficam $5$, $4$, $4$ e $3$: só dois pontos ímpares. Um passeio que atravessa cada ponte uma vez passa a existir, começando num ponto ímpar e terminando no outro.
Exercício: por que K₃,₃ não é planar
Use a fórmula de Euler para desenhos planares, $V-A+F=2$ (vértices menos arestas mais faces), para provar que $K_{3,3}$ não é planar.
$K_{3,3}$ tem $V=6$ e $A=9$. Se fosse planar, teria $F=2-6+9=5$ faces. Em $K_{3,3}$ não há triângulos (cada ligação vai de uma casa a um serviço), então cada face tem pelo menos $4$ arestas. Como cada aresta está na borda de no máximo $2$ faces, $4F\leq2A$, ou seja, $20\leq18$, o que é falso. Logo, não há desenho sem cruzamentos.
Índice do capítulo · ← O plano de Argand: o número imaginário que ganhou lugar · Provas sem palavras →