Teoria dos Grafos

“GrafosModfranci
2009/6/30
page 1
Estilo OBMEP

Grafos – Uma Introdução
Samuel Jurkiewicz

“GrafosModfranci
2009/6/30
page 2
Estilo OBMEP

Texto já revisado pela nova ortografia.

“GrafosModfranci
2009/6/30
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/30
page 4
Estilo OBMEP

“GrafosModfranci
2009/6/30
page i
Estilo OBMEP

Sumário
1 O que é um Grafo?

5

1.1

Primeiras Noções . . . . . . . . . . . . . . . . . . . . .

5

1.2

Grau de um Vértice . . . . . . . . . . . . . . . . . . .

7

1.3

Nosso Primeiro Resultado . . . . . . . . . . . . . . . .

10

1.4

Alguns Problemas com as Definições . . . . . . . . . .

11

1.5

Isomorfismo . . . . . . . . . . . . . . . . . . . . . . . .

13

1.6

Outras Definições . . . . . . . . . . . . . . . . . . . . .

16

1.7

Tipos Especiais de Grafos . . . . . . . . . . . . . . . .

17

1.8

Representação por Matrizes . . . . . . . . . . . . . . .

22

2 Ciclos e Caminhos

28

2.1

Conexidade Outra Vez . . . . . . . . . . . . . . . . . .

28

2.2

O Problema do Menor Caminho

. . . . . . . . . . . .

31

Algoritmos e Computadores . . . . . . . . . . . . . . .

31

Qual o Menor Caminho até a Escola? . . . . . . . . . .

32

3 Mais Ciclos e mais Caminhos i 45

“GrafosModfranci
2009/6/30
page ii
Estilo OBMEP

ii

SUMÁRIO

3.1

Euler e as Pontes de Köenisberg . . . . . . . . . . . . .

45

Esse Problema é Importante? . . . . . . . . . . . . . .

47

3.2

Estrutura de Dados . . . . . . . . . . . . . . . . . .