Grafos - uma introdução

Disponível somente no TrabalhosFeitos
  • Páginas : 71 (17520 palavras )
  • Download(s) : 0
  • Publicado : 29 de março de 2011
Ler documento completo
Amostra do texto
“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 daUFRJ. 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.71.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 ProblemaChinês do Carteiro . . . . . . . . . . . . . Grafos e Ciclos Hamiltonianos . . . . . . . . . . . . . . O Problema do Caixeiro Viajante – PCV . . . . . . . . Uma Palavra sobre Complexidade . . . . . . . . . . . .

4 Árvores 4.1 4.2 Definições e Caracterizações . . . . . . . . . . . . . . . Árvores Geradoras . . . . . . . . . . . . . . . . . . . . O Problema de Conexão de Peso Mínimo . . . . . . . .5 Subconjuntos Especiais de um Grafo 5.1 5.2 5.3 5.4 5.5 5.6 Conjuntos Independentes . . . . . . . . . . . . . . . .

Coloração . . . . . . . . . . . . . . . . . . . . . . . . . Aplicações de Coloração . . . . . . . . . . . . . . . . . Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . Acoplamentos . . . . . . . . . . . . . . . . . . . . . . . Acoplamentos em Grafos Bipartidos . . . .. . . . . .

“GrafosModfranci 2009/6/17 page iii Estilo OBMEP

iii 5.7 5.8 Coloração de Arestas . . . . . . . . . . . . . . . . . . . Outros Subconjuntos . . . . . . . . . . . . . . . . . . . 85 92 95 95 99

6 Grafos Planares 6.1 6.2 6.3 6.4 Índice Definições e Resultados Simples . . . . . . . . . . . . . Teorema de Kuratowski . . . . . . . . . . . . . . . . .

Dualidade . . . . . . . . .. . . . . . . . . . . . . . . . 100 O Problema das 4 Cores . . . . . . . . . . . . . . . . . 101 110

“GrafosModfranci 2009/6/17 page iv Estilo OBMEP

“GrafosModfranci 2009/6/17 page 1 Estilo OBMEP

Introdução
O leitor seria capaz de desenhar a figura 1 abaixo sem tirar o lápis do papel? Tem que ir de ponto a ponto e não pode passar pela mesma linha duas vezes. C

B

D

A Figura 1E

Foi fácil? Experimente agora começar pelo ponto B. Bem, esse problema é importante? Pensemos numa pequena cidade com pequeno orçamento. O serviço de recolhimento de lixo é feito por um pequeno caminhão. Queremos evitar o desperdício; uma boa ideia seria fazer o caminhão passar uma única vez por cada 1

“GrafosModfranci 2009/6/17 page 2 Estilo OBMEP

2 rua e retornar ao ponto de...
tracking img