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