Grafos
16474 palavras
66 páginas
“GrafosModfranci2009/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 . . . . . . . . . . . . . . . . . .