(1) Introdução à Teoria dos Grafos: Breve contexto histórico

Prévia do material em texto

Introdução à Teoria dos Grafos 
 
Breve contexto histórico 
 
O estudo dos grafos teve 
origem no século XVIII em 
Königsberg, uma importante 
cidade da antiga Prússia, ao 
norte da Europa, pelo 
matemático e físico suíço 
Leonhard Euler. A cidade 
possuía duas ilhas cortadas 
pelo Rio Pregel e, na época, 
seis pontes as ligavam às 
margens e outra fazia a ligação 
das duas ilhas entre si. 
 
Por volta de 1735, os 
moradores de Königsberg 
desafiaram-se com o seguinte 
problema: Como seria possível fazer um passeio a pé pela cidade de forma a passar uma única vez 
por cada uma das sete pontes e retornar ao ponto de partida. 
 
 
 
Euler demonstrou que o problema das pontes de Königsberg não tem solução, usando um modelo 
simplificado de ligações entre as regiões. 
 
 
 
Euler usou um raciocínio muito simples. Transformou os caminhos em “retas”, que seriam as ligações 
e suas interseções em pontos, criando, possivelmente, o primeiro grafo da história. 
A partir da análise do problema, Euler concluiu que este não possuía solução, pois não era possível 
fazer um passeio a pé pela cidade de forma a passar uma única vez por cada uma das sete pontes e 
retornar ao ponto de partida. Isso porque cada ilha possuía um número ímpar de pontes que as 
ligavam com as demais ilhas e essa quantidade ímpar de pontes não permitia que o percurso fosse 
finalizado na ilha que se iniciou.