pesquisa operacional

Pesquisa Operacional II
Profª Lidia, Prof. Paulo Sérgio Coelho

Teoria dos Grafos
Caminho Mínimo
Árvore Geradora Mínima
Fluxo Máximo

Teoria dos Grafos




Pontes de Königsberg na
Prússia que cruzam o rio
Pregel (atual Kalingrado, na Russia): “seria possível percorrer todas as quatro seções e voltar ao local de partida cruzando cada ponte uma única vez?”
Resolvido por Leonhard
Euler XVIII, resposta: não é possível realizar tal percurso 1

Teoria dos Grafos


Um grafo é uma noção simples e abstrata utilizada para representar a idéia de relação entre “elementos". Exemplos: relações de amizade, entre pais e filhos, entre irmãos, etc.
João
Pedro

João

Maria

Maria
Marta

Tereza

Tereza
(X, Y) → X é pai/ mãe de Y

(X, Y) → X é irmão de Y

Teoria dos Grafos






Matematicamente: G = (V,A), onde V é o conjunto de vértices e A é o conjunto de ligações entre vértices.

Grafo não orientado: ligações representadas os pares de vértices não possuem uma ordem
(i,j) = (j,i) = [i,j], aresta
Grafo orientado (dígrafo): ligações (arcos) representadas por partes ordenados (i,j)  (j,i)

2

Teoria dos Grafos

Grafo não orientado
V=(1,2,3,4,5,)
A=([1,2],[1,3],[1,5],[2,4],
[3,2][3,5],[3,4],[4,5])
n = 5, m=8

Grafo orientado
V=(A,B,C,D,E)
A=((A,B),(A,D),(A,C),(B,C),
(C,E),(D,E),(E,D))
n = 5, m = 7

Grafos valorados, valores associados às ligações = Redes

Representação de um Grafo


Listas de Adjacências: armazena o relacionamento entre os vértices em uma estrutura de listas.
Representação econômica do ponto de vista computacional. Grafos orientados: duas listas origem - destinos e destino - origens
Grafo não orientados: uma lista

3

Representação de um Grafo


Matriz de adjacências: dois vértices são adjacentes se estão unidos por uma aresta ou arco. Matriz Mnxn (n total de vértices)

Exemplo:

aij  1  (i, j)  A.

M 
aij  0  (i, j)  A.
