aula-algoritmos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Prof. Tarcisio Rocha
Algoritmos em Grafos
Prof. Tarcisio Rocha
Livro Texto: 
• Cormen, T., Leiserson, C., Rivest, R. and Stein, C. “Algoritmos – Teoria e Prática”, Elsevier, 2002.
Busca em Largura
� Considere:
� um grafo G = (V, E)
� um vértice de origem s, 
� Busca em largura: 
� explora sistematicamente as arestas de G até descobrir cada vértice � explora sistematicamente as arestas de G até descobrir cada vértice 
acessível a partir de s;
� calcula a distância (caminho mais curto) desde s até todos os vértices 
acessíveis a partir de s.
� “em largura”
� Descobre todos os vértices à distância k a partir de s, antes de descobrir 
quaisquer vértices à distância k + 1.
Busca em Largura
� Controle do andamento do algoritmo
� Utiliza três tipos de marcações para os vértices
� Vértice branco
� É um vértice ainda não descoberto pelo algoritmo 
� Vértice cinza
� É um vértice que já foi descoberto pelo algoritmo mas que ainda 
possui vértices adjacentes não descobertos.
� Vértice preto
� É um vértice que já foi descoberto pelo algoritmo e que não possui 
nenhum vértice adjacente que ainda não foi descoberto.
Busca em Largura
� O Algoritmo:
� G = (V,E) é representado com o uso de listas de adjacência.
� A cada vértice v são adicionadas as seguintes informações
� cor[v] – indica a cor do vértice v
� pi[v] – indica o vértice predecessor de v, ou seja, o vértice a partir do qual [v] – indica o vértice predecessor de v, ou seja, o vértice a partir do qual 
v foi descoberto
� d[v] – indica a distância entre s e v, onde s é o vértice de origem
� O conjunto de vértices de cor cinza é mantido em uma fila Q 
do tipo FIFO (o primeiro a entrar é o primeiro a sair)
Busca em Largura
� O Algoritmo:
Busca em Largura
� Exemplo
Busca em Profundidade
� Tenta-se e explorar novos vértices a partir do vértice mais 
recentemente descoberto.
� Informações
� cor[v] – indica a cor do vértice v (branco, cinza ou preto)
� pi[v] – indica o vértice predecessor de v, ou seja, o vértice a partir do qual 
v foi descobertov foi descoberto
� Dois carimbos de tempo:
� d[v] – indica o “tempo” em que o vértice v foi descoberto (pintado de 
cinza)
� f[v] – indica o “tempo” em que o o algoritmo termina de examinar a 
lista de adjacências de v (v é pintado de preto)
o d[v] e f[v] compartilham o mesmo contador de tempo
o O contador de tempo é um inteiro entre 1 e 2|V|
Busca em Profundidade
Busca em Profundidade
Busca em Profundidade
� Propriedades
� Produz informações sobre a estrutura de um grafo
� Floresta de árvores
� Estrutura de parênteses
� Classificação das arestas
� Arestas de árvore
� Arestas de retorno
� Arestas diretas
� Arestas cruzadas
Busca em Profundidade
� Estrutura de Parênteses
� Representação
� A descoberta de um vértice (u) é representada por “(u”
� O término de um vértice é representado por “u)”
� A história de descobertas e términos forma uma expressão bem 
formada
Retângulos: linha de tempo
Aninhamento: parentesco
Busca em Profundidade
� Classificação das Arestas
� Aresta de árvore
� Arestas na floresta. 
� Arestas de retorno
� Arestas (u, v) que conectam u a um ancestral v em uma árvore.
Busca em Profundidade
� Classificação das Arestas
� Aresta diretas
� Arestas (u, v) que conectam u a um descendente v em uma árvore. 
� Arestas cruzadas
� Todas as outras arestas.
Busca em Profundidade
� Classificação das Arestas
� Aplicação
� Ex: Descoberta de grafos orientados acíclicos: UM GRAFO 
ORIENTADO É ACÍCLICO SSE EM UMA BUSCA EM 
PROFUNDIDADE NÃO É ENCONTRADA NENHUMA ARESTA DE 
RETORNORETORNO
Busca em Profundidade
� Classificação das Arestas
� Como classificar as arestas?
� Cada aresta (u, v) pode ser classificada pela cor do vértice v que é 
alcançado pelo algoritmo
� BRANCO – indica uma aresta de árvore
� CINZA – indica uma aresta de retorno� CINZA – indica uma aresta de retorno
� PRETO – indica uma aresta direta ou cruzada
Busca em Profundidade
� Classificação das Arestas
� Grafos não orientados
� Em uma busca em profundidade de um grafo G, toda aresta de G é uma 
aresta de árvore ou uma aresta de retorno.
Ordenação Topológica
� Definição
� A ordenação toplógica de um gao G=(VG, AG) é uma 
ordenação linear de todos os seus vértices tal que se G contém 
uma aresta (u, v), então u aparece antes de v na ordenação.
� Pode ser vista como uPode ser vista como u
� Aplicação
� Grafos acíclicos orientados (gao’s) 
� Se o grafo não é acíclico, então não é possível nenuma ordenação linear
Ordenação Topológica
� Algoritmo 
� Baseado no algoritmo de busca em profunidade (DFS)
1. Chamar DFS(G) para calcular o tempo de término de f[v] para cada 
vértice v
2. À medida que cada vértice é terminado, inserir o vértice à frente de 
uma lista ligadauma lista ligada
3. Devolva como redultado a lista ligada
Ordenação Topológica
� Exemplo
� Ordenação topológica de vestuário
Ordenação Topológica
� Exemplo
� Ordenação topológica de vestuário
Componentes Fortemente Conectados
� Definição
� Um componente fortemente conectado de um grafo G=(VG, 
AG) é um conjunto máximo de vértices C ⊆VG tal que, para 
todo par de vértices u e v em C:
� u é acessível a partir v
� v é acessível a partir u
Componentes Fortemente Conectados
� O Algoritmo
Árvores Geradoras Mínimas
� Definição 
� Árvore geradora na qual o somatório dos pesos das suas arestas 
é minimo (não existe uma outra árvore geradora que possua um 
somatório de pesos menor)
� ExemploExemplo
� Menor uso de cabos na interconexão de componentes elétricos (o peso 
entre as arestas é a distância entre os componentes)
Árvores Geradoras Mínimas
� Algoritmo Genério
� Tipo guloso
� Parte-se de um vértice (subconjunto da árvore geradora) adicionando 
arestas seguras até completar a árvore 
Árvores Geradoras Mínimas
� Algoritmo Genério
� Definições
� Um corte (S, V-S) de um grafo G=(V,E) é uma partição de V
� Uma aresta que cruza um corte é leve se seu peso é mínimo com relação a 
qualquer outra aresta que cruza o mesmo corte. 
Árvores Geradoras Mínimas
� Algoritmo de Prim
� Durante a execução do algoritmo, todos os vértices que estão em uma fila de 
prioridade mínima Q baseada em um campo chave
� Para cada vértice v, chave[v] é o peso mínimo de qualquer aresta que 
conecta v a um vértice na árvore
w(u,v) – peso da aresta que liga u a v
Árvores Geradoras Mínimas
� Exemplo
(0)
(4)
(8)
(∞)
(∞)
(∞)
(∞)
(∞)
(∞)
(0)
(4)
(8)
(8)
(∞)
(∞)
(∞)
(∞)
(∞)
(8) (∞) (∞) (8) (∞) (∞)
(0)
(4)
(8)
(8)
(2)
(∞)
(7)
(4)
(∞)
(0)
(4)
(7)
(8)
(2)
(6)
(7)
(4)
(∞)
Árvores Geradoras Mínimas
(0)
(4)
(7)
(8)
(2)
(2)
(7)
(4)
(10)
(0)
(4)
(1)
(8)
(2)
(2)
(7)
(4)
(10)
(4) (8) (7) (4) (8) (7)
(0)
(4)
(1)
(8)
(2)
(2)
(7)
(4)
(10)
(0)
(4)
(1)
(8)
(2)
(2)
(7)
(4)
(9)
(0)
(4)
(1)
(8)
(2)
(2)
(7)
(4)
(9)
Caminhos Mais Curtos
� O Algoritmo de Dijkstra
� Calcula o caminho mais curto entre um vértice de origem e os demais 
vértices do grafo
� Operação de relaxamento de aresta (RELAX)
� Relaxar uma aresta (u,v) consiste em tentar melhorar o caminho mais 
curto para v encontrado até agora pela passagem através de u e, nesse curto para v encontrado até agora pela passagem através de u e, nesse 
caso, atualizar d[v] e pi[v]
� d[v] – caminho mais curto da origem até v; pi[v] - antecessor de v
Caminhos Mais Curtos
� O Algoritmo de Dijkstra
Caminhos Mais Curtos
� O Algoritmo de Dijkstra
Coloração Aproximada
� Um Algoritmo
� Q - lista dos vértices ordenados pelos seus graus
� EXTRACT-MAX(Q) – retira de Q o vértice de maior grau
COLORIR(G)
1 for cada u ∈ V[G]1 for cada u ∈ V[G]
2 do cor[u] ← 0
3 cor[r] ← 1
4 Q ← V[G] – r
5 while Q ≠ 0
6 do u ← EXTRACT-MAX(Q)
7 cor ←min { i | cor[Adj[u]] ≠ i} 
8 cor[u] ← cor
Coloração Aproximada
� Exemplos de aplicação
� Ex 1: Estipulação de horários para realização de provas
. D1 D2 D3 D4 D5 D6 D7
D1 . * * * - * *
Disciplinas
D1 . * * * - * *
D2 * . * - - - *
D3 * * . * - - -
D4 * - * . * * -
D5 - - - * . * -
D6 * - - * * . *
D7 * * - - - * .
* = ocorrência de alunos em comum
Coloração Aproximada
� Exemplos de aplicação
� Ex 1: Estipulação de horários para realização de provas
. D1 D2 D3 D4 D5 D6 D7
D1 . * * * - * *
Disciplinas
D1 . * * * - * *
D2 * . * - - - *
D3 * * . * - - -
D4 * - * . * * -
D5 - - - * . * -
D6 * - - * * . *
D7 * * - - - * .
* = ocorrência de alunos em comum
Cor = horário da prova
Coloração Aproximada
� Exemplos de aplicação
� Ex 2: Atribuibuição de armários em uma creche
. 1 2 3 4 5 6 7
7:00 * - - * * - -
Crianças
H
o
r
á
r
i
o
s
 
q
u
e
 
e
s
t
ã
o
 
n
a
 
c
r
e
c
h
e
7:00 * - - * * - -
8:00 * * * - - - -
9:00 * - * * - * -
10:00 * - * - - * *
11:00 * - - - - * *
12:00 * - - - * - -
H
o
r
á
r
i
o
s
 
q
u
e
 
e
s
t
ã
o
 
n
a
 
c
r
e
c
h
e
Coloração Aproximada
� Exemplos de aplicação
� Ex 2: Atribuibuição de armários em uma creche
. 1 2 3 4 5 6 7
7:00 * - - * * - -
Crianças
H
o
r
á
r
i
o
s
 
q
u
e
 
e
s
t
ã
o
 
n
a
 
c
r
e
c
h
e
7:00 * - - * * - -
8:00 * * * - - - -
9:00 * - * * - * -
10:00 * - * - - * *
11:00 * - - - - * *
12:00 * - - - * - -
H
o
r
á
r
i
o
s
 
q
u
e
 
e
s
t
ã
o
 
n
a
 
c
r
e
c
h
e
Cor = armário
Fluxo Máximo em Redes
� Tipos de Redes
� Rede de computadores 
� Fluxo de dados
� Rede elétrica
� Fluxo de energia
� Rede de esgotoRede de esgoto
� Fluxo de água/dejetos
� Rede de abastecimento de água
� Fluxo de água potável
Fluxo Máximo em Redes
� Conceitos Básicos
� Origem (Fonte)
� Produz “material” em uma taxa fixa
� Sorvedor (Destino)
� Consome “material” na mesma taxa da origem
� Fluxo
� Taxa na qual o material se move
Fluxo Máximo em Redes
� Definições
� Fluxo em rede
� É um grafo orientado G=(V, E) em que cada aresta (u, v) ∈ E tem uma 
capacidade não negativa c(u, v) ≥ 0
� Distinguem-se dois vértices em um fluxo em rede:
� Um vértice de origem s� Um vértice de origem s
� Um vértice sorvedor t
Fluxo Máximo em Redes
� Propriedades
� Um fluxo G é uma função de valor real f:VxV → R que satisfaz 
as três propriedades seguintes:
v, uv, u
Fluxo Máximo em Redes
� Definições
� Fluxo total positivo que entra em um vértice v
� ∑ f(u,v)
� Fluxo total positivo que sai de um vértice v
u ∈ V
f(u,v)>0
� ∑ f(v,u)
� Fluxo total líquido de um vértice v
� Diferença entre o fluxo total positivo de saída de v e o fluxo total positivo 
de entrada de v
� Pela propriedade de conservação de fluxo, o fluxo total líquido de um 
vértice deve ser sempre igual a 0
u ∈ V
f(v,u)>0
� Problema de transporte
� Como determinar o número máximo de caixotes que podem 
ser enviados por dia?
� Manter a conservação de fluxo
Exemplo de Fluxo
� Redução a um problema de fluxo máximo comum
Redes com várias origens e sorvedores
superorigem superdestino
� O método de Ford-Fulkerson
� Conceitos necessários
� Redes residuais
� Caminhos aumentantes
� Cortes
Encontrando o fluxo máximo
� Algoritmo genérico
� O método de Ford-Fulkerson
� Redes residuais
� Dados um fluxo em rede e um fluxo, a rede resiual consite em arestas que 
podem admitor mais fluxo
� Definição formal
� Considere um fluxo de rede G=(V,E) com origem s e sorvedor t. 
Encontrando o fluxo máximo
� Considere um fluxo de rede G=(V,E) com origem s e sorvedor t. 
� Seja f um fluxo em G, e considere um par de vértices u, v ∈V. 
� A capacidade residual de (u, v) é a quantidade de fluxo adicional que 
podemos empurrar desde u até v antes de exceder a capacidade c(u, v)
o cf(u,c) = c(u,v) – f(u,v)
� A rede residual de G induzida por f é Gf=(V,Ef)
� O método de Ford-Fulkerson
� Redes residuais
Encontrando o fluxo máximo
R
e
d
e
s
 
r
e
s
i
d
u
a
i
s
� O método de Ford-Fulkerson
� Caminhos aumentantes
� Dados um fluxo em rede G=(V,E) e um fluxo f, um caminho aumentante 
p é um caminho desde s até t na rede residual Gf
� Capacidade residual de p
� Quantidade máxima pela qual podemos aumentar o fluxo em cada 
Encontrando o fluxo máximo
� Quantidade máxima pela qual podemos aumentar o fluxo em cada 
aresta de p 
o cf(p) = min{cf(u,v): (u,v) está em p}
� O método de Ford-Fulkerson
� Caminho aumentante
Encontrando o fluxo máximo
� O método de Ford-Fulkerson
� Cortes de fuxo em redes
� Um corte (S,T) de um fluxo em rede G=(V,E) é uma partição de V em S 
e T=V-S tal que s∈S e t∈T
� Se f é um fluxo, então o fluxo líquido pelo corte (S,T) é definido como 
f(S,T).
Encontrando o fluxo máximo
f(S,T).
� A capacidade do corte (S,T) é c(S,T)
� Um corte mínimo de uma rede é um corte cuja capacidade é mínima 
dentre todos os cortes da rede
� O método de Ford-Fulkerson
� Cortes de fuxo em redes
� Exemplo
� Corte ({s, v1, v2}, {v3, v4, t})
� Fluxo líquido: f(v1,v3) + f(v2,v3) + f(v2,v4) = 12+(-4)+11 = 19
Encontrando o fluxo máximo
� Capacidade: c(v1,v3) + c(v2,v4) = 12+14 = 26
� O algoritmo básico de Ford-Fulkerson
� A cada interação, encontramos algum caminho aumentante p e 
aumentamos o fluxo f em cada aresta de p pela capacidade 
residual cf(p) 
Encontrando o fluxo máximo
� O algoritmo básico de Ford-Fulkerson
Encontrando o fluxo máximo
� O algoritmo básico de Ford-Fulkerson
Encontrando o fluxo máximo
� Emparelhamento em grafos bipartidos
Emparelhamento bipartido máximo
Como encontrar um emparelhamento máximo?
� Emparelhamento máximo a partir de um fluxo em rede
� Artifício
� Construir um fluxo em rede G´=(V´,E´) a partir do grafo bipartido 
G=(V,E) no qual os fluxos equivalem a emparelhamentos
� A origem s e o sorvedor t são novos vertices não pertencentes a V
� V´=V∪{s,t}
Emparelhamento bipartido máximo
� V´=V∪{s,t}
� Se a partição de vértices de G é V = L ∪ R, as arestas orientadas de G´são 
arestas de E, orientadas de L para R, junto com |V| novas arestas
� Atribui-se capacidade unitária a cada aresta
� Usa-se o método de Ford-Fulkerson para encontrar um fluxo máximo
� O caminho aumentante escolhido deve ser o lexicograficamente 
menor
� O fluxo máximo resultante corresponderá a um emparelhamento 
máximo no subgrafo bipartido G de G´
� Emparelhamento máximo a partir de um fluxo em rede
Emparelhamento bipartido máximo
G G´