Baixe o app para aproveitar ainda mais
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
Compartilhar