Passeios De Euler E As Pontes De Königsberg

Passeios de Euler e as pontes de Königsberg

João Carlos V. Sampaio

UFSCar

[e-mail]

Königsberg era uma cidade da antiga Prússia, hoje chamada Kaliningrado, na atual Rússia.

Na parte central de Königsberg, fluíam vertentes do rio Pregel, formando uma ilha.

Sete pontes, interligando partes da cidade, foram construídas, como representado na

figura abaixo.

Figura 1. Diagrama das sete pontes de Königsberg.

Um desafio, proposto pelos habitantes de Königsberg, era fazer um passeio, passando

pelas sete pontes, porém apenas uma vez sobre cada ponte. Tente traçar, a lápis,

um caminho realizando esse passeio.

Um matemático suíço, de nome Leonhard Euler (leia-se “Óiler”), em 1736, não

somente elucidou a natureza desse problema, como acabou por criar uma teoria que se

aplica a vários problemas desse tipo.

Euler pensou: “este é um tipo de problema no qual as distâncias envolvidas são

irrelevantes. O que importa é como as várias porções de terra estão interligadas entre si.”

Euler queria dizer que este problema pode ser pensado, geometricamente, da seguinte

maneira. Há quatro porções de terra envolvidas, separadas umas das outras pelas

águas do rio Pregel. São elas: N (norte), S (sul), A (ilha central) e B (leste), como na

Figura 1. Um diagrama, representando as várias interligações entre essas porções de terra,

é mostrado na Figura 2. Esse diagrama é um exemplo de um “grafo”.

Figura 2. O grafo das sete pontes de Königsberg.

Rio Pregel Velho

N (norte de Königsberg)

S (sul de Königsberg)

A B

Rio Pregel Novo

Rio Pregel

B

N

A

S

2

Um grafo é uma figura, constituída de um número finito de arcos (ou curvas),

chamadas “arcos” ou “arestas” do grafo, cujas extremidades são chamadas de “vértices”

do grafo. Um mesmo vértice pode pertencer a vários arcos, e dois arcos só podem ter em

comum um ou dois vértices de suas extremidades. As duas extremidades de um arco

podem coincidir, dando lugar a um único vértice (esquerda da Figura 3a). Um grafo pode

ter