Aula-Representacao

Prévia do material em texto

Representações de Grafos 
Disciplina: Grafos e Algoritmos Computacionais 
Prof. Tarcisio Rocha 
Matriz de Adjacência 
� Definição 
� Seja G um grafo simples de n vértices v1, v2... vn. A matriz de 
adjacência é uma matriz n x n, onde o valor de cada elemento 
ejk da matriz é determinado da seguinte maneira: 
� ejk = 1, se os vértices vj e vk são ligados por uma aresta, senão 
� ejk = 0 
 v1 v2 v3 v4 v5 v6 
v1 
v2 
v3 
v4 
v5 
v6 
Matriz de Adjacência 
� Definição 
� Seja G um grafo simples de n vértices v1, v2... vn. A matriz de 
adjacência é uma matriz n x n, onde o valor de cada elemento 
ejk da matriz é determinado da seguinte maneira: 
� ejk = 1, se os vértices vj e vk são ligados por uma aresta, senão 
� ejk = 0 
 v1 v2 v3 v4 v5 v6 
v1 0 1 0 0 1 0 
v2 1 0 1 1 0 0 
v3 0 1 0 0 0 0 
v4 0 1 0 0 1 1 
v5 1 1 0 1 0 0 
v6 0 0 0 1 0 0 
Matriz de Adjacência 
� Arestas múltiplas? 
� Laços? 
Matriz de Adjacência 
� Arestas múltiplas 
� Podem ser representadas pelo valores que representam as 
adjacências (“0”: sem aresta; “1”: uma aresta; “2”: duas 
arestas...) 
� Laços 
� Um laço pode ser representado colocando um valor diferente de 
zero na diagonal da matriz 
 
Matriz de Adjacência 
� Dígrafo 
� Um elemento ejk da matriz terá o valor “1” se existe uma aresta 
de vj até vk 
v
 1 
v2 
v3 
v4 
v5 
v6 
v
 1 v2 v3 v4 v5 v6 
Matriz de Adjacência 
� Dígrafo 
� Um elemento ejk da matriz terá o valor “1” se existe uma aresta 
de vj até vk 
v
 1 0 1 1 1 0 0 
v2 0 0 0 0 0 1 
v3 0 0 1 0 0 0 
v4 0 1 0 0 0 0 
v5 0 0 0 1 0 0 
v6 0 0 0 0 1 0 
v
 1 v2 v3 v4 v5 v6 
Matriz de Adjacência 
� Arestas rotuladas? 
Matriz de Adjacência 
� Arestas rotuladas (ponderadas) 
� Podem ser representadas colocando o rótulo (valor ou peso) no 
lugar de “1”. 
Matriz de Adjacência 
� Arestas múltiplas rotuladas? 
� Uma solução é fazer com que cada elemento da matriz seja uma 
lista onde cada elemento indicaria o peso de uma aresta 
 
Matriz de Adjacência 
� Questões 
� Como saber se o grafo possui laços? 
� Qual a relação entre um grafo representado pela matriz M e a 
sua transposta MT ? 
� Como calcular o grau de um vértice? 
Matriz de Adjacência 
� Características 
� Para grafos sem laços, os elementos da diagonal da matriz é 
sempre “0”. 
� Matrizes de Adjacência são sempre simétricas 
� M = MT (a matriz é igual a sua transposta) 
� O número de valores diferentes de “0” de uma determinada linha 
ou coluna, indica o grau do vértice correspondente. 
 
Matriz de Adjacência 
� Grafos desconexos? 
Matriz de Adjacência 
� Características 
� Seja um grafo G desconexo que contém dois componentes g1 e 
g2. A matriz de adjacência M(G) pode ser escrita em função das 
duas matrizes de M(g1) e M(g2): 
M(g1) 0 
0 M(g2) 
Matriz de Adjacência 
� Questões 
� Qual a quantidade de memória necessária para armazenar um 
grafo G=(V, E) como uma matriz de adjacência? 
� Qual o problema de representar grafos esparsos como matrizes 
de adjacência? 
� Como reduzir a quantidade de memória necessária para 
armazenar um grafo como uma matriz de adjacência? 
 
 
Matriz de Adjacência 
� Problema 
� Em matrizes esparsas (que possuem o número de vértices bem 
maior que o número de arestas) pode ocorrer desperdício de 
memória. 
� A matriz de adjacência ocupa memória na ordem de Θ(|V|2), 
independentemente do seu número de arestas 
� Pode-se reduzir a memória exigida armazenando os elementos 
acima da diagonal ou abaixo da diagonal 
� Mesmo com esse problema, a matriz de adjacência é uma forma 
adequada de representação em casos onde: 
� Os grafos são razoavelmente pequenos 
� A simplicidade de representação é um requisito 
 
 
 
Lista de Adjacência 
� Definição 
� Seja G=(VG,AG) um grafo. A estrutura de adjacência J de G é 
um conjunto de n listas J(v), uma para cada vértice v de VG. 
Cada lista J(v) é denominada lista de adjacências de v e contém 
todos os vértices que são adjacentes a v. 
Lista de Adjacência 
� Arestas múltiplas? 
� Laços? 
Lista de Adjacência 
� Dígrafos? 
 
Lista de Adjacência 
� Dígrafos 
� Só aparece na lista de adjacência de um vértice v, os vértices 
para os quais as arestas que saem de v se dirigem. 
Lista de Adjacência 
Arestas rotuladas? 
Lista de Adjacência 
� Arestas rotuladas 
� Pode-se acrescentar informação de rótulo aos elementos da lista 
de adjacência.