Pesquisa Operacional

Introdução

Grafos

Grafos
Grafos

Prof. Dr. Julio Arakaki www.pucsp.br/~jarakaki ([e-mail])
Depto. Ciência da Computação

© Julio Arakaki

1

Ciência da Computação

Introdução

Grafos

Problema – Abstração – Modelo – Solução
Problema – Abstração – Modelo – Solução
Problema Real (Muitos)

Abstração (Análise do problema)
Modelagem

Grafos (Ferramenta de abstração)
Aplicação de algoritmos

Solução no domínio dos Grafos

© Julio Arakaki

2

Ciência da Computação

1

Introdução

Grafos

O que é um Grafo? (formal)
O que é um Grafo? (formal)
“Um grafo é representado como um conjunto de pontos
(vértices) ligados por retas (as arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por setas".
- Wikipédia -

© Julio Arakaki

3

Ciência da Computação

Introdução

Grafos

O que é um Grafo? (mais informal)
O que é um Grafo? (mais informal)

“Abstração que permite representar o relacionamento entre pares de elementos“
Onde:
Elementos – vértices do grafo
(computadores, empresas, cidades, paises, pessoas, páginas web, etc...)
Relacionamentos – arestas do grafo
(conexão, distância, amizade, custo, etc...)

© Julio Arakaki

4

Ciência da Computação

2

Introdução

Grafos

Exemplo de Grafo: Tráfego Rodoviário/Aéreo
Exemplo de Grafo: Tráfego Rodoviário/Aéreo
Transporte comercial entre cidades

Vôo entre as cidades São Paulo
Campo Grande

Rio de Janeiro

Brasília
Cuiabá

© Julio Arakaki

5

Ciência da Computação

Introdução

Grafos

Exemplo de Grafo: Executando tarefas
Exemplo de Grafo: Executando tarefas
Tarefa

Relacionamento entre tarefas:
“B depende de E”

- Todas as tarefas podem ser executadas?
-Qual a ordem de execução?
(Semelhante a um Sistema de N módulos com dependências entre si – diversas bibliotecas.
Qual a seqüência/ordem de compilação ou execução dos módulos?) © Julio Arakaki

6

Ciência da