Introdução a teoria dos grafos

Nota de aula 1 da disciplina de Teoria dos Grafos
Professor: Leonardo Sampaio
25 de abril de 2014
Como dispor cabos com um m´nimo de custo de maneira que todos os telefones possam ser alcancados um ı ¸
´
´ a partir do outro? Qual e o caminho mais r´ pido da capital de um estado at´ cada cidade do interior? Qual e a a e
´
quantidade m´ xima de agua que pode passar de uma fonte at´ um destino utilizando uma rede de dutos? Quantas a e camadas deve ter um chip de computador de maneira que os fios em uma mesma camada n˜ o se cruzem? Como a os jogos de um campeonato devem ser programados de maneira que o campeonato dure o menor tempo poss´vel? ı Em que ordem uma transportadora deve visitar um conjunto de cidades de maneira a minimizar o tempo total
´
de viagem? E poss´vel colorir as regi˜ es de qualquer mapa utilizando quatro cores de maneira que regi˜ es com ı o o fronteira comum possuam cores distintas?
´
Todos estes problemas pr´ ticos e muitos outros envolvem a teoria dos grafos. O objetivo desta disciplina e a introduzir os principais conceitos e resultados desta teoria.

1

O problema das pontes de K¨ nigsberg o Muitos autores consideram que o seguinte problema iniciou a teoria dos grafos.
`
Problema 1.1 (O problema das pontes de K¨ nigsberg). A cidade de K¨ nigsberg era localizada a beira do rio o o
Preg´ lia, na R´ ssia. A cidade ocupava duas ilhas, al´ m de territ´ rios acima e abaixo das mesmas. Estas regi˜ es o u e o o eram conectadas por sete pontes como ilustrado na Figura 1. Os habitantes da cidade se perguntavam se seria poss´vel sair de casa, cruzar cada ponte exatamente uma vez e retornar para casa. Este problema se reduz ao de ı ` atravessar a figura a direita, cujos pontos representam as regi˜ es e as ligacoes as pontes. o ¸˜

Figura 1: As pontes de K¨ nigsberg e o grafo correspondente. o `
O modelo a direita na Figura 1 fornece um argumento simples para a impossibilidade do percurso desejado