Problema das Pontes de Königsberg

Problema


No século 18 havia na cidade de Königsberg um conjunto de sete pontes (identificadas pelas letras de a até f na figura abaixo) que cruzavam o rio Pregel . Elas conectavam duas ilhas entre si e as ilhas com as margens



Por muito tempo os habitantes daquela cidade perguntavam-se se era possível cruzar as sete pontes numa caminhada contínua sem passar duas vezes por qualquer uma delas.



Modelo do Problema


O Grafo utilizado como modelo é definido como segue:

V = { m | m é uma ilha ou uma margem }
A = { (m1,m2, p} | existe uma ponte p unindo as margens ou ilhas m1 e m2 }

Os conjuntos acima são apresentados, a seguir, na forma extensiva, contendo todos seus elementos, extraídos do problema:

V = { A, B, C, D }
A = { (A,C,c), (A,C,d), (A,B,a), (A,B,b), (A,D,e), (B,D,f), (C,D,g) }

O Grafo, construído a partir dessas definições pode se apresentar como:




Observação sobre o Grafo:

Não orientado

Multigrafo

Conexo



Solução


A solução consiste em, partindo de qualquer vértice, tentar atravessar todas as arestas uma única vez e retornar ao vértice de origem.
Euler, ao propôr a solução para este problema, se preocupou em descobrir em que tipos de grafos se pode fazer esse caminhamento fechado, passando por todas as arestas uma única vez. Esse tipo de caminhamento foi chamado 'caminho de Euler', e um grafo que consiste de um caminho de Euler foi denominado 'grafo de Euler'.
Como todo grafo de Euler possui um caminho de Euler, como o proposto no problema das pontes de Königsberg, para sabermos se existe solução, basta sabermos se o grafo modelo do problema é um grafo de Euler ou não.

TEOREMA: Um grafo conexo G é um grafo de Euler se e somente se todos os seus vértices são de grau par.

PROVA: Imagine que G seja um grafo de Euler. Então ele contém um caminho de Euler. Seguindo esse caminho nota-se que chegamos num vértice 'entrando'por uma aresta e encontramos outra para 'sair' do vértice e continuar o caminho. Se houver outras arestas adjacentes ao vértice, 'entramos' por uma destas arestas e devemos encontrar uma, ainda não visitada, para 'sairmos' do vértice. Se houver um número n ímpar de arestas em pelo menos um dos vértices, ao realizar o caminhamento, cruzaremos esse vértice (n / 2) vezes, passando por (n-1) arestas. Ao passarmos pela n-esima aresta, 'entraremos' no vértice e não encontraremos mais arestas ainda não visitadas. O caminhamento não pode continuar.

Solução: Pela análise do grafo modelo G para o problema das pontes de Königsberg, observa-se que Para Todo v E V, gr(v) é ímpar. Logo, o grafo G não é um grafo de Euler. Isso significa que o problema não possui solução. Note que não é necessário que tenhamos Para Todo v E V, gr(v) é impar , basta que Exista Pelo Menos Um v E V | gr(v) é impar para concluirmos que o grafo em questão não é um grafo de Euler.