Grafos e RedesAs pontes de Königsberg

Um dos primeiros matemáticos a pensar em grafos e redes foi Leonhard Euler. Euler ficou intrigado com um antigo problema relacionado à cidade de Königsberg, perto do mar Báltico.

O rio Pregel divide Königsberg em quatro partes separadas, que são conectadas por sete pontes. É possível caminhar pela cidade atravessando todas as pontes exatamente uma vez - mas não mais de uma vez? (Você pode começar e terminar em qualquer lugar, não necessariamente no mesmo lugar.)

Tente encontrar uma rota válida desenhando nestes mapas:

Mapa 1

Mapa 2

Map 3

Map 4

No caso de Königsberg, parece impossível encontrar uma rota válida, mas em algumas outras cidades é possível. Euler conseguiu encontrar uma regra simples que pode ser aplicada a qualquer cidade, sem ter que tentar muitas possibilidades - usando a teoria dos grafos.

Primeiro, precisamos converter os mapas da cidade em grafos com arestas e vértices. Toda ilha ou região de terra é representada por e toda ponte que liga duas regiões é representada por uma correspondente.

Agora, o problema de “percorrer uma cidade enquanto atravessa todas as pontes exatamente uma vez” tornou-se um problema de “desenhar um grafo com um traço contínuo enquanto se traça cada aresta exatamente uma vez”.

No papel, crie alguns grafos diferentes e tente descobrir quais podem ser desenhados com apenas um único traço contínuo.

Assim como nos mapas da cidade, descobrimos que alguns grafos são possíveis, enquanto outros não. Para nos ajudar a entender o porquê, rotulemos cada vértice com seu grau. Em seguida, podemos colorir os vértices de maneiras diferentes e tentar revelar um padrão:

Valor

Tamanho

Números primos

Par e ímpar

Esses grafos são possíveis:

Esses grafos não são possíveis:

Comparando esses números para grafos possíveis e não possíveis, parece que um grafo pode ser desenhado se . Essa condição pode ser explicada se observarmos apenas um único vértice no grafo:

Aqui pode ser visto um único vértice ampliado do grafo.

Se desenharmos o grafo, eventualmente teremos uma aresta entrando nesse vértice, e outra aresta saindo. Ou seja, temos duas arestas se encontrando neste vértice.

Possivelmente o vértice é um cruzamento em vez de uma beirada. Nesse caso se terá outra aresta entrando no vértice e outra aresta saindo vértice e teremos quatro arestas.

E em alguns grafos, pode até haver um terceiro par de arestas entrando e saindo do vértice. Nesse caso teremos seis arestas.

Em todo caso, note que sempre há um número par de arestas se encontrando no vértice.

As únicas exceções são os vértices onde o caminho começa e onde o caminho termina. Esses dois vértices podem ter um número ímpar de arestas. Se o ponto de partida e o ponto de término são o mesmo, todos vértices do grafo são possuem um número par de arestas.

Se você voltar ao mapa de Königsberg, verá que existem mais de duas ilhas com um número ímpar de pontes. Portanto, uma rota que atravessa todas as pontes exatamente uma vez é realmente impossível - e foi isso que Leonard Euler descobriu.

A descoberta de Euler pode não parecer particularmente útil na vida real, mas os grafos estão na base de muitos outros problemas geográficos, como encontrar direções entre dois locais. Descobriremos mais aplicações mais tarde.

Mudar idioma

Entrar no Mathigon

Compartilhar

Redefinir progresso

Glossário

Grafos e RedesAs pontes de Königsberg

Mapa 1

Mapa 2

Map 3

Map 4