Operações e Representações de Grafos

Prévia do material em texto

2
Operações com Grafos
� União:
� Considere dois grafos G1=(V1,E1) e G2=(V2,E2) onde V1 e 
V2 são conjunto distintos, ou seja, V1∩∩∩∩ V2 = ∅∅∅∅.
� A união G1 ∪∪∪∪ G2 é formada pelo grafo com conjunto de 
vértices V1∪∪∪∪ V2 e o conjunto de arestas E1∪∪∪∪ E2.
� Exemplo:
� G: VG = {1, 2}; EG = {(1, 2)}
� H: VH = {3, 4}; EH = {}
� G ∪∪∪∪ H: VG ∪∪∪∪ H = {1, 2, 3, 4}; EG ∪∪∪∪ H = {(1, 2)}
3
Operações com Grafos
� Soma:
� Considere dois grafos G1=(V1,E1) e G2=(V2,E2) onde V1 e 
V2 são conjunto distintos , ou seja, V1∩∩∩∩ V2 = ∅∅∅∅.
� A soma G1 + G2 é formada por G1 ∪∪∪∪ G2 e pelas arestas 
ligando cada vértice de G1 a cada vértice de G2.
� Exemplo:
� G: VG = {1, 2}; EG = {(1, 2)}
� H: VH = {3, 4}; EH = {}
� G + H: 
� VG + H = {1, 2, 3, 4}; 
� EG + H = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)}
4
Operações com Grafos
� Exemplos
1 2
G H
3 4
G ∪ H G + H
1 2
3 4
1 2
3 4
5
Operações com Grafos
� União e soma:
� Podem ser aplicadas a qualquer número finito de 
grafos;
� São operações associativas;
� São operações comutativas.
6
Operações com Grafos
� Remoção de Aresta:
� Se e é uma aresta de um grafo G, denota-se G-e o 
grafo obtido pela remoção da aresta e de G.
� Genericamente, se F é um subconjunto de arestas em 
G, denota-se G-F ao grafo obtido pela remoção das 
arestas em F.
7
Operações com Grafos
� Remoção de vértice:
� Se v é um vértice de um grafo G, denota-se G-v o grafo 
obtido pela remoção do vértice v juntamente com as 
arestas incidentes a v.
� Genericamente, denota-se G-S ao grafo obtido pela 
remoção dos vértices em S, sendo S um subconjunto 
qualquer de vértices em G.
8
Operações com Grafos
� Contração de arestas:
� Denota-se G/e o grafo obtido pela contração da 
aresta e do grafo G.
� Isto significa remover e de G e unir suas duas 
extremidades v e w de tal forma que o vértice 
resultante seja incidente às arestas originalmente 
incidentes a v e w.
9
Representação de Grafos
� Embora seja conveniente a representação de 
grafos através de diagramas ligados por 
linhas, tal representação é inadequada se 
desejarmos armazenar grandes grafos em 
um computador.
10
Representação de Grafos
� Grafos podem ser implementados em um 
computador através de:
� Matriz de adjacência;
� Lista de adjacência;
� Matriz de incidência.
11
Matriz de Adjacência
� A matriz de adjacência M de um grafo G = (V, E)
contendo n vértices é uma matriz de n×n de bits, 
onde M[i, j] é 1 (ou verdadeiro) se e somente se 
existe um arco do vértice i para o vértice j.
� Para grafos ponderados, M[i, j] contém o rótulo ou 
peso associado à aresta e, neste caso, a matriz não 
é de bits.
� Se não existir uma aresta i para j, então é
necessário utilizar um valor que não possa ser 
usado como rótulo ou peso.
12
Matriz de Adjacência
13
Matriz de Adjacência
� Deve ser utilizada para grafos densos, onde |E| é 
próximo de |V|2.
� O tempo necessário para acessar um elemento é 
independente de |V| ou |E|.
� É muito útil para algoritmos em que necessitamos 
saber com rapidez se existe uma aresta ligando 
dois vértices.
� A maior desvantagem é que a matriz necessita 
 Ω(|V|2) de espaço. Ler ou examinar a matriz tem 
complexidade de tempo O(|V|2).
14
Lista de Adjacência
� Um arranjo adj de |V| listas, uma para cada 
vértice em V.
� Para cada u ∈ V, adj[u] contém todos os 
vértices adjacentes a u em G.
15
Lista de Adjacência
� Os vértices de uma lista de adjacência são em geral 
armazenados em uma ordem arbitrária.
� Possui uma complexidade de espaço O(|V| + |E|).
� Indicada para grafos esparsos, onde |E| é muito 
menor do que |V|2.
� É compacta e usualmente utilizada na maioria das 
aplicações
� A principal desvantagem é que ela pode ter tempo 
O(|V|) para determinar se existe uma aresta entre o 
vértice i e o vértice j, pois podem existir O(|V|)
vértices na lista de adjacentes do vértice i.
16
Matriz de Incidência
� Representação de matriz de um grafo baseada na 
incidência de vértices e de arestas.
� Uma matriz de incidência M do grafo G = (V, E) é 
uma matriz |V| ×××× |E| tal que
�
�
�
=
contráriocaso ,0
 v vérticeao incidente é e aresta a se ,1
],[
ij
jiM
17
Matriz de Incidência
18
Qual a melhor a 
representação?
Depende do problema