Teoria dos Grafos - Parte 2 - Representacao Computacional

Prévia do material em texto

Teoria dos Grafos 
 
Representação Computacional 
Prof. Rômulo Alencar 
romulo.alencar@unifor.br 
Prof. Rômulo Alencar Teoria dos Grafos 2 
Considerações 
 
 
 Estes slides foram elaborados com base no material 
de professores anteriores da disciplina, especialmente os 
Profs. Maikol Rodrigues, Tibérius Bonates e André Coelho, 
e nos livros indicados na bibliografia da disciplina, com 
foco principal no livro “Algoritmos – Teoria e Prática” de 
Cormen et al. 
Prof. Rômulo Alencar 
romulo.alencar@unifor.br 
Prof. Rômulo Alencar Teoria dos Grafos 3 
Conteúdo 
  Conceitos Básicos 
  Representação Computacional 
  Busca em Grafos 
  Ordenação Topológica 
  Conexidade 
  Fecho Transitivo 
  Árvores Geradoras Mínimas 
  Caminhos Mínimos 
  Fluxo em Redes 
Prof. Rômulo Alencar Teoria dos Grafos 4 
Adjacência 
  Em um grafo simples, dois vértices u e v são adjacentes 
(ou vizinhos) se há uma aresta {u, v} ou arco (u, v) em G 
  Esta aresta/arco é dita incidente a ambos, v e u 
Prof. Rômulo Alencar Teoria dos Grafos 5 
Grafo Regular 
  Um grafo é regular quando todos os seus vértices têm o 
mesmo grau 
  O grafo abaixo, por exemplo, é um grafo regular-3, pois 
todos os seus vértices têm grau 3 
5 
Prof. Rômulo Alencar Teoria dos Grafos 6 
Grafo Completo 
  Um grafo é completo quando há uma aresta entre cada 
par de seus vértices 
  Estes grafos são designados por Kn, onde n é a ordem 
do grafo 
  Um grafo Kn possui o número máximo possível de 
arestas para um dado n. Fórmula? 
  Ele é também regular-(n-1) pois todos os seus vértices 
tem grau n-1 
6 
Prof. Rômulo Alencar Teoria dos Grafos 7 
Grafo Conexo 
  Um grafo é conexo se há pelo menos uma “cadeia” 
ligando cada par de vértices deste grafo. Caso contrário, 
o grafo é desconexo. 
7 
Prof. Rômulo Alencar Teoria dos Grafos 8 
Componente Conexa 
  Um grafo desconexo G é formado por pelo menos dois 
subgrafos conexos, disjuntos e maximais em relação aos 
vértices 
  Cada um destes subgrafos conexos é uma componente 
conexa de G 
8 
Prof. Rômulo Alencar Teoria dos Grafos 9 
Grafo Fortemente Conexo 
  Um grafo orientado é fortemente conexo (f-conexo) se 
todo par de vértices está ligado por pelo menos um 
caminho em cada sentido 
  Ou seja, cada vértice é alcançável de qualquer outro 
vértice do grafo 
9 
Prof. Rômulo Alencar Teoria dos Grafos 10 
Componente Fortemente Conexa 
  Um grafo orientado G que 
não é fortemente conexo é 
formado por pelo menos 
dois subgrafos fortemente 
conexos, disjuntos e 
maximais em relação aos 
vértices 
  Cada um destes subgrafos 
é uma componente 
fortemente conexa de G 
10 
Prof. Rômulo Alencar Teoria dos Grafos 11 
Árvore 
  Se G é um grafo de ordem n > 2, as propriedades 
seguintes são equivalentes para caracterizar G como 
uma árvore 
 G é conexo e sem ciclos 
 G é sem ciclos e tem n-1 arestas 
 G é conexo e tem n-1 arestas 
 G é sem ciclos e, por adição de uma aresta, cria-se um 
único ciclo 
 G é conexo, mas deixa de sê-lo se uma aresta é suprimida 
 Todo par de vértices de G é unido por uma única 
sequência de arestas 
11 
Prof. Rômulo Alencar Teoria dos Grafos 12 
Representação Computacional 
  Matriz de Adjacência; 
  Lista de Adjacência; 
  Matriz de Incidência; 
  Lista de Incidência; 
  Lista de Arestas. 
12 
Prof. Rômulo Alencar Teoria dos Grafos 13 
Matriz de Adjacência 
  A mais simples e mais popular representação de grafos 
  Dado um grafo G=(V, E), a matriz de adjacência A é 
tal que 
 aij = 1, se (i, j) ∈ E 
 aij = 0, caso contrário 
  Complexidade de espaço: O(V2)‏ 
13 
1 
0 
0 
1 
0 
0 
6 
0 0 0 0 0 6 
0 1 0 0 0 5 
0 0 0 1 0 4 
1 0 0 0 0 3 
1 0 0 0 0 2 
0 1 0 1 0 1 
5 4 3 2 1 
1 2 
5 
3 
4 6 
Prof. Rômulo Alencar Teoria dos Grafos 14 
Matriz de Adjacência 
  Observe a simetria com relação à diagonal principal… 
  Isso acontece em um grafo não-orientado, pois (u, v) e 
(v, u) representam a mesma aresta {u, v}; 
  Para grafos com muitos nós, armazena-se apenas as 
entradas contidas na diagonal principal e acima 
14 
1 2 
4 
3 
5 0 1 0 1 1 5 
1 0 1 1 0 4 
0 1 0 1 0 3 
1 1 1 0 1 2 
1 0 0 1 0 1 
5 4 3 2 1 
Prof. Rômulo Alencar Teoria dos Grafos 15 
Matriz de Adjacência 
  Se o grafo G=(V,E) é não-orientado, a soma dos 
elementos da matriz é 2|E| 
  Se o grafo G=(V,E) é orientado, a matriz deixa de ser 
simétrica e a soma dos elementos da matriz é |E| 
15 
1 
0 
0 
1 
0 
0 
6 
0 0 0 0 0 6 
0 1 0 0 0 5 
0 0 0 1 0 4 
1 0 0 0 0 3 
1 0 0 0 0 2 
0 1 0 1 0 1 
5 4 3 2 1 
1 2 
5 
3 
4 6 
Prof. Rômulo Alencar Teoria dos Grafos 16 
Matriz de Adjacência 
  No caso de grafos ponderados, a matriz pode conter os 
pesos das arestas 
  Se uma aresta não existe, geralmente a entrada na 
matriz é armazenada como 0 ou um valor muito grande 
16 
0 
inf 
15 
19 
inf 
inf 
inf 
7 
18 inf inf inf inf inf 7 
0 
inf 
12 
17 
inf 
inf 
6 
inf inf inf inf inf 6 
0 10 inf inf inf 5 
inf 0 16 inf inf 4 
inf inf 0 inf inf 3 
14 11 inf 0 inf 2 
inf 13 15 10 0 1 
5 4 3 2 1 
10 1 2 
3 4 5 
6 7 
12 
18 
10 
14 
15 17 19 
15 
16 
13 11 
Prof. Rômulo Alencar Teoria dos Grafos 17 
Lista de Adjacência 
  Dado um grafo G=(V,E), a lista de adjacência consiste 
em um grupo de |V| listas, uma para cada vértice v 
  A lista de um nó v contém os vértices adjacentes a v 
  Complexidade de espaço: O(V+E)‏ 
  Os vértices em cada lista são mantidos em uma ordem 
arbitrária 
17 
1 2 
4 
3 
5 
2 nil 5
2 5 nil 3 
1 5 3
2 nil 4
4 1
4 nil 
1 
 
2 
 
3 
 
4 
 
5 
nil 2
Prof. Rômulo Alencar Teoria dos Grafos 18 
Lista de Adjacência 
  Se o grafo G=(V,E) é orientado, a soma dos 
comprimentos de todas as listas de adjacências é |E| 
  Se o grafo G=(V,E) é não orientado, a soma dos 
comprimentos de todas as listas de adjacências é 2|E| 
18 
2 nil 4 
 nil 2 
5 
6 nil 5 
nil 4 
1 
 
2 
 
3 
 
4 
 
5 
 
6 
nil 
nil 6 
1 2 
5 
3 
4 6 
Prof. Rômulo Alencar Teoria dos Grafos 19 
Lista de Adjacência 
  Listas de adjacências podem ser facilmente adaptadas 
para representar grafos ponderados 
19 
10 1 2 
3 4 5 
6 7 
12 
18 
10 
14 
15 17 19 
15 
16 
13 11 
nil 
10 2 15 3 nil 13 4 
11 4 nil 14 5 
nil 18 6 
11 4 nil 15 7 
nil 17 6 
16 3 12 6 nil 19 7 
1 
 
2 
 
3 
 
4 
 
5 
 
6 
 
7 
Prof. Rômulo Alencar Teoria dos Grafos 20 
Lista de Adjacência 
  Dependendo das características do grafo e dos 
algoritmos a serem executados, estruturas de dados 
baseadas em arranjos e/ou ponteiros podem ser 
utilizadas 
 Ponteiros: maior flexibilidade para inserir/remover arestas 
 Arranjos: melhor tempo de acesso 
 Por exemplo, na figura abaixo, a lista de adjacências do 
vértice i está contida entre as posições α(i) e α(i+1)-1 do 
arranjo β 
20 
Prof. Rômulo Alencar Teoria dos Grafos 21 
Matriz de Adjacência X Lista de Adjacência 
  Dado um grafo G=(V,E): 
21 
Procurar por v na lista de 
adjacências de u 
Verificar au,v (u,v) ∈ G ? 
Grafos esparsos 
(E é muito menor que V 2) 
Grafos densos 
(E está próximo de V 2) 
Ideal para... 
O(V + E) 
Grafo orientado ou não 
O(V 2) 
Independente de E 
Memória utilizada 
 
LA MA 
Prof. Rômulo Alencar Teoria dos Grafos 22 
Matriz de Incidência 
  Dado um grafo G=(V,E), a matriz de incidências 
B|V|,|E| é tal que 
 bij = 1, se vi ∈ ej 
 bij = 0, caso contrário 
  Complexidade de espaço: O(VE)‏ 
  É uma matriz esparsa por natureza, mas tem utilidade 
para alguns problemas específicos 
22 
1 2 
4 
3 
5 
e1 e2 
e3 
e7 e6 
e4 
e5 
1 1 0 0 0 5 
0 1 1 0 0 4 
0 0 1 1 0 3 
0 0 0 1 1 2 
1 0 0 0 1 1 
5 4 3 2 1 
1 
0 
0 
1 
0 
6 
0 
1 
0 
1 
0 
7 
Prof. Rômulo Alencar Teoria dos Grafos 23 
Matriz de Incidência 
  Para um grafo não-orientado G=(V,E), a soma dos 
elementos da matriz é 2|E| 
  Se o grafo é orientado, a representação abaixo pode ser 
utilizada (soma dos elementos é 0)‏ 
23 
1 2 
4 
3 
5 
e1 e2 
e3 
e7 e6 
e4 
e5-1 -1 0 0 0 5 
0 1 -1 0 0 4 
0 0 1 -1 0 3 
0 0 0 1 1 2 
1 0 0 0 -1 1 
5 4 3 2 1 
-1 
0 
0 
1 
0 
6 
0 
-1 
0 
1 
0 
7 
Prof. Rômulo Alencar Teoria dos Grafos 24 
Lista de Incidência 
  Dado um grafo G=(V,E), a lista de incidências consiste 
em um grupo de |E| itens, um para cada aresta e, 
referenciando os vértices que são incidentes a e 
  Complexidade de espaço: O(V+E)‏ 
24 
1 2 
4 
3 
5 
e1 e2 
e3 
e7 e6 
e4 
e5 
1 
2 
3 
4 
5 
6 
7 
1 
2 
3 
4 
5 
Prof. Rômulo Alencar Teoria dos Grafos 25 
Lista de Arestas 
  Objeto Vértice 
 elemento 
 Referência para posição em 
uma sequência de vértices 
  Objeto Aresta 
 elemento 
 Objeto do vértice origem 
 Objeto do vértice destino 
 Referência para uma posição 
em uma seqüência de arestas 
  Sequência de vértices 
  Sequência de arestas 
25 
v 
u 
w 
a c 
b 
a 
z 
d 
u v w z 
b c d 
Prof. Rômulo Alencar Teoria dos Grafos 26 
Exercício 
  Dê a matriz de adjacência, a lista de adjacência e a 
matriz de incidência dos grafos abaixo 
26 
f 
a 
b
c 
d
e 
g
h i 
j 
Prof. Rômulo Alencar Teoria dos Grafos 27 
Exercício 
  Desenhe os grafos armazenados nas estruturas de 
dados abaixo: 
27 
Prof. Rômulo Alencar Teoria dos Grafos 28 
Exercício 
  Dada a matriz de adjacência a seguir, desenhe o grafo 
correspondente. Em seguida, mostre a representação de 
lista de adjacência e matriz de incidência. 
28 
Prof. Rômulo Alencar Teoria dos Grafos 29 
Exercício 
  Dado o digrafo ponderado abaixo, determine a matriz de 
incidência e a lista de adjacência. Forneça estruturas de 
dados baseadas em ponteiros e em arranjos para a lista 
de adjacências. 
29