Pesquisa Operacional (Grafos)

Prévia do material em texto

Grafos
Raphael Ramos
Histo´rico
Problema das Pontes de Konigsberg
No se´culo 18, na cidade de Ko¨nigsberg (antiga Pru´ssia), um
conjunto de sete pontes cruzavam o rio Pregel. Elas
conectavam duas ilhas entre si (A e D) e as ilhas com as
margens (C e B). Os habitantes perguntavam: E´ poss´ıvel
cruzar as sete pontes numa caminhada cont´ınua sem passar
duas vezes por qualquer uma delas? Em 1736, Euler apresenta
a soluc¸a˜o deste problema na Academia de Sa˜o Petersburgo,
sendo este o primeiro trabalho sobre Grafos.
Pontes de Konigsberg
Introduc¸a˜o
Um grafo (= graph) e´ uma estrutura formada por dois tipos
de objetos: ve´rtices (= vertices) e arestas (= edges). Cada
aresta e´ um par na˜o ordenado de ve´rtices, ou seja, um
conjunto com exatamente dois ve´rtices. Uma aresta como v, w
sera´ denota simplesmente por vw ou wv; diremos que a aresta
incide em v e em w; diremos tambe´m que v e w sa˜o as pontas
da aresta; diremos, ainda, que os ve´rtices v e w sa˜o vizinhos
(= neighbors), ou adjacentes (= adjacent).
Exemplo
Os ve´rtices do grafo sa˜o t, u, v, w, x, y, z e as arestas sa˜o vw, uv, xw, xu, xy e yz.
A figura abaixo e´ uma representac¸a˜o gra´fica desse grafo
v
u
w
x
y
t
z
Grafos
• conjunto de ve´rtices;
• conjunto de arestas;
• aresta = par de ve´rtices;
• ve´rtices adjacentes;
• G = (V, A)
Aplicac¸o˜es
Ferramenta simples e poderosa para a construc¸a˜o de modelos
e resoluc¸a˜o de diversos problemas
• Processos industriais;
• Ta´tica e log´ıstica;
• Sistemas de comunicac¸a˜o;
• Redes de computadores;
• Engenharia;
• Computac¸a˜o;
• Jogos.
Definic¸o˜es
Grafo
Um grafo G(V, A) e´ definido pelos conjuntos V e A, onde:
• V e´ um conjunto na˜o vazio: Ve´rtices, Nodos ou No´s do
grafo;
• A e´ um conjunto de pares ordenados a=(v,w) com v e w
pertencente a V: Arestas, Linhas ou Ramos do grafo
Exemplo
Grafo - G1
• V = p | p e´ uma pessoa
• A = (v,w) | v e´ amiga de w
• V = Maria, Jose´, Ana, Luiz
• A = (Maria, Jose´), (Maria, Ana), (Jose´, Luiz), (Jose´,
Ana)
Maria
Ana
Jose´
Luiz
D´ıgrafo
Grafo orientado - G2
• V = p | p e´ uma pessoa
• A = (v,w) | v e´ pai ou ma˜e de w
Joana
Joa˜o
Paulo
Ana
Maria
Ordem
G3
E´ o nu´mero de ve´rtices do grafo:
Maria
Ana
Jose´
Luiz
Ordem = 4
Ordem
G4
A
B
C
D
E
F
G
Ordem = 7
Adjaceˆncia
• Dois ve´rtices - v e w de um grafo - sa˜o adjacentes se ha´
uma aresta a=(v,w) no grafo
• Jose´ e Luiz em G1
• Duas arestas sa˜o adjacentes se incidem sobre o mesmo
ve´rtice
• Ex: (Ana, Maria) e (Ana, Jose´) em G1
Adjaceˆncia
Grau de um ve´rtice - G4
A
B
C
D
E
F
G
B e´ adjacente a A. Mas a na˜o e´ adjacente a B.
Grau
Grau de um ve´rtice - G5
E´ o nu´mero de arestas incidentes no ve´rtice:
A
B
C
D
Grau(A) = 3 Grau(B) = 2
Grau
Digrafo
A
B
C
D
E
F
G
• Grau de sa´ıda: Nu´mero de arestas que teˆm ponta inicial
no ve´rtice. Ex: Gs(A) = 3
• Grau de entrada: Nu´mero de arestas teˆm ponta final no
ve´rtice. Ex: Ge(E) = 2
Ve´rtice Isolado
v
u
w
x
y
t
z
Ve´rtice T e´ isolado
Lac¸o
• Lac¸o: E´ uma aresta do tipo a=(v,v). Ex: Ve´rtice A
A
B
C
D
9
5
Arestas Paralelas
• Arestas paralelas: Possuem os mesmos ve´rtices terminais:
ci=(v,w) e cj=(v,w). Ex: Arestas de U e X
S
U
X
V
Y
Multigrafo, Grafos Simples
• Multigrafo
• E´ o grafo que possui lac¸os e/ou arestas paralelas;
• Grafo simples
• Na˜o possui lac¸os e/ou arestas paralelas
Grafo completo
Um grafo e´ dito completo quando cada par distinto de ve´rtice e´ adjacente - G6
v
u
w
x
Grafo complementar
Um grafo G’ e´ complementar de G, se possuir a mesma ordem de G e se todas
arestas (vi, vj) pertencentes a G’, na˜o pertencerem a G.
a b
c
a b
c
Grafo Rotulado
Grafo em que cada ve´rtice esta´ associado a um ro´tulo
A (Maria)
B (Ana)
C (Jose´)
D (Luiz)
Grafo Valorado
Um grafo G(V, A) e´ dito ser valorado quando existe uma ou mais func¸o˜es
relacionando V e/ou A com um conjunto de nu´meros
A
B
C
D
E
F
2
3
5
2
5
1
2
4
Subgrafo
Um grafo Gs(Vs, As) e´ dito ser subgrafo de G(V, A) se Vs esta´ contido em V e se
As esta´ contido em A
v
u
w
x
v
u
w
Bipartido
Um grafo e´ considerado bipartido quando seu conjunto de ve´rtices V puder ser
particionado em dois subconjuntos V1 e V2, tal que toda aresta de G une um
ve´rtice de V1 a outro de V2