ENG1529 - 2012 Cap 2

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 1
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Grafo
Goldbarg e Luna, 2000
Grafo é uma estrutura de abstração que representa um conjunto de elementos 
denominados nós e suas relações de interdependência ou arcos.
2 - Introdução aos grafos e as redes
Um grafo é uma representação gráfica de interdependência entre elementos que 
são representados por nós (ou vértices). Esses elementos que atendem à relação 
imaginada são simbolicamente unidos através de traços denominados arcos (ou 
arestas).
Um grafo pode ser representado por: G = (N,A) ou G(N,A)
N - > o conjunto de nós da estrutura.
A - > o conjunto de arcos ou ligações entre os nós.
Considera-se que a teoria dos grafos foi iniciada 
com a publicação, em 1736, da solução do 
problema das pontes de Königsberg por Leonard 
Euler. 
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Exemplo de Grafo - G(N,A)
Goldbarg e Luna, 2000
1
2
4 3
7
5
a
b
c
d
f
e
G = (N,A) = ({1,2,3,4,5,7} , {a,b,c,d,e,f})
= ({1,2,3,4,5,7} , {(7,5),(1,2),(2,3),(3,5),(4,7),(1,4)})
conjunto de nós
conjunto de arcos
2 - Introdução aos grafos e as redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Rede
Rede é um grafo associado a grandezas numéricas ou físicas como 
distância, peso, demandas, custo, etc.
Nó
Fonte
Nó
Sumidouro
Nó
Intermediário
Nó
Intermediário (distância, custo, tempo)
(10, 4, 3) (11, 2, 2)
(14, 5, 5) (13, 3, 2)
(5, 1, 1)
2 - Introdução aos grafos e as redes
Goldbarg e Luna, 2000
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Definições Básicas (I)
Grafo direcionado (orientado): quando o sentido das ligações 
entre os nós é importante. 
Goldbarg e Luna, 2000
Grafo não direcionado (não orientado): quando não existe 
sentido para as arcos que ligam os nós. 
a
d
c
b
a
d
c
b
2 - Introdução aos grafos e as redes
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 2
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Definições Básicas (II)
Os nós a e b são adjacentes quando existe um arco “c” os unindo. 
a bc
A adjacência pode ser insuficiente 
para os grafos orientados. Existe 
então, o conceito de sucessores e 
antecessores de um nó.
Goldbarg e Luna, 2000
a
d
c
ebAntecessor de b Sucessores
de b
2 - Introdução aos grafos e as redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Definições Básicas (III)
Laço: é um arco formado por um par de nós idênticos.
Arcos múltiplos ou paralelos: quando existe mais de uma 
arco entre o mesmo par de nós.
a b
c
d
Um grafo que permite a existência de arcos múltiplos é um 
multigrafo.
2 - Introdução aos grafos e as redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Definições Básicas (IV)
Nó isolado: qualquer nó “a” de grau zero. a
Grau de um nó: é o número de arcos que incidem em um nó “a” ou o 
número de nós adjacentes de “a”.
a ba
Grau (a) = 2
a b a b
Grau (a) = 1 Grau (a) = 2 Grau (a) = 4
Grafo regular: um grafo é regular de grau ß quando todos seus nós 
possuem o mesmo grau ß.
OBS: A soma dos graus de todos os nós de um grafo é sempre par.
2 - Introdução aos grafos e as redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Definições Básicas (V)
b
c
a
e
f
d
Grafo bipartido
b
c
a
e
f
d
Grafo bipartido completo
Goldbarg e Luna, 2000
N1 N2 N1 N2
2 - Introdução aos grafos e as redes
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 3
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Definições Básicas (VI)
b
a
e
d
Grafo Planar: quando o esquema admitir pelo menos uma
representação planar, ou seja, quando traçado em um plano dois arcos
quaisquer se toquem, no máximo, em alguma extremidade.
Esquema não planar
b
a
e
d
Esquema planar
Goldbarg e Luna, 2000
2 - Introdução aos grafos e as redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Definições Básicas (VII)
b
a
e
c
Um grafo é denominado árvore se for conectado e não possuir ciclos. 
Árvore
Goldbarg e Luna, 2000
d
2 - Introdução aos grafos e as redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Goldbarg e Luna, 2000
Sub-grafo 
b
a
e
c
Grafo G
d
b
a
e
c
Sub-grafo Gs
d
Gs = G – (bc) – (ec)
є є 
2 - Introdução aos grafos e as redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Goldbarg e Luna, 2000
Grafo Complementar 
G = (Nc,Ac) é um grafo complementar de G quando Nc = N e Ac A = ø
b
a
e
c
Grafo G
d
b
a
e
c
Complementar Gc
d
U
Dois nós de G são adjacentes em Gc se e somente se eles não são
adjacentes em G.
2 - Introdução aos grafos e as redes
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página:
4
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Goldbarg e Luna, 2000
Isomorfismo 
Dois grafos G1 e G2 são ditos isomorfos quando é possível
estabelecer uma correspondência biunívoca entre nós e arcos, bem
como entre as relações Nós X Arcos.
b
a
ec
d
b
a
e
d
c
Grafos isomorfos são analiticamente idênticos, contudo são
representados graficamente de forma diferente.
2 - Introdução aos grafos e as redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Conexidade de Grafos
1 2
6 3
5 4
Goldbarg e Luna, 2000
1 2
6 3
5 4
Grafo conexo Grafo não conexo
2 - Introdução aos grafos e as redes
Um grafo G é conexo se existe pelo menos 
um caminho (ou cadeia) entre qualquer par 
de nós de G. Caso contrário o grafo é 
desconexo.
Todo grafo desconexo é composto por
subgrafos conexos chamados de
componentes.
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Pizzolato, 2003
Caminho 
Caminho: é um uma seqüência de nós e arcos sem a repetição de nós 
e arcos.
b
a
e
d
cf
Caminho f – e {u1,u2,u3,u4}
u1 u2
u3
u4
2 - Introdução aos grafos e as redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Pizzolato, 2003
Comprimento do Caminho 
Comprimento de um Caminho:
Grafo não direcionado - é o número de arcos desse caminho;
Grafo direcionado - é a soma dos pesos dos arcos desse caminho.
b
a
e
d
cf
Comprimento do
caminho = 4
b
a
e
d
cf
1 3
7
4
Comprimento do
caminho = 15
2 - Introdução aos grafos e as redes
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 5
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Pizzolato, 2003
Grafos Hamiltoniano X Grafos Euleriano
e
a
f
b
g
c
h
d
e
a
f
b
g
c
h
d
e
a
f
b
g
c
h i
e
a
g
c
h i
Hamiltoniano Não Hamiltoniano
Não 
Euleriano
Euleriano
Grafo Euleriano: a meta é percorrer os arcos sem repetição.
Grafo Hamiltoniano: a meta é percorrer os nós sem repetição.
2 - Introdução aos grafos e as redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Ciclos e Circuitos Especiais
Goldbarg e Luna, 2000
1 2
6 3
5 4
Circuito Hamiltoniano:
Trata-se de um circuito que 
passa por todos os nós de G.
1 2
6 3
5 4
Percurso Hamiltoniano Percurso Euleriano
Percurso: denominação genérica para qualquer trajetória sobre nós e arcos de G.
2 - Introdução aos grafos e as redes
Ciclo Euleriano:
Trata-se de um ciclo que passa 
por todos os arcos do grafo G.
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Cadeia – seqüência de arcos tais que cada arco tem um ponto 
comum com o arco precedente e com o seguinte. Os arcos são não 
orientados.
Ciclo – cadeia fechada.
Caminho – cadeia em que todos os arcos são orientados no mesmo 
sentido.
Circuito – caminho fechado.
Cadeia, Ciclo, Caminho e Circuito
2 - Introdução aos grafos e as redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Representação Através da Matriz de Adjacência
Goldbarg e Luna, 2000
1 2
4 3
6 5
1 2 3 4 5 6
1 0 0 0 1 0 0
2 0 0 1 1 0 0
3 0 1 0 1 0 0
4 1 1 1 0 1 1
5 0 0 0 1 0 0
6 0 0 0 1 0 0
O grafo é expresso em uma matriz A = [aij] através de nós e de suas 
relações de vizinhança. As linhas e as colunas da matriz estão associadas 
aos nós do grafo. 
Uma matriz n X n, onde A=[aij] é denominada como de adjacência do 
grafo G = (N,A) se: aij = 1 � Ligação (i,j)
aij = 0 � Ligação (i,j)
E
E
2 - Introdução aos grafos e as redes
Nó
Nó
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 6
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Representação Através da Matriz de Incidência em 
Grafo Não-direcionado
Goldbarg e Luna, 2000
1 2
3
4 5
u1 u2 u3 u4
1 1 0 0 0
2 0 1 0 0
3 1 1 1 1
4 0 0 1 0
5 0 0 0 1
u1 u2
u3 u4
2 - Introdução aos grafos e as redes
Dado um grafo G(N,A) de n nós e m arcos a matriz de incidência de G é denotada 
por B = [bij] é uma matriz n x m definida por:
bij = 1 se Ni é nó de aj
0 caso contrário
Nó
Arco
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Representação Através da Matriz de Incidência em 
Grafo Direcionado
Goldbarg e Luna, 2000
1 2
3
4 5
u1 u2 u3 u4
1 1 0 0 0
2 0 1 0 0
3 -1 -1 1 1
4 0 0 -1 0
5 0 0 0 -1
Uma matriz n X m, onde A=[aij] é denominada como de incidência do grafo 
G = (N,A) se: 
aij = +1 se arco (j) é incidente do nó i (exteriormente). “Sai”
aij = - 1 se arco (j) é incidente do nó i (interiormente). “Chega”
aij = 0 nos outros casos
u1 u2
u3 u4
2 - Introdução aos grafos e as redes
Nó
Arco