Grafos Orientados
(digrafos)
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Grafo Orientado ou digrafo
• Consiste em um grafo G = (V,A) onde V =
{v1, …, vn} é um conjunto de vértices e A =
{a1, …, ak} é um conjunto de arcos tais que
ak, k=1,…,m é representado por um par
ordenado (vi,vj) de vértices, i,j = 1,…,n.
c
e
f
d
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Lista de adjacência
2
1
4
3
1
2
2
4
1
3
5
2010/1
1
3
2
•
2
1
4
3
2
1
•
4
1
•
4
2
•
2
3
•
4
5
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Matriz de Adjacência
• Seja G = (V,A)
• A = (aij), 1 ≤ i,j ≤ n
• aij = 1, quando (i,j) ∈ A
0, caso contrário
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Matriz de Adjacência
a
c
d
e
2010/1
b
c
d
0
1
1
0
1
c
0
0
0
0
0
d
0
1
0
1
0
0
1
0
0
0
0
0
1
0
0
a
b
e
a
b
e
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Matriz de Adjacência
• Diagonal principal nula: grafos sem laços
• Matriz não necessariamente simétrica.
• Valores nulos: ausência de arestas
• Valores não nulos: presença de arcos
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Matriz de Incidência
• Seja G = (V,E)
• B = (bkl), 1 ≤ k ≤ n, 1 ≤ l ≤ m
• bkl = 1, quando o vértice k é extremidade inicial
do arco l
-1, quando o vértice k é extremidade final
do arco l
0, caso contrário
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Matriz de Incidência
(a,b) (a,c) (a,e) (c,b) (c,d) (d,b) (e,c)
a
c
b
d
e
2010/1
a
+1 +1 +1 0
0
0
0
b
-1
0
0
0
-1
0
c
0
-1
0 +1 +1 0
-1
d
0
0
0
0
-1 +1 0
e
0
0
-1
0
0
Teoria dos Grafos
(INF 5037/INF2781)
-1
0 +1
CC/EC/PPGI/UFES
Relações de adjacência
• Em um digrafo G = (X, U), diz-se que y ∈
X é sucessor de x ∈ X quando existe (x,y)
∈ U. Diz-se também que x é antecessor
de y.
– Γ+ (x): conjunto de sucessores de x
– Γ- (x): conjunto de antecessores de x
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Vizinhança
• Vizinho ou vértice adjacente de um vértice
x, em um grafo orientado ou não, é todo
vértice y que participa de uma ligação
(arco ou aresta) com x.
x
Γ+ (x)
x
Γ - (x)
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Vizinhança
• Seja A ⊂ X. Então Γ+ (A) = U Γ+ (x) , x ∈ A
a
A
c
b
d
e
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
Idem para
Γ- (A)!
CC/EC/PPGI/UFES
Fechos Transitivos
• Conjuntos que representam ligações
diretas ou indiretas entre vértices em
grafos orientados.
• Diz-se que um vértice y é atingível a partir
de x em um grafo G quando existe em G
uma seqüência de sucessores que
começa em x e termina em y.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Fecho Transitivo Direto
• Γ^ + (x): conjunto de vértices de G atingíveis
a partir de x
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Fecho Transitivo inverso
• Γ^ - (x): conjunto de vértices de G a partir
dos quais x é atingível
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Incidência de um vértice
• Um arco incide exteriormente em x ∈ X se x for
extremidade inicial e interiormente se x for
extremidade final do arco.
• O arco (i,j) é incidente em A ⊂ X de um grafo G,
se ele tem uma e só uma extremidade em um
vértice pertencente a A.
• (i,j) é incidente a A: interiormente (i ∉ A, j ∈ A)
exteriormente (i ∈ A, j ∉ A)
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Grau de um vértice
• Semigrau exterior (d+(x)): número de
arcos incidentes exteriormente a x
• Semigrau interior (d-(x)): número de arcos
incidentes interiormente a x
• d(x) = d+(x) + d-(x)
• Vértice nulo: d+(x) = d-(x) = 0
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Isomorfismo
• Seja G um digrafo e G´ o grafo
correspondente sem orientações.
• Seja G´ um grafo não orientado. Então G,
obtido a partir de G´ definindo-se uma
orientação arbitrária de suas arestas é dito
digrafo associado a G.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Isomorfismo
• Se G é um digrafo e G´ é um grafo não
orientado obtido a partir de G: único.
• Se G é um grafo não orientado e G´ é
orientado, obtido a partir de G: várias
possibilidades.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Isomorfismo
• Quando dois digrafos G1 e G2 são
isomorfos?
– Os grafos não orientados G1´ e G2´
correspondentes a G1 e G2 devem ser
isomorfos.
– As orientações entre as arestas
correspondentes devem ser as mesmas.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Alguns tipos de digrafos
• Simples: sem laços ou arestas paralelas
• Assimétrico: possui no máximo um arco entre
cada par de vértices
• Simétrico: para cada par de vértices existe um
arco em cada direção
• Completo simétrico (n(n-1) arcos)
• Completo assimétrico (n(n-1)/2 arcos)
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Percursos
• Percurso simples direcionado de um vértice i
para um vértice j: é uma seqüência alternada de
vértices e arestas sucessivamente adjacentes.
Nenhuma aresta aparece mais de uma vez, mas
um vértice pode ser repetido.
• Caminho direcionado: percurso simples sem
repetição de vértices
• Circuito: ciclo orientado com todos os arcos na
mesma direção.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Conexidade
• Grafo simplesmente conexo ou s-conexo:
todo par de vértices é unido por ao menos
um caminho no grafo correspondente não
a
direcionado
c
b
d
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Conexidade
• Grafo semi-fortemente conexo ou sfconexo: em todo par de vértices do grafo,
um deles é atingível a partir do outro (ou
a
seja, entre eles existe
c
um caminho em ao
b
menos um dos dois
sentidos possíveis
d
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Conexidade
• Grafo fortemente conexo ou f-conexo: é um
grafo no qual todo par de vértices é mutuamente
atingível. Assim, a todo par de vértices está
associado um par de caminhos de sentidos
opostos
a
b
c
• Todo vértice é atingível a partir de um vértice
dado e todo vértice atinge todo vértice dado
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Níveis de Conexidade
s-conexo
sf-conexo
f-conexo
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Componentes f-conexas
• Atingibilidade recíproca: (simetria)
• Todo vértice é atingível a partir de si
mesmo: (reflexividade)
• Se z é atingível a partir de y e y é atingível
a partir de x então z é atingível a partir de
x: (transitividade)
relação de equivalência sobre o conjunto de vértices de G
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Componentes f-conexas
• Um grafo orientado qualquer pode ser
particionado em componentes f-conexas
maximais.
• Se um grafo orientado é f-conexo: a
partição é o próprio conjunto de vértices
do grafo.
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES
Árvores
• Uma árvore é um digrafo s-conexo sem
circuitos ou ciclos no grafo não orientado
associado
a
c
b
d
2010/1
Teoria dos Grafos
(INF 5037/INF2781)
CC/EC/PPGI/UFES