Aula03_grafos

Prévia do material em texto

Teoria dos Grafos
Valeriano A. de Oliveira
So
orro Rangel
Silvio A. de Araujo
Departamento de Matemáti
a Apli
ada
antunes�ibil
e.unesp.br, so
orro�ibil
e.unesp.br, saraujo�ibil
e.unesp.br
AULA 3
Grafos dire
ionados (Digrafos), Grafos e Algoritmos
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Grafos Dire
ionados
(Digrafos)
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
• Até o momento trabalhamos 
om grafos tais que as arestas são pares
não ordenados de vérti
es.
• Várias situações práti
as requerem que asso
iemos sentido às arestas
do grafo.
• P�r exemplo, 
onsidere um grafo representando as ruas de uma 
idade.
Nem todas as ruas são de mão dupla. Ao se estudar rotas de �nibus é
ne
essário 
onsiderar se as ruas são de mão úni
a, isto é permitem �uxo
apenas no sentido (vi, vj) ou se são de mão dupla.
• Outras situações são: �uxograma de programas 
omputa
ionais onde
os vérti
es representam instruções e as arestas a seqüên
ia de exe
ução;
redes elétri
as; �uxos em redes que possuem válvulas nos en
anamentos.
• Quando asso
iamos sentido às arestas do grafo temos um grafo
dire
ionado ou digrafo.
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
• A maioria dos 
on
eitos e terminologia usados para grafos
não-orientados são também apli
áveis para digrafos.
• P�r exemplo o 
on
eito de planaridade independe do sentido asso
iado
às arestas.
Vamos 
hamar atenção neste tópi
o apenas para as propriedades e
on
eitos que se apli
am apenas a digrafos. O 
on
eito formal de um
grafo dire
ionado é dado a seguir.
De�nição 1. Um grafo dire
ionado G(V,A) é 
onstituído p�r um
onjunto V = {v1, v2, . . . , vn} não-vazio de objetos, 
hamados vérti
es
(ou nós), e um 
onjunto A = {a1, a2, . . . , am} de arestas ou ar
os, e
uma apli
ação Ψ que asso
ia 
ada aresta a um par ordenado de vérti
es.
Os digrafos são representados através de um diagrama onde os vérti
es
são representados por pontos e 
ada aresta (vi, vj) é representada por
uma linha ligando vi a vj 
om uma seta apontando para vj.
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
Exemplo 1
V = {v1, v2, v3, v4, v5},
A = {(v1, v2), (v1, v3), (v2, v4), (v3, v4), (v4, v5), (v1, v2), (v2, v2)}.
v
1
v
2
v
3
v
4
v
5
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
Exemplo 2
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
Em digrafo, quando dizemos que uma aresta é in
idente a um vérti
e
queremos saber em que sentido, isto é, se a aresta é 
onvergente ou
divergente a este vérti
e.
É natural dizer que uma aresta a asso
iada ao par (vi, vj) é 
onvergente
a vj e divergente de vi.
Em relação ao grau de um vérti
e vi queremos também saber:
■ o número de arestas 
onvergentes, 
hamado grau de entrada e
denotado de(vi) (ou d
−(vi));
■ o número de arestas divergentes, 
hamado grau de saída e denotado
ds(vi) (ou d
+(vi)).
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
Exer
í
io Seja G(V,A) um digrafo. Mostre que
∑
vi∈V
de(vi) =
∑
vi∈V
ds(vi) = m,
onde m é o número de arestas de G.
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 9
Mais de�nições:
•Temos uma fonte quando o grau de entrada é nulo e um sumidouro
quando o grau de saída é nulo.
•Duas arestas são paralelas se elas in
idem nos mesmos vérti
es e
possuem a mesma orientação.
•Muitas das propriedades de grafos não orientados são válidas para
digrafos e portanto muitas vezes a orientação do grafo é des
onsiderada.
De�nimos o grafo asso
iado a um digrafo G 
omo sendo o grafo obtido
des
onsiderando a orientação de G.
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
Orientação de um grafo
•A operação oposta também pode ser 
onsiderada:
Dado um grafo (não orientado) G podemos de�nir alguma orientação
para suas arestas obtendo assim um digrafo
~G 
hamado de um digrafo
asso
iado a G.
• Observemos que enquanto o grafo asso
iado a um digrafo é úni
o (a
menos de isomor�smos), um digrafo asso
iado a um grafo pode ter
várias orientações distintas.
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
• Digrafos Isomorfos Dados digrafos G e H, dizemos que eles são
isomorfos quando os grafos asso
iados são isomorfos e além disso a
orientação das arestas 
oin
ide.
Exer
í
io: Veri�que se os pares de digrafos abaixo (G1 e G2, G3 e G4 )
são isomorfos.
G1 G2
Tipos de digrafos
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
Seja G(V,A) um digrafo. Então G é dito
■ Simples se não possui loops ou arestas paralelas;
■ Assimétri
o se possui no máximo uma aresta orientada entre 
ada
par de vérti
es;
■ Simétri
o se para 
ada aresta (a, b) existe também uma aresta (b, a);
■ Completo Simétri
o se G é simples e existe exatamente uma aresta
dire
ionada de todo vérti
e para todos os outros vérti
es;
■ Completo Assimétri
o se G é assimétri
o e existe exatamente uma
aresta entre 
ada par de vérti
es;
Tipos de digrafos (
ont.)
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
■ Balan
eado se de(vi) = ds(vi) para todo vi ∈ V ;
■ Regular se existe um inteiro k tal que tal que de(vi) = ds(vi) = k
para todo vi ∈ V . Dizemos que o digrafo é k-regular.
Exer
í
ios
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 14
1. Mostre que um digrafo 
ompleto assimétri
o 
om n vérti
es possui
n(n− 1)/2 arestas.
2. Mostre que um digrafo 
ompleto simétri
o 
om n vérti
es possui
n(n− 1) arestas.
Caminhos Orientados
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
■ De�nimos passeios, trajetos, 
aminhos e 
ir
uitos da mesma forma que para
grafos. No entanto, a orientação das arestas deve 
oin
idir:
isto é, dado um par de arestas 
onse
utivas onde v é o vérti
e 
omum, a
primeira aresta 
onverge para v enquanto a segunda diverge de v. Neste 
aso
podemos 
hamar a sequen
ia de passeio orientado, ou simplesmente passeio.
Quando a orientação das arestas não 
oin
ide, dizemos que a sequên
ia é um
semi-passeio.
■ De forma similar de�nimos semi-trajetos, semi-
aminhos e semi-
ir
uitos.
Digrafos Conexos
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 16
De�nição 2. Um digrafo D(V,A) é fortemente 
onexo se existe um
aminho orientado de vi para vj e de vj para vi, quaisquer que sejam
vi, vj ∈ V .
Um digrafo D(V,A) é fra
amente 
onexo se o grafo asso
iado é 
onexo
mas D não é fortemente 
onexo.
G1 G2
Propriedades
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
Um digrafo é dito ser a
í
li
o se não possui 
ir
uitos.
■ Um digrafo é a
í
li
o se e somente se todo trajeto orientado é
também um 
aminho orientado.
■ Todo digrafo a
í
li
o possui pelo menos uma fonte e um sumidouro.
Exer
í
io: En
ontre exemplos que ilustrem as propriedades a
ima.
Grafos e Algoritmos
GrafosDire
ionados (Digrafos) Grafos e Algoritmos
Algoritmos e 
ontagem do número de Operações
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
■ Problemas de otimização e problemas 
omputa
ionais em geral são
resolvidos por meio de algoritmos.
■ De uma forma vaga, podemos dizer que um algoritmo é um 
onjunto
de �nito de instruções do tipo usado em linguagens de programação
tais 
omo: operações aritméti
as, instruções 
ondi
ionais, instruções
de leitura e es
rita.
■ O tempo de exe
ução de um algoritmo depende de vários fatores,
entre eles: boa práti
a de programação, 
odi�
ação das instruções
de forma inteligente, estrutura de dados, equipamento onde esta
sendo exe
utado.
■ Apesar da importân
ia destes fatores, estamos interessados em
avaliar a qualidade de um algoritmo independentemente da forma em
que está 
odi�
ado ou da máquina onde esta sendo exe
utado.
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
■ Uma maneira de avaliar o desempenho 
omputa
ional de um
algoritmo independentemente de uma implementação parti
ular é
al
ular aproximadamente o número de operações (aritméti
as,
ondi
ionais, et
) que o mesmo exe
uta.
■ Esta práti
a é em geral satisfatória, apesar de des
onsiderar que
operações 
om números inteiros de pou
os dígitos são menos
trabalhosas que operações envolvendo números reais de alta pre
isão,
ou números inteiros de muitos dígitos.
■ Um 
ál
ulo mais pre
iso 
onsidera também os dados do problema.
■ Neste 
urso, iremos 
onsiderar apenas os dados relativos à dimensão
do problema. Um tratamento mais detalhado sobre a avaliação do
desempenho 
omputa
ional de um algoritmo pode ser en
ontrado
em [1℄, [2℄ e [3℄.
Exemplo 1 - Produto Es
alar entre dois vetores
(Algoritmo 1)
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
Cal
ula o produto es
alar p entre os vetores v, w ∈ Rn.
iní
io
p = v(1) ∗ w(1)
Para i = 2 até n faça
p = p+ v(i) ∗ w(i)
�m
es
reva p
�m
Exemplo 2 - Produto de duas matrizes
(Algoritmo 2)
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
Cal
ula o produto C de duas matrizes A ∈ Rm×n, B ∈ Rn×p.
iní
io
para i = 1 até m faça
para j = 1 até p faça
c(i, j) = a(i, 1) ∗ b(1, j)
para k = 2 até n
c(i, j) = c(i, j) + a(i, k) ∗ b(k, j)
�m
�m
�m
�m
Contagem do número de operações
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 23
■ Note que no Algoritmo 1 temos n multipli
ações e n− 1 adições totalizando
2n− 1 operações.
■ O algoritmo 2 
al
ula os elementos c(i, j) da matriz C fazendo o produto es
alar
entre a linha i da matriz A e a 
oluna j da matriz B. Isto é, são 
al
ulado m ∗ p
produtos es
alares que por sua vez requerem 2n− 1 operações, totalizando
m ∗ p(2n− 1) operações.
■ Para os algoritmos 1 e 2 foi possível fazer a 
ontagem exata do número de
operações que 
ada um exe
uta. Porém, nem sempre a 
ontagem do número de
operações é trivial.
■ Pro
ura-se então fazer uma estimativa do 
res
imento do número de operações
em função dos parâmetros que de�nem o problema.
■ Assim, para o Algoritmo 1 é su�
iente dizer que o número de operações
exe
utadas é uma função linear de n, enquanto que o número de operações do
Algoritmo 2 é uma função 
úbi
a de n,m e p.
Contagem do número de operações
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 24
Para maior pre
isão na estimativa do número de operações é utilizada a
expressão �ordem de magnitude� de�nida a seguir.
De�nição 3. Sejam f, g : Rn+ → R+. Dizemos que:
a) f(n) é O(g(n)) (f é da ordem de g) se existirem 
onstantes c, n0
tais que f(n) ≤ cg(n) para n ≥ n0 (
omplexidade no pior 
aso).
b) f(n) é Ω(g(n)) (f é da ordem de g) se existirem 
onstantes c, n0
tais que f(n) ≥ cg(n) para n ≥ n0 (
omplexidade no melhor 
aso).
) f(n) é Θ(g(n)) se f(n) é O(g(n)) e f(n) é Ω(g(n)) (
omplexidade
exata).
Contagem do número de operações
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 25
Exemplos:
1. f(p) = 3p3 + 2p2 é da ordem de p3, ou simplesmente f é O(p3), pois para
p0 = 0 e c = 5, temos 3p
3 + 2p2 ≤ 5p3.
2. f(p) = (p+ 1)2 é da ordem de O(p2). Neste 
aso, para p0 = 1 e c = 4, temos
(p+ 1)2 ≤ 4p2.
3. f(p) = 542 é O(1).
4. Observe que 
om esta de�nição as funções f(x) = 1010n3 + n2 e g(x) = n3 + n2
possuem 
omplexidade O(n3).
Exer
í
io: Veri�
ar que:
a) f(p) = 3p3 + 2p2 + 10 é Θ(n3).
b) f(n) = n logn é O(n2) e Ω(n).
Como avaliar se a 
omplexidade de um dado
algoritmo é boa ou ruim?
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 26
Suponha que possamos es
olher entre dois algoritmos, A e B. O tempo
de exe
ução do algoritmo A é 10n/100, isto é O(10n) (exponen
ial) e do
algoritmo B é 10n3, isto é O(n3) (polinomial).
Para valores bem pequenos de n, por exemplo n = 3, o algoritmo A é
mais e�
iente que o algoritmo B. Veja a tabela abaixo:
n 10n/100 10n3
3 10 90
4 100 640
5 1000 1250
6 10000 2160
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 27
Mas o que a
onte
e para valores maiores de n?
Suponha que dispomos de uma máquina 
apaz de exe
utar 107
operações aritméti
a por segundo, e que estamos dispostos a exe
utar os
dois algoritmos por 1000 segundos.
Qual é a dimensão dos problemas que poderíamos resolver 
om 
ada um
dos algoritmos dentro deste intervalo de tempo?
Se a máquina exe
uta 107 operações por segundo, o algoritmo A,
exe
utado nesta máquina pode realizar quantas operações em 1000
segundos?
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 28
Uma simples regra de três:
1 s ←→ 107
1000 s ←→ 10n/100
nos leva a seguinte equação:
10n
100
= 107 ∗ 1000⇒ n = 12.
Isto é, neste tempo o algoritmo A resolve problemas 
om n ≤ 12.
Fazendo um ra
io
ínio similar para o algoritmo B, temos que este resolve
problemas 
om n ≤ 1000.
Estes 
ál
ulos indi
am que algoritmos polinomiais permitem a resolução
de problemas maiores dentro de um mesmo intervalo de tempo.
Grafos Dire
ionados (Digrafos) Grafos e Algoritmos
Teoria dos Grafos (Antunes Rangel&Araujo) � 29
■ De uma maneira geral algoritmos 
om 
omplexidade 
omputa
ional polinomial
são 
onsiderados rápidos e e�
ientes enquanto que os algoritmos 
om
omplexidade exponen
ial são vistos 
omo lentos e ine�
ientes.
■ Este ponto de vista se justi�
a em muitas, mas não todas, situações.
■ A otimização linear é um exemplo onde algoritmos exponen
iais (baseados no
método simplex) e algoritmos polinomiais (métodos de ponto interior) 
ompetem
em pé de igualdade.
■ O estudo de 
omplexidade de algoritmos será útil para determinamos o grau de
di�
uldade de resolução de problemas em Grafos.
■ Em geral as medidas de 
omplexidade são feitas em função da dimensão do
problema.
■ No 
aso de grafos em função do número de vérti
es, n, e do número de arestas,
m.
	Grafos Direcionados (Digrafos)
	
	
	
	
	
	
	
	
	
	Tipos de digrafos
	Tipos de digrafos (cont.)
	Exercícios
	Caminhos Orientados
	Digrafos Conexos
	Propriedades
	Grafos e Algoritmos
	Algoritmos e contagem do número de Operações
	
	Exemplo 1 - Produto Escalar entre dois vetores (Algoritmo 1)
	Exemplo 2 - Produto de duas matrizes (Algoritmo 2)
	Contagem do número deoperações
	Contagem do número de operações
	Contagem do número de operações
	Como avaliar se a complexidade de um dado algoritmo é boa ou ruim?