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