677186_Unidade 1 - dígrafos

Prévia do material em texto

1
Grafos Dirigidos
ou Dígrafos (1)
Pontifícia Universidade Católica de Minas Gerais
Prof. Pasteur Jr e Prof. Max do Val 
Machado
1 Conjunto de transparências baseado no material da Profa. Raquel Mini
2
Dígrafos
• São grafos nos quais as arestas são 
pares ordenados de vértices
• Definições:
– vértice inicial de uma aresta
– vértice final de uma aresta
– grau de entrada de um vértice 
– grau de saída de um vértice
( ) ( )∑∑ −
n
=i
i
n
=i
i
+ vd=vd
11
( )vd−
( )vd+
v1
v2
v5
v3
v4
3
Dígrafos
v1
v2
v5
v3
v4
Grafo 
Correspondente
v1
v2
v5
v3
v4
4
Dígrafos – Definições
• Um vértice pendente é aquele que 
possui grau 1
• Arestas paralelas devem possuir a 
mesma direção
• Isomorfismo de dígrafos: a direção das 
arestas deve ser a mesma
( ) ( ) 1=vd+vd + −
G1 G2
G1 e G2 não são isomorfos
5
Dígrafos – Definições
• Dígrafos simples: não possui loops e 
nem arestas paralelas
• Dígrafo simétrico: para toda aresta 
(vi,vj) existe uma aresta (vj,vi)
• Digrafo completo:
Simétrico Assimétrico
6
• Dígrafo balanceado: para todo vértice 
v tem-se:
• Um dígrafo balanceado é regular se 
todos os vértices possuem o mesmo 
grau de entrada e saída
• Caminho dirigido: segue a orientação 
das arestas
• Semi-caminho: é um caminho no grafo 
correspondente mas não é no dígrafo
• Caminho simples dirigido e Semi-
caminho simples
• Circuito dirigido e Semi-circuito
( ) ( )vd=vd + −
Dígrafos – Definições
7
• Dígrafo fortemente conexo: existe um 
caminho dirigido entre todos os pares 
de vértices
• Dígrafo fracamente conexo: dígrafo 
não é fortemente conexo, mas seu 
grafo correspondente é conexo
Dígrafos – Definições
Obs.: Se falarmos que um dígrafo é conexo 
simplesmente significa que seu grafo 
correspondente é conexo
8
Dígrafos Eulerianos
• Dígrafos Eulerianos: possuem um 
caminho fechado dirigido que passa por 
todas as arestas exatamente uma vez
• TEOREMA: Um dígrafo é euleriano se, e 
somente se, ele for fortemente conexo e 
balanceado
( ) ( ) Vvvd=vd + ∈∀−
a
b
c
d
e
f