Buscar

PAA-11-representacaoGrafosEConceitos

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 36 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 36 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 36 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Profa. Thaís Alves Burity Rocha 
GRAFOS 
Agenda 
 Representação computacional de grafos 
Matriz de adjacências 
 Lista de adjacências 
Matriz de incidência 
 Lista de incidências 
 
 Conjunto independente de vértices 
 
 Clique 
 
 
Exercício de revisão 1 
 Se G é um grafo k-regular com n vértices e a 
arestas, expresse a em função de n e k 
 
 
Exercício de revisão 1: Solução 
 A soma dos graus dos vértices de um grafo é igual 
a duas vezes o número de arestas 
 
 
 Em um grafo k-regular, todo vértice possui grau k 
 
 
 Daí: 
 
 
 
Revisão: Exercício 2 
 Qual o número de arestas de um grafo completo 
com 6 vértices? 
 
Exercício de revisão 2: Solução 
 Um grafo completo é regular 
 Logo, a fórmula se aplica 
 Cada vértice está conectado a todos os demais 
 Se há 6 vértices, cada vértice se conecta aos outros 5 
 Resultado: 
 a = (5 x 6)/2 = 5 x 3 = 15 
Representação de grafos 
 Representação gráfica 
 Útil na prática 
 Computacionalmente não é adequada 
 
 Formas de representação computacional 
Matriz de adjacências 
 Lista de adjacências 
Matriz de incidências 
 Lista de incidências 
Matriz de adjacências 
 Dado um grafo G = (V, E) 
 
 Requer que os vértices sejam numerados arbitrariamente de 
1, 2, …, |V| 
 
 Matriz A = (aij) de ordem |V|×|V| 
 aij = 1, se (i,j) є E 
 aij = 0, caso contrário 
 
 Válido também para grafos ponderados 
 Ao invés de 1, é atribuído o peso da conexão entre os vértices 
Matriz de adjacências 
 A matriz de adjacências pode ser representada por um 
vetor n x n, que denotaremos por A, onde: 
 A[i][j]=1, se a aresta está presente no grafo 
 Ou A[i][j]=0, caso contrário 
 
 Uso: Adequada para representar grafos densos, em que 
|E| é próximo de |V|2 
 
 Vantagem: Tempo constante (O(1)) para verificar se uma 
aresta está presente ou não no grafo 
 
 Desvantagem: Consumo de memória de Θ(V2), no geral 
 Se o grafo não for ponderado, A = At, sendo possível armazenar 
somente as entradas na diagonal principal e acima dela 
Matriz de adjacências: Exemplo 1 
1 
5 4 
2 
3 
1 2 3 4 5 
1 0 1 0 0 1 
2 1 0 1 1 1 
3 0 1 0 1 0 
4 0 1 1 0 1 
5 1 1 0 1 0 
Matriz de adjacências: Exemplo 2 
1 
5 
4 
2 3 
6 
1 2 3 4 5 6 
1 0 1 1 1 0 1 
2 1 0 0 0 0 0 
3 1 0 0 1 1 1 
4 1 0 1 0 1 1 
5 0 0 1 1 0 0 
6 1 0 1 1 0 0 
Lista de adjacências 
 Consiste de um vetor Adj de |V| listas, uma para cada 
vértice em V 
 
 Para cada u em V, Adj[u] consiste de todos os vértices de G 
adjacentes a u 
 
 Vértices armazenados de forma arbitrária na lista 
 
 Também pode ser utilizada no caso de grafos ponderados 
 O peso da aresta é armazenado junto com o vértice na lista de 
adjacências 
Lista de adjacências: Exemplo 1 
1 
5 4 
2 
3 
1 2 5 
2 1 5 3 4 
3 2 4 
4 2 5 3 
5 4 1 2 
listas vetor 
Lista de adjacências: Exemplo 2 
BSB 
Sal 
Rio 
Man Rec 
Sao 
Sao 
Rec Rio 
BSB 
Man 
Rec 
Rio 
Sal 
Sao 
Rec Man 
BSB 
Sal Rio 
Sao Rio 
Sal BSB 
Rec BSB Rio 
BSB Sao 
Rec 
Lista de adjacências 
 Tempo O(grau(i)) para verificar a pertinência de uma 
aresta ao grafo 
 grau(i) é o grau do vértice i e, consequentemente, o 
tamanho da lista de adjacências de i 
 
 Pior caso: quando grau(i) = |V|-1 
 
 Vantagem: Fornece um modo compacto de representar 
grafos esparsos, aqueles para os quais |E| é muito 
menor que |V|2 
 Quantidade de memória consumida é Θ(V+E) 
 
 
Lista de adjacências: Representação 
por matrizes 
 Uma linha para cada vértice 
 Cada linha possui um vetor, denotado por A 
 A quantidade de colunas corresponde a maxG 
maxG é o maior grau entre os vértices do grafo 
 
 Para descobrir se existe aresta (i,j) percorremos o 
vetor A[i] até encontrarmos j ou -1 
 
 Tamanho (custo espacial): |V| × maxG 
Lista de adjacências: Representação 
por matrizes 
 Exemplo 
 maxG = 3 
2 
1 
3 
0 
4 
(i) 0 1 2 
0 1 -1 -1 
1 0 2 3 
2 1 4 -1 
3 1 4 -1 
4 2 3 -1 
Matriz X listas de adjacências 
 
 
 
 
 
 
 
 
Testar se aresta está no grafo Matriz de adjacências 
Determinar o grau de um vértice Listas de adjacências 
Menos memória Listas de adjacências 
Inserção ou remoção de aresta Matriz de adjacências 
Atravessar o grafo Listas de adjacências 
Melhor na maioria dos problemas Listas de adjacências 
Matriz X listas de adjacências 
 Conclusão: 
Matrizes são melhores para busca, mas consomem mais 
memória 
 
 Listas são melhores para armazenamento, pois 
consomem menos memória, mas a busca consiste em, 
dada a aresta (u,v), procurar v na lista Adj[u] 
 
 Em se tratando de grafos pequenos, a lista é 
assintoticamente tão eficiente quanto a matriz, mas a 
simplicidade dessa última pode torná-la preferível 
Matriz de incidências 
 Matriz B = (bij), de ordem |V|x|E| 
 bij = 1, se vértice vi e aresta ej forem incidentes 
 bij = 0, caso contrário 
 
 Uma linha para cada vértice 
 
 Uma coluna para cada aresta 
 
Matriz de incidências: Exemplo 1 
1 
5 4 
2 
3 
e2 
e1 e3 e5 
e6 
e7 
e4 
1 2 3 4 5 6 7 
1 1 1 0 0 0 0 0 
2 0 1 1 0 1 1 0 
3 0 0 0 0 0 1 1 
4 0 0 0 1 1 0 1 
5 1 0 1 1 0 0 0 
Exercício 1 
 Observe o grafo e informe 
 A matriz de adjacências 
 
 A matriz de incidências 
 
 A lista de adjacências 
1 2 
3 
4 
5 
6 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
Exercício 1: Solução 
 Matriz de adjacências 
1 2 3 4 5 6 
1 0 1 0 0 0 1 
2 0 0 1 0 0 1 
3 0 0 0 1 0 0 
4 0 0 1 0 0 0 
5 0 1 0 1 0 0 
6 1 0 1 0 1 0 
1 2 
3 
4 
5 
6 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
Exercício 1: Solução 
 Matriz de incidências 
1 2 3 4 5 6 7 8 9 10 11 
1 1 1 -1 0 0 0 0 0 0 0 0 
2 -1 0 0 0 1 0 1 -1 0 0 0 
3 0 0 0 -1 0 0 -1 0 0 1 -1 
4 0 0 0 0 0 0 0 0 -1 -1 1 
5 0 0 0 0 0 -1 0 1 1 0 0 
6 0 -1 1 1 -1 1 0 0 0 0 0 
1 2 
3 
4 
5 
6 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
Exercício 1: Solução 
 Lista de adjacências 
1 2 6 
2 3 6 
3 4 
4 3 
5 2 4 
6 1 3 5 
0 1 2 
1 2 6 -1 
2 3 6 -1 
3 4 -1 -1 
4 3 -1 -1 
5 2 4 -1 
6 1 3 5 
1 2 
3 
4 
5 
6 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
a 
d 
f 
b 
c 
e 
g 
VIND de G 
a 
d 
f 
b 
c 
e 
g 
Grafo G 
Conjunto independente de vértices 
 Seja um grafo G=(V, E) 
 Um conjunto independente de vértices VIND de G é um 
subconjunto de V em que não existe nenhuma aresta 
entre pares de vértices de VIND 
Conjunto independente de vértices 
 Um grafo pode ter vários conjuntos independentes 
distintos 
 
 VIND é máximo se todos os outros conjuntos 
independentes possuem cardinalidade menor ou igual 
 
 VIND é maximal se não estiver contido em nenhum 
outro conjunto independente 
Conjunto independente de vértices 
 O conjunto independente VIND a seguir é 
maximal e máximo 
 
a 
d 
f 
b 
c 
e 
g 
a 
d 
f 
b 
c 
e 
g 
VIND V’IND 
Exercício 2 
 Encontre no grafo a seguir um conjunto 
independente maximal que não é máximo. Qual a 
cardinalidade do conjunto independente máximo? 
a d 
f 
b c 
e g h 
Exercício 2: Solução Conjunto independente maximal que não é máximo 
 
a d 
f 
b c 
e g h 
Exercício 2: Solução 
 A cardinalidade do conjunto independente máximo 
é 3 
a d 
f 
b c 
e g h 
VIND máximo: Aplicação 
 Seja um grafo cujos vértices representam projetos que 
podem ser executados em uma unidade de tempo 
 
 Todo projeto que utiliza recursos comuns a um outro 
projeto são interligados por uma aresta 
 
 O conjunto independente máximo representa o conjunto 
máximo de projetos que podem ser executados 
simultaneamente em um único período de tempo 
VIND máximo: Aplicação 
 Suponhamos que você queira realizar uma reunião 
envolvendo o maior número possível de pessoas do seu 
círculo de amizades que não se conhecem 
 
 Dentre as pessoas que poderiam ser convidadas, você 
traça um grafo contendo uma aresta ligando duas 
pessoas que se conhecem 
 
 O conjunto independente máximo representa o maior 
conjunto de pessoas que não se conhecem 
 
Clique 
 Seja um grafo G = (V, E) 
 Um clique VCLQ de G é um subconjunto de V em que, 
para quaisquer dois vértices u, v ∈ VCLQ, a aresta (u, 
v) ∈ E 
 Idéia “contrária” ao conceito de conjunto 
independente 
Grafo G 
a d 
f 
b 
c 
e 
g 
VCLQ de G 
a d 
f 
b 
c 
e 
g 
Clique: Aplicação 
 Considere uma rede social onde os vértices 
representam pessoas e as arestas, duas pessoas 
que se conhecem 
 
 O objetivo é identificar o grupo máximo de 
pessoas que se conhecem 
VIND máximo e Clique: Limitação 
 Não existe nenhum algoritmo de tempo polinomial 
que resolva estes problemas 
 Conjunto independente máximo de G 
 Clique de G 
 
 Apesar disso, é possível verificar em tempo 
polinomial se uma possível solução resolve o 
problema

Outros materiais