Grafos - uma introdução

“GrafosModfranci 2009/6/17 page 1 Estilo OBMEP

Grafos – Uma Introdução
Samuel Jurkiewicz

“GrafosModfranci 2009/6/17 page 2 Estilo OBMEP

Texto já revisado pela nova ortografia.

“GrafosModfranci 2009/6/17 page 3 Estilo OBMEP

Sobre o Autor Samuel Jurkiewicz é carioca e Doutor em Matemática pela Universidade Pierre et Marie, em Paris. Atualmente é professor da Escola de Engenharia da UFRJ. Já atuou como docente em todos os níveis, inclusive no pré-escolar. Além do ensino de graduação e pós-graduação, tem desenvolvido atividades junto a professores e alunos do Ensino Médio através de oficinas de Matemática Discreta.

“GrafosModfranci 2009/6/17 page 4 Estilo OBMEP

“GrafosModfranci 2009/6/17 page i Estilo OBMEP

Sumário
1 O que é um Grafo? 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Primeiras Noções . . . . . . . . . . . . . . . . . . . . . Grau de um Vértice . . . . . . . . . . . . . . . . . . . Nosso Primeiro Resultado . . . . . . . . . . . . . . . . Alguns Problemas com as Definições . . . . . . . . . . Isomorfismo . . . . . . . . . . . . . . . . . . . . . . . . Outras Definições . . . . . . . . . . . . . . . . . . . . . Tipos Especiais de Grafos . . . . . . . . . . . . . . . . Representação por Matrizes . . . . . . . . . . . . . . . 5 5 7 10 11 13 16 17 22 28 28 31 31 32 45

2 Ciclos e Caminhos 2.1 2.2 Conexidade Outra Vez . . . . . . . . . . . . . . . . . . O Problema do Menor Caminho . . . . . . . . . . . .

Algoritmos e Computadores . . . . . . . . . . . . . . . Qual o Menor Caminho até a Escola? . . . . . . . . . . 3 Mais Ciclos e mais Caminhos i

“GrafosModfranci 2009/6/17 page ii Estilo OBMEP

ii 3.1

SUMÁRIO

Euler e as Pontes de Köenisberg . . . . . . . . . . . . . Esse Problema é Importante? . . . . . . . . . . . . . .

45 47 48 51 57 58 59 62 66 66 68 68 73 73 76 77 82 82 84

3.2 3.3 3.4 3.5 3.6 3.7

Estrutura de Dados . . . . . . . . . . . . . . . . . . . . Grafos Eulerianos . . . . . . . . . . . . . . . . . . . . . O Problema