Euler

Leonhard Euler
Teoria dos Grafos

Um pouco de história... histó
Prof. Humberto Brandão [e-mail] aula disponível no site: http://bcc.unifal-mg.edu.br/~humberto/
Universidade Federal de Alfenas Departamento de Ciências Exatas versão da aula: 0.2

•

Em 1735, Euler ganha fama mundial ao 1735 resolver um problema que por décadas foi desafio para os matemáticos da época (Série infinita da soma dos inversos dos quadrados – conhecido como problema da Basiléia); A maioria dos grandes matemáticos de seu tempo tentaram sem êxito encontrar o resultado desta série infinita;

•

• Euler possuía apenas 28 anos na época; possuí

Leonhard Euler
• Um ano mais tarde (1736), Euler resolve o problema conhecido como as Sete pontes de Königsberg. nigsberg. • É possível que uma pessoa faça um percurso na cidade de tal forma que inicie e volte a mesma posição passando por todas as pontes somente uma única vez?

As Sete Pontes de Königsberg
• Euler resolve este problema simplificando a forma de se enxergar o mapa: • Cada faixa de terra representa um ponto, e as pontes são ligações entre os pontos.

As Sete Pontes de Königsberg

As Sete Pontes de Königsberg
• Obviamente, existem duas respostas possíveis para o possí dilema:
– Ou Existe solução... soluç ão
• Basta mostrar uma!!! Fácil... ☺ • Será mesmo simples??? Para todo problema...

– Ou não existe solução. soluç ão
• Pode se mostrar enumerando todos os caminhos possíveis, e possíveis mostrar que todos falham;
– Árvore de possibilidades; possibilidades

• ou de forma mais elegante, provando através das atravé características do grafo caracterí que não existe solução soluç para o problema. problema

As Sete Pontes de Königsberg
• Aparentemente não existe solução; soluç ão • Partindo do vértice A, toda vez que se passa por qualquer outro vértice, duas arestas são usadas: a de “chegada” e a de “saída”. chegada” saí da”

As Sete Pontes de Königsberg
• No entanto, temos:
– grau(A) = grau(C) =