Aula 6 - Componentes conexos, grafos direcionados, busca em grafos direcionados, DAG, ordenação topológica

Prévia do material em texto

Teoria dos Grafos
Aula 6
Aula passada
BFS – 
implementação
Complexidade
Busca em 
profundidade (DFS)
Implementação
Aula de hoje
Componentes 
Conexos
Grafos direcionados
Busca em grafos 
direcionados
Ordenação topológica
 
Figueiredo – 2010
Componentes Conexos
Maiores subgrafos “conectados” de um grafo
mais precisamente...
Exemplo: 
Subgrafos maximais de G que sejam conexos
maximal: subconjunto que maximiza a 
propriedade, no caso subgrafo conexo
6
7
8
2 3
6
5 9
7
8
1
4
2
5
1
4
Componente
conexo?
Componente
conexo?
 
Figueiredo – 2010
Componentes Conexos
Problema: Determinar o número de 
componentes conexos de um grafo
e tamanho de cada componente
Algoritmo eficiente para 
resolver este problema?
 
Figueiredo – 2010
Componentes Conexos
Desmarcar todos os vértices
Escolher vértice s qualquer
Realizar BFS(s)
Vértices marcados determinam uma CC
Escolher vértice s qualquer não marcado
Realizar BFS(s)
Vértices marcados determinam outra CC
...
Usar Busca em Grafos (BFS ou DFS)
 
Figueiredo – 2010
Componentes Conexos
Complexidade do algoritmo anterior
Maior número de CC de um grafo?
Custo para detectar cada CC?
Usar marcações diferentes para cada CC
Complexidade?
O(m + n)
Figueiredo – 2010
Grafo Direcionado (Dígrafo)
Relacionamento não é simétrico!
A estar relacionado com B, não implica B estar 
relacionado com A
Exemplo de relacionamento assimétrico?
Abstração: arestas têm “direção”
par de vértices é ordenado
Exemplo: G = (V, E)
V = {1, 2, 3, 4}
E = {(1,2), (1,3), (2,3), (3,4)} 
1
3
2
4
Figueiredo – 2010
Grau
Grau de entrada: número de arestas que “entram” 
em v: |{(*,v)}|
Grau de saída: número de arestas que “saem” de 
v: |{(v,*)}|
Exemplo: G = (V, E)
ge(3) = ?
gs(3) = ?
ge(4) = ?
gs(7) = ?
Número máximo de arestas em G?
Relação entre ge(v) e gs(v)? Nenhuma
n(n-1)
1 7
4 6
5
3
2
8
Figueiredo – 2010
Caminho, Ciclo, Distância
Mesma definição de antes!
Respeitando o direcionamento das areas
Exemplo: G = (V, E)
Existe caminho de 5 para 2?
Ciclo que contém 1?
d(1,8) = ?
d(8,1) = ? 
d(7,1) = ?
1 7
4 6
5
3
2
8
Figueiredo – 2010
Fortemente Conexo
Análogo a conexo (no caso não direcionado)
Existe caminho entre qualquer par de 
vértices
mas caminho de u a v, não implica caminho 
de v a u
Exemplo: G = (V, E)
É fortemente 
conexo?
1 7
4 6
5
3
2
8
Figueiredo – 2010
Componentes 
Fortemente Conexos
Análogo a componentes conexos
Subgrafos maximais de G que são 
fortemente conexos
Exemplo: G = (V, E)
Componentes 
fortemente conexos?1 7
4 6
5
3
2
8
Figueiredo – 2010
Busca em Grafos Direcionados
Busca precisa respeitar direcionamento das 
arestas
(u, v) não é igual a (v, u)
BFS e DFS idênticas (respeitando arestas)
Mesmos algoritmos, mesma complexidade
Mesma idéia!
Mas há diferenças!
Figueiredo – 2010
Busca em Grafos Direcionados
Escolher vértice s (grafo direcionado)
Executar BFS à partir de s
Qual significado dos vértices marcados?
Vértices que s alcança!
Tais vértices alcançam s?
existe caminho de volta a s?
Figueiredo – 2010
Busca em Grafos Direcionados
Como descobrir quais vértices alcançam s?
Solução pouco eficiente
Para cada vértice do grafo, executar BFS e 
verificar se s é marcado
Idéias melhores?
Inverter a direção das arestas!
executar BFS no novo grafo à partir de s
vértices que s alcançou, alcançam s no grafo 
original!
Figueiredo – 2010
Busca em Grafos Direcionados
Exemplo
determinar vértices que chegam em 1?
1 7
4 6
5
3
2
8
Grafo com arestas invertidas: Grev
1 7
4 6
5
3
2
8
Executar BFS à partir 
de 1
Vértices marcados 
chegam em 1 no grafo 
original
Figueiredo – 2010
Fortemente Conexo
Problema: Como determinar se um grafo 
direcionado é fortemente conexo?
Como fizemos no caso não-direcionado?
Idéias?
Mesmo princípio de antes
Se s chega aos vértices u e v, e os vértices u e v 
chegam a s
Então u chega a v, via s
Figueiredo – 2010
Fortemente Conexo
Problema: Como determinar se um grafo 
direcionado é fortemente conexo?
Escolher vértice s qualquer
Executar BFS à partir de s
Construir Grev
Executar BFS à partir de s em Grev
Se todos os vértices foram marcados nas 
duas buscas, então G é fortemente conexo
Complexidade?
Figueiredo – 2010
Executando Tarefas
N tarefas precisam ser executadas
Tarefas são dependentes
Tarefas tem “pré-requisitos” (como sua 
grade curricular)
Problema: Qual ordem de execução 
não viola as dependências?
Modelar problema utilizando
grafos direcionados
Figueiredo – 2010
Executando Tarefas
Exemplo com 5 tarefas
B depende de A
A depende de C
C depende de D
B depende de E
B depende de D
C depende de E
A B
D
C
E
Qual é a ordem de execução?
Figueiredo – 2010
DAG
Grafo direcionado acíclico (DAG, em inglês)
importante estrutura em grafos
Tarefas podem ser executadas, somente se 
grafo de dependência é um DAG
não podemos ter ciclos!
Dado um DAG, como descobrir ordem de 
execução das tarefas?
Algoritmo (eficiente)!
Figueiredo – 2010
Ordenação Topológica
Dado grafo direcionado G
Ordenação dos vértices de G: v1, v2, ..., vn, 
tal que para toda aresta (vi, vj), i < j
Ordenação dos vértices de forma que 
arestas “apontam” sempre para frente
A B
D
C
E
Ordenação topológica?
v
1
 = E
v
2
 = D
v
3
 = C
v
4
 = A
v
5
 = B
Figueiredo – 2010
Ordenação Topológica
Problema: Dado um DAG, como determinar 
uma ordernação topológica?
Define uma ordem de execução das tarefas
Idéias?
Figueiredo – 2010
Ordenação Topológica
Algoritmo
1.Ordem = 0
2.Enquanto |V| > 0 faça
3. Encontrar u com grau de entrada zero
4. Ordem = Ordem + u
5. Remover u do grafo G
A B
D
C E
G
F
Exemplo
Figueiredo – 2010
Ordenação Topológica
Complexidade?
1.Ordem = 0
2.Enquanto |V| > 0 faça
3. Encontrar u com grau de entrada zero
4. Ordem = Ordem + u
5. Remover u do grafo G
Depende to tempo para remover u do grafo
Depende do tempo necessário para 
encontrar u
Procurar sequencialmente: O(n)
Complexidade O(n2)
Figueiredo – 2010
Ordenação Topológica
Como melhorar 
complexidade?
Manter lista dos vértices com grau zero
atualizar a cada remoção de vértice
Complexidade: O(m + n)
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24