Digrafos - Teoria dos Grafos

Prévia do material em texto

digrafos – Teoria dos Grafos – Prof. Maria do Socorro Rangel – DCCE/UNESP -11/09/07 - 1 /3 
6 - Grafos Direcionados (Digrafos) 
 
 Até o momento trabalhamos com grafos tais que as arestas são pares não ordenados de 
vértices. Várias situações práticas requerem que associemos sentido às arestas do grafo. Pôr 
exemplo, considere um grafo representando as ruas de uma cidade. Nem todas as ruas são de mão 
dupla. Ao se estudar rotas de ônibus é necessário considerar se as ruas são de mão única, isto é 
permitem fluxo apenas no sentido (vi, vj) ou se são de mão dupla. Outras situações são: fluxograma 
de programas computacionais onde os vértices representam instruções e as arestas a seqüência de 
execução; redes elétricas; fluxos em redes que possuem válvulas nos encanamentos. 
 Quando associamos sentido às arestas do grafo temos um grafo direcionado ou digrafo. A 
maioria dos conceitos e terminologia usados para grafos não–orientados são também aplicáveis para 
digrafos. Pôr exemplo o conceito de planaridade independe do sentido associado às arestas. Vamos 
chamar atenção neste tópico apenas para as propriedades e conceitos que se aplicam apenas a 
digrafos. Vamos inicialmente definir formalmente o conceito de um grafo direcionado. 
 
Definição 1 – Um grafo direcionado G(V,A) é constituído pôr um conjunto V não-vazio de 
objetos, chamados vértices (ou nós), e um conjunto A de pares ordenados de elementos de V, 
chamados de arestas ou arcos. 
 
6.1 – Representação e conceitos iniciais 
 
Vamos considerar o seguinte digrafo: 
V = {v1, v2, v3, v4,v5} e A = {(v1,v2), (v1,v3), (v2,v4), (v3,v4), (v4,v5), (v1,v2), (v2,v2)} 
 
Os digrafos podem ser representados através de um diagrama onde os vértices são representados pôr 
pontos e cada aresta (vi,vj) é representada pôr uma linha ligando vi a vj com uma seta apontando 
para vj. 
 
 
 
 
 
 
 
 
 
 
Em digrafo, quando dizemos que uma aresta é incidente a um vértice que queremos saber em que 
sentido, isto é se a aresta é convergente ou divergente . 
 
Em relação ao grau de um vértice queremos também saber : 
 
Grau de entrada de(vi) – número de arestas convergentes e 
Grau de saída ds(vi) – número de arestas divergentes. 
 
∑ ∑= )()( vidsvide 
 
Temos uma fonte quando o grau de entrada é nulo e um sumidouro quando o grau de saída é nulo. 
 
Arestas paralelas – Duas arestas são paralelas se elas incidem nos mesmos vértices e possuem a 
mesma orientação. 
 
 v1 v2 
 
 v5 
 
 v3 
 v4 
digrafos – Teoria dos Grafos – Prof. Maria do Socorro Rangel – DCCE/UNESP -11/09/07 - 2 /3 
Muitas das propriedades de grafos não orientados são válidas para digrafos e portanto muitas vezes 
a orientação do grafo é desconsiderada. Podemos então definir: 
 
6.2 Grafo associado a um digrafo 
 
6.3 Orientação de um grafo 
 
6.4 Digrafos Isomorfos : os grafos associados são isomorfos e além disso a orientação das arestas 
deve coincidir. 
Verifique se os pares de digrafos abaixo (G1 e G2, G3 e G4 ) são isomorfos. 
 
G1: G2: 
 
 
 
 
 
 
 
G3: G4 
 
 
 
 
 
 
6.5 Tipos de digrafos 
 
Simples 
 
Simétrico – para cada aresta (vi, vj ), existe a aresta (vj, vi) 
 
Assimétrico – possui no máximo uma aresta entre cada par de vértices 
 
Completo – 
 simétrico – existe uma aresta orientada entre cada par de vértices 
 assimétrico – existe no máximo uma aresta entre cada par de vértices. 
 
Balanceado - )()(, vidsvideVvi =∈∀ 
 
 
 
6.6 Caminhos Orientados e conexidade – 
 
Definição 2 - Trajeto orientado - Dado um grafo G(V,A), um trajeto em G consiste de uma 
seqüência finita alternada de vértices e arestas, começando e terminando pôr vértices, tal que cada 
aresta aparece apenas uma vez e diverge do vértice que a precede e converge para o vértice que a 
sucede. 
Quando a orientação das arestas no trajeto não coincide dizemos que temos um semi-trajeto. 
digrafos – Teoria dos Grafos – Prof. Maria do Socorro Rangel – DCCE/UNESP -11/09/07 - 3 /3 
Exemplo 1: 
(trajeto onde há repetição de vértices) (trajeto onde não há repetição de vértices) 
 
semi-trajeto 
 
De maneira similar definimos: 
Caminho orientado, 
semi-caminho, 
trajeto orientado fechado, 
semi-trajeto fechado, 
circuito orientado, 
semi-circuito. 
 
Digrafos Conexos 
Um digrafo é fortemente conexo se existe um caminho orientado de vi para vj e de vj para vi, 
qualquer que seja vi, vj V∈ . 
Um digrafo D (V,A) é fracamente conexo se o grafo associado é conexo mas D não é fortemente 
conexo. 
 
 
 
 
 
 
 
 fortemente conexo fracamente conexo 
 
 
 
 
 
Propriedades: 
• Um digrafo é acíclico se não possui circuitos 
• Um digrafo é acíclico se e somente se todo trajeto orientado é também um caminho orientado. 
• Todo digrafo acíclico possui pelo menos uma fonte e um sumidouro. 
 
 
 
Exercício: Encontre exemplos que ilustrem as propriedades acima.