Cap´ıtulo 6 Grafos - Parte II (Algoritmos)
Transcrição
Cap´ıtulo 6 Grafos - Parte II (Algoritmos)
Capı́tulo 6 Grafos - Parte II (Algoritmos) 6.1 Acessibilidade • nó acessı́vel: em um grafo direcionado, o nó nj é acessı́vel do nó ni se existe um caminho de ni para nj • matriz R de acessibilidade: R[i, j] = 1 se, e somente se, nj é acessı́vel a partir de ni • como obter? R = A ∨ A2 ∨ · · W · ∨ An onde: A2 [i, j] = nk=1 (aik ∧ akj ) e An = A · A · · · A (n vezes) ∧ e ∨ são os operadores booleanos AND e OR, respectivamente • Algoritmo de Warshall Algorithm 1 Warshall Require: M = matriz de adjacência de um grafo direcionado G for k = 0 até n − 1 do for i = 1 até n do for j = 1 até n do M [i, j] ← M [i, j] ∨ (M [i, k + 1] ∧ M [k + 1, j]) end for end for end for Ensure: M = matriz de acessibilidade de G 21 • quanto trabalho? o algoritmo de Warshall é de ordem n3 6.2 Caminho de Euler • um caminho de Euler em um grafo G é um caminho que usa cada arco em G exatamente um vez. • Teorema: Existe um caminho de Euler em um grafo conexo se, e somente se, não existem nós ı́mpares ou existem exatamente dois nós ı́mpares. 6.3 Circuito Hamiltoniano • um circuito hamiltoniano é um ciclo contendo todos os nós do grafo. • não existe algoritmo eficiente • problema do caixeiro viajante: caminho fechado que passe por todas as cidades e percorra a menor distância, ou seja, é um circuito hamiltoniano de peso mı́nimo. 6.4 Caminho mı́nimo • dado um grafo G simples, conexo e com pesos positivos, qual o caminho de peso mı́nimo entre dois nós x e y de G? • Algoritmo de Dijkstra 6.5 Árvore geradora mı́nima • uma árvore geradora para um grafo conexo é uma árvore sem raiz cujo conjunto de nós coincide com o conjunto de nós do grafo e cujas arestas são (algumas das) arestas do grafo • para um grafo com peso, a árvore geradora mı́nima é uma árvore de peso mı́nimo 22 Algorithm 2 Dijkstra Require: A = matriz de adjacência de um grafo com peso nós x e y para os quais o caminho mı́nimo será obtido Require: variáveis locais conjunto de nós IN {nós cujo caminho mı́nimo a partir de x é conhecido} nós z e p {nós temporários} vetor de inteiros d {contém as distâncias de x até cada nó} vetor de nós s {contém os nós anteriores para cada nó} inteiro DistAnterior IN ← {x} {inicializações} d[x] ← 0 for all z ∈ / IN do d[z] ← A[x, z] s[z] ← x end for while y ∈ / IN do {insere p em IN e atualiza os vetores d e s} p ← nó z ∈ / IN com d[z] mı́nimo IN ← IN ∪ {p} for all z ∈ / IN do DistAnterior ← d[z] d[z] ← min{d[z], d[p] + A[p, z]} if d[z] 6= DistAnterior then s[z] ← p end if end for end while Ensure: d[y] = distância mı́nima caminho mı́nimo: x, . . . , s[s[y]], s[y], y 23 • Algoritmo de Prim Algorithm 3 Prim Require: A = matriz de adjacência de um grafo com peso nó inicial x Require: variáveis locais conjunto de nós IN {nós que compõem a árvore mı́nima} nós z e p {nós temporários} vetor de inteiros d {contém as distâncias de cada nó ao nó pai} vetor de nós s {contém o nó pai de cada nó} inteiro DistAnterior IN ← {x} {inicializações} d[x] ← 0 for all z ∈ / IN do d[z] ← A[x, z] s[z] ← x end for while todos os nós ∈ / IN do {insere p em IN e atualiza os vetores d e s} p ← nó z ∈ / IN com d[z] mı́nimo IN ← IN ∪ {p} for all z ∈ / IN do DistAnterior ← d[z] d[z] ← min{d[z], A[p, z]} if d[z] 6= DistAnterior then s[z] ← p end if end for end while Ensure: d contém o peso da aresta que liga cada nó a seu pai na árvore mı́nima s contém o nó pai de cada nó da árvore mı́nima 6.6 Algoritmos de percurso • Algoritmo de busca em profundidade ou deep-first search • Algoritmo de busca em nı́vel ou breadth-first search 24 Algorithm 4 Busca em profundidade Require: grafo G e nó x marque x como visitado print x for all nó n adjacente a x do if n não visitado then CALL Busca em profundidade (G, n) end if end for Ensure: todos os nós “abaixo” de x foram visitados (em profundidade) Algorithm 5 Busca em nı́vel Require: grafo G e nó x Require: variáveis locais fila de nós F inicialize F vazio marque x como visitado print x inserir(x, F ) {insere x no final da fila} while F não vazio do for all nó n adjacente a frente(F ) do {frente(F ) obtém o primeiro nó da fila} if n não visitado then marque n como visitado print n inserir(n, F ) end if end for retirar(F ) {elimina o primeiro nó da fila} end while Ensure: seqüência impressa é o resultado da busca em nı́vel 25 • Aplicações: 1. árvore geradora 2. acessibilidade 3. ordenação topológica 4. componentes conexas de um grafo 6.7 Pontos de articulação • um nó em um grafo simples conexo é um ponto de articulação se sua remoção (junto com os arcos dos quais ele é uma extremidade) torna o grafo desconexo • um grafo conexo simples é biconexo se não tem pontos de articulação • Algoritmo Ponto de Articulação • exceção: nó inicial o nó inicial é um ponto de articulação se dois ou mais arcos de árvore partem do nó inicial 26 Algorithm 6 Ponto de Articulação Require: grafo G, nó n, inteiro NumArvore marque n como visitado N umArvore ← N umArvore + 1 N uArvore[n] ← N umArvore N uT ras[n] ← N uArvore[n] for all nó x adjacente a n por um arco de trás do if x não visitado then faça n − x um arco de árvore CALL Ponto de Articulação (G, x, NumArvore) if N uT ras[x] ≥ N uArvore[n] then print n é um ponto de articulação else N uT ras[n] ← min{N uT ras[n], N uT ras[x]} end if else N uT ras[n] ← min{N uT ras[n], N uArvore[x]} end if end for Ensure: nós impressos são pontos de articulação (exceto o nó inicial) 27
Documentos relacionados
Método Bonecas Russas para Conjunto Independente
computacionais cujos resultados são descritos e analisados em artigos publicados nos últimos anos dão conta de que o uso de coberturas por vértices, de paralelismo nas operações sobre a matri...
Leia maisTeoria dos Grafos
peso ótimo (máximo ou mı́nimo). Um exemplo é o famoso Problema do Caixeiro Viajante onde o caixeiro deseja passar por todas as n cidades de uma região e voltar à cidade de origem percorrendo a...
Leia mais