História e conceitos centrais da Teoria dos Grafos

Apuntes

DEPARTAMENTO DE INFORMÁTICA Curso de Ciência da Computação 2025 Teoria dos Grafos Aula 2 Contextualização Histórica O Problema das Sete Pontes de Königsberg (1736) Duas ilhas, existentes no rio Pregel em Königsberg (Rússia), foram ligadas as margens do rio através de 7 pontes. É possível iniciar uma caminhada a partir de um dos blocos de terra, passar por cada uma das pontes e voltar ao ponto de partida sem nadar pelo rio? 2 UERN Grad. CC - Teoria dos Grafos Contextualização Histórica • O fundador da teoria dos grafos (hipoteticamente): Euler com o problema das sete pontes de Königsberg na Rússia (1736). 3 UERN Grad. CC - Teoria dos Grafos Leonhard Euler (1707-1783) http://pt.wikipedia.org/wiki/Sete_Pontes_de_K%C3%B6nigsberg 4 3 2 1 4 UERN Grad. CC - Teoria dos Grafos Contextualização Histórica Rio Pregel e suas sete pontes. Königsberg - Kalinigrado nos tempos atuais. Contextualização Histórica 5 UERN Grad. CC - Teoria dos Grafos • O problema das pontes de Königsberg – Resolvido em 1736 por Leonhard Euller através de um modelo de grafos. – Abstração de detalhes irrelevantes: • Área de cada ilha • Formato de cada ilha • Tipo da ponte, etc. Contextualização Histórica 6 UERN Grad. CC ...