Grafos

PCS 2214 – Fundamentos de Engenharia de Computação I
PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo:Grafos

1o. Semestre 2006 GRAFOS Professores: Anna Helena Reali Costa Jaime Simão Sichman Liria Matsumoto Sato Romero Tori

Autor: Liria M. Sato

Versão: 1.0 Data: 22/02/06

1

Conteúdo
1. 2. 3. 4. 5. 6. 7. Grafos: histórico e conceitos Caminhos (rotas) e Ciclos Ciclo de Euler Ciclo de Hamilton Algoritmo do Caixeiro Viajante Algoritmo do Caminho Mínimo Grafos Isomorfos e Planares.

PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo:Grafos

Autor: Liria M. Sato

Versão: 1.0 Data: 22/02/06

2

1

Histórico
• Primeiro trabalho usando teoria de grafos (1736): Euler – solução para o problema das pontes de Königsberg. • Primeiro texto (1936): desde esta época o interesse em teoria dos grafos tem sido intenso e amplo. • Aplicabilidade em diversos campos: na ciência da computação, na química, na engenharia elétrica, na economia.

PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo:Grafos

Autor: Liria M. Sato

Versão: 1.0 Data: 22/02/06

3

Histórico
Problema da ponte de Königsberg (solução apresentada por Euler em 1736)
A Pregel River B D
Autor: Liria M. Sato

PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna H. R. Costa Jaime S. Sichman Líria M. Sato Romero Tori © 2005 Módulo:Grafos

A C B D

C

Versão: 1.0 Data: 22/02/06

4

Problema: iniciar em qualquer lugar, A,B,C ou D, atravessar cada ponte exatamente uma vez; e então retornar para o lugar inicial.

2

Conceitos principais
Grafos Grafo (ou grafo não orientado) G: consiste de um conjunto V de vértices (ou nós) e um conjunto E de arestas (ou arcos) tal que cada aresta e∈ E é associada a um par não ordenado de vértices. Se existe uma única